پیاده سازی موازی الگوریتم بهینه سازی جستجوی فاخته با زبان OpenCL بر روی GPU و بررسی تسریع حاصل از آن

یکی از مباحث مهم در علوم کامپیوتر و ریاضی بهینه سازی مسائل غیر قابل حل با روش های ریاضی معمول، با استفاده از روش های مبتنی بر تکرار است. در میان روش های مبتنی بر تکرار، الگوریتم های مبتنی بر جمعیت و الهام گرفته شده از طبیعت جایگاه خاصی دارند. اما موضوعی که مطرح می شود این است که اجرای این الگوریتم ها روی سیستم های کامپیوتری اغلب بسیار زمانگیر است. از این رو موازی سازی آن ها می تواند بسیار مفید و کمک کننده باشد. در این مقاله یکی از جدیدترین الگوریتم های بهینه سازی مبتنی بر جمعیت، را بطور موازی و با استفاده از زبان برنامه نویسی موازی OpenCL پیاده سازی می نماییم. این الگوریتم که از طبیعت الهام گرفته شده است، الگوریتم جستجوی فاخته نام دارد و بر اساس رفتار ادامه ی نسل پرنده ی فاخته عمل بهینه سازی را انجام می دهد. با انجام آزمایش های متنوع روی دو تابع معروف Sphere و Rosenbrock مقایسه ای بین برنامه ی موازی و سریال انجام می دهیم. این آزمایش ها بر روی یک GPU-GeForce GT 230M شامل 48 هسته انحام شده است. نتایج نشان می دهند که در محاسبات متوسط تا سنگین، با افزایش بار کاری روی سیستم، که منشأ آن می تواند پیچیدگی مسئله، یا اندازه ی جمعیت مورد استفاده باشد، تسریع موجود بین 32/1 تا 11/8 است.

کلیدواژه ها:

الگوریتم بهینه سازی جستجوی فاخته ، OpecCL ، موازی سازی ، GPU