مروری بر پیاده سازی مبتنی بر GPU الگوریتم های هوش جمعی

مقاله: مروری بر پیاده سازی مبتنی بر GPU الگوریتم های هوش جمعی

این مقاله در سال 2015 توسط Ying Tanو Ke Ding با موضوع مروری بر پیاده سازی های مبتنی بر GPU از الگوریتم های هوش جمعی در IEEE پذیرفته شده است.

با الهام از طبیعت الگوریتم های هوش جمعی به طور گسترده ای برای حل مسائل بهینه سازی مورد استفاده قرار می گیرند. زمانی که برای حل مسائل پیچیده مورد استفاده قرار می گیرند تعداد زیادی از ارزیابی های توابع برازش برای بدست آوزدن راه حل قابل قبول مورد نیاز است. برای مقابله با این مسئله حیاتی، واحد های فرآیند گرافیکی (GPU) برای سرعت بخشیدن به فرآیند بهینه سازی الگوریتم های هوش جمعی مورد استفاده قرار می گیرد.

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

این مقاله یک مرور جامعی از الگوریتم های هوش جمعی مبتنی بر GPU مطابق با تازه ترین طبقه بندی پیشنهاد شده ارائه داده است.  علاوه بر این معیارهای جدید برای ارزیابی و مقایسه پیاده سازی موازی و کارائی الگوریتم در سطح جهانی پیشنهاد شده است.

عقلانی و عملی بودن متدولوژی و معیارهای بهینه سازی پیشنهاد شده با مطالعه موردی (case study) دقیق مورد ارزیابی قرار گرفته شده است.

در این مقاله، الگوریتم های هوش جمعی مبتنی بر GPU به چهار دسته مختلف طبقه بندی شده است. پیاده سازی موازی الگوریتم های هوش جمعی هم روی CPU و هم روی GPU اجرا شده است. علاوه بر معیار کارائی، بازدهی اصلاح شده برای ارزیابی پیاده سازی موازی پیشنهاد شده است.

بهینه سازی چند هدفه (MOO) همیشه جزو موضوعات داغ در هوش جمعی ها بوده است. با این حال، پیاده سازی های کمی قادر به استفاده از توانایی محاسباتی GPU را دارد چون چند هدفه ها محاسبات متمرکز تر و فشرده تری نسبت به تک هدفه ها دارند.

بیشتر از سکوی CUDA برای پیاده سازی مسائل هوش جمعی مبتنی بر GPU مورد استفاده قرار می گیرد. که البته ایراد آن در این است که محدود به کارت گرافیک های شرکت انویدیا می باشد.

الگوریتم های هوش جمعی مبتنی بر GPU

 در واقع، الگوریتم های هوش جمعی از نوع الگوریتم های جستجوی تصادفی مبتنی بر تکرار هستند که اطلاعات ابتکاری آنها به منظور راهنمائی در جستجوهای متوالی به اشتراک گذاشته می شود. در شکل 1 یک چارچوب کلی ساده برای الگوریتم های هوش جمعی نشان داده شده است.

شکل 1: چارچوب کلی الگوریتم های هوش جمعی

ترتیب هر فاز و مدت زمان اجرای هر مرحله می تواند متفاوت باشد به همین دلیل، اینکه هر فاز چطور به پردازنده ها نگاشت شود می تواند پیاده سازی های مبتنی بر GPU مختلفی ایجاد شود که در اینجا به چهار دسته بزرگ تقسیم شده است:

الف: مدل موازی ساده

در شکل 2 مدل موازی ساده نشان داده شده است. به دلیل سادگی این روش و اینکه می توان تقریباً در تمام الگوریتم های هوش جمعی آن را استفاده کرد این مدل را موازی ساده نامگذاری شده است. پیاده سازی مدل موازی ساده می تواند دانه درشت (موازی سازی وظیفه) یا ریز دانه پنج تائی (موازی سازی داده) باشد.

شکل 2: مدل موازی ساده برای الگوریتم های هوش جمعی

زمانی که تابع برازش فاقد موازی سازی است یا ارزیابی های مستقل زیادی به طور همزمان وجود دارد روش دانه درشت مناسب می باشد. در این شرایط ، همان طور که در شکل 3 قسمت a نشان داده شده است، هر وظیفه به یک نخ نگاشت می شود.

مدل موازی ساده زمانی که تابع برازش موازی می شود بسیار جالب می شود. در آن صورت، این تابع می تواند به عنوان ترکیبی از تعداد معینی از توابع ذرات که به صورت موازی می تواند اجرا شود نمایش داده شود. به طور مثال، در شکل 3 قسمت b پیاده سازی ریز ذره پنج تائی آن نشان داده شده است. 

