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

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

کلیدواژه ها:

متافیزیک ، برنامه نویسی GPU ، بهینه سازی مورچه کلونی ، TSP ، تجزیه و تحلیل عملکرد