افزایش موازات داده ها برای بهینه سازی مومیایی مورچه در پردازنده های گرافیکی

قیمت: 41,000 تومان

دانلود رایگان مقاله

خرید ترجمه مقاله

عنوان فارسی

افزایش موازات داده ها برای بهینه سازی مومیایی مورچه در پردازنده های گرافیکی

عنوان لاتین

Enhancing data parallelism for Ant Colony Optimization on GPUs

واحد پردازش گرافیکی (GPU) ها طی پنج سال گذشته به معماری بسیار موازی و کاملا برنامه ریزی شده تبدیل شده است و ظهور CUDA کاربرد آنها را در بسیاری از برنامه های کاربردی دنیای واقعی تسهیل کرده است. در این مقاله ما با استفاده از یک GPU بهینه سازی مورچه Colony (ACO)، یک روش بهینه سازی جمعیتی که شامل دو مرحله عمده است: ساخت تور و به روز رسانی فروم است. به دلیل ماهیت ذاتی آن، ACO برای اجرای GPU بسیار مناسب است، اما با توجه به الگوهای دسترسی نامنظم حافظه، چالش های مهمی نیز ایجاد می کند. سهم ما در این زمینه سه برابر است: (1) یک طرح همپوشانی داده برای ساخت تور در قالب پردازنده های گرافیکی، (2) استراتژی های برنامه ریزی گرافیکی جدید برای مرحله به روز رسانی فرومون و (3) یک مکانیزم جدید به نام I-Roulette برای تکرار چرخش کلاسیک در حالی که بهبود موازی GPU. پیاده سازی ما منجر به افزایش کارایی بیش از 20x برای هر یک از دو مرحله الگوریتم ACO به عنوان TSP در مقایسه با نسخه همپوشانی پس از آن در حال اجرا بر روی یک CPU بالا پایان تک رشته مشابه است. علاوه بر این، بحث گسترده ای که در مورد راه های مختلف پیاده سازی در GPU ها متمرکز شده است نشان می دهد که راه برای مقابله با اجزای وابسته به گراف موازی شده است. این به نوبه خود، یک منطقه گسترده تر از تحقیق را پیشنهاد می دهد، که در آن طراحان الگوریتمی ممکن است یاد بگیرند که روش های مشابه بهینه سازی را برای معماری GPU سازگار کنند.

Graphics Processing Units (GPUs) have evolved into highly parallel and fully programmable architecture over the past five years, and the advent of CUDA has facilitated their application to many real-world applications. In this paper, we deal with a GPU implementation of Ant Colony Optimization (ACO), a population-based optimization method which comprises two major stages: tour construction and pheromone update. Because of its inherently parallel nature, ACO is well-suited to GPU implementation, but it also poses significant challenges due to irregular memory access patterns. Our contribution within this context is threefold: (1) a data parallelism scheme for tour construction tailored to GPUs, (2) novel GPU programming strategies for the pheromone update stage, and (3) a new mechanism called I-Roulette to replicate the classic roulette wheel while improving GPU parallelism. Our implementation leads to factor gains exceeding 20x for any of the two stages of the ACO algorithm as applied to the TSP when compared to its sequential counterpart version running on a similar single-threaded high-end CPU. Moreover, an extensive discussion focused on different implementation paths on GPUs shows the way to deal with parallel graph connected components. This, in turn, suggests a broader area of inquiry, where algorithm designers may learn to adapt similar optimization methods to GPU architecture.