شکل 3: مثالی از مدل موازی ساده با (a) دانه درشت و (b) ریز دانه پنج تائی

ب: مدل موازی چند فازی

در مدل موازی چند مرحله ای تلاش می شود که محاسبات offload از فازهای مختلف با موازی سازی صریح و ضمنی در داخل GPU ایجاد شود. مراحل این مدل در شکل 4 نشان داده شده است.

شکل 4: مدل موازی چند فازی

برخلاف مدل موازی ساده که برای همه الگوریتم های هوش جمعی عمومیت داشت به الگوریتم وابسته می باشد. هسته های چندگانه می تواند برای موازی سازی مراحل مختلف پیاده سازی شود و همچنین هسته های مختلف می توانند برای رسیدن به بهترین برازش وظایف خاص استراتژی های موازی مختلف بکار ببرند. برخی از این استراتژی ها مانند عملگر بردار می باشد مثلاً در مسئله بهینه سازی ازدحام ذرات سرعت و موقعیت را می توان نام برد. استراتژی دیگر، کاهش می باشد که بلوک ساختاری هسته برای محاسبات موازی می باشد. مثلاً در برخی از مسائلی کرم شب تاب و PSO منظور محاسبه فاصله می باشد. استراتژی دیگر، مرتب سازی می باشد که یک بلوک مبنا برای بسیاری از الگوریتم های هوش جمعی مانند الگوریتم زنبور عسل می باشد. استراتژی دیگر، ساخت مسیر می باشد که یکی از موضوعات داغ در تحقیقات می باشد به عنوان مثال موازی سازی انتخاب چرخه رولت برای ساخت مسیر در الگوریتم کلونی مورچگان بسیار موثر می باشد. استراتژی دیگر، بروزرسانی فرمون می باشد که در الگوریتم ACO جزو موضوعات فعال می باشد که شامل دو وظیفه اصلی می باشد: (a تبخیر فرومون و (b اثر فرومون. موازی سازی فرمون بی اثر می باشد. استراتژی آخر، موازی سازی های دیگر می باشد که برای الگوریتم هوش جمعی خاص، رسیدگی ویژه برای پیاده سازی موازی مبتنی بر GPU لازم می باشد.

ج: مدل موازی GPU کامل

در مقایسه با سرعت محاسباتی GPU، ارتباط بین CPU و GPU خیلی پایین می باشد. سربار هسته تکرار شونده همچنین یک فاکتور بالقوه در صدمه زدن به کارائی GPU می باشد. بنابراین، همان طور که در شکل 5 نشان داده شده است، بهتر است که کل برنامه روی GPU اجرا شود. در این حالت کد سریال نیز داخل GPU نوشته می شود.

شکل 5: مدل موازی GPU کامل

د: مدل موازی چند جمعیتی

برای مسائل با ابعاد بزرگ و مقیاس بالا، مدل موازی چند جمعیتی به عنوان یک روش طبیعی وجود دارد این روش نه تنها برای کاهش زمان جستجو بلکه برای بهبود کیفیت راه حل ها مفید می باشد. همان طور که در شکل 6 نشان داده شده است به جای اجرا در یک جمعیت تنها، در مدل موازی چند جمعیتی، جمعیت به زیر جمعیت های کمی تقسیم می شوند. و هر کدام از آنها به طور جداگانه در قالب نخ یا گروهی از نخ ها مورد استفاده قرار می گیرند. این روش، مدل جزیره ای نیز نامیده می شود.  

شکل 6: مدل موازی چند جمعیتی

در ادامه مقاله به نکاتی مانند شماره های شناور، دسترسی حافظه، تولید عدد تصادفی و واگرائی بخش  در اجرای GPU اشاره شده است. در شکل 7 سلسله مراتب حافظه GPU نشان داده شده است.

شکل 7: سلسله مراتب حافظه GPU

در شکل 8 ، speed up سراسری CPU در مقایسه با GPU با مدل ساده موارزی نشان داده شده است.

شکل 8: speed up سراسری بدست آمده با پیاده سازی مبتنی بر GPU به کمک مدل ساده

در شکل 9 نتایج راه حل های بدست آمده در شرایط مختلف نشان داده شده است.

شکل 9: مقایسه راه حل ها بدست آمده در شرایط مختلف

  [1].  Ying Tan, Ke Ding,,” A Survey on GPU-Based Implementation of Swarm Intelligence Algorithms”, IEEE,2015.