افزایش موازی سازی GPU برای الگوریتم های الهام گرفته شده از طبیعت

مقاله: افزایش موازی سازی GPU برای الگوریتم های الهام گرفته شده از طبیعت

این مقاله در سال 2012 توسط José M. Cecilia و همکارانش با موضوع افزایش موازی سازی GPU برای الگوریتم های الهام گرفته شده از طبیعت در Springer به چاپ رسیده است.

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

در این مقاله به بررسی رفتار الگوریتم ACO و روش های سیستم P روی GPU پرداخته شده است. ناکارآمدی های اصلی پیاده سازی ها شناسایی می شود و از طریق بهینه سازی های مختلف بهبود قابل قبولی ارائه می شود. دید کلی در این مقاله:

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

تنظیم الگوریتم کلونی مورچگان برای حل مسئله فروشنده دوره گرد روی GPU

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

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

شکل 1: الگوریتم حل مسئله TSP به کمک ACO

ساخت مسیر به دو مرحله مقداردهی اولیه و ASDecisionRule تقسیم می شود. در ابتدا همه ساختار داده توسط هر مورچه مقداردهی می شوند و مورچه ها به طور تصادفی به شهر ها تخصیص داده می شوند.

شکل 2 الگوریتم شماره دو را نشان می دهد که در آن مرحله دوم را به تصویر کشیده است که خود شامل دو زیر مرحله می باشد: اول، هر مورچه اطلاعات ابتکاری را محاسبه می کند به منظور اینکه آیا از شهر j شهر i را ملاقات کند یا خیر؟ هر ورودی ساختار می تواند به طور مسقل محاسبه شود. دوم، انتخاب احتمالی شهر بعدی برای ملاقات هر مورچه که به کمک چرخه رولت این کار انجام می شود.

شکل 2: الگوریتم 2 ساخت بخش ASDecisionRule مسیر در روش ترتیبی

ساخت مسیر روی GPU ها

رویکرد سنتی برای ساخت مسیر در حالت موازی این است که مورچه ها برای یافتن بهترین مسیر جستجو انجام می دهند. بنابراین هر گونه موازی سازی ذاتی در سطح مورچه ها وجود دارد. در کودا، هر مورچه به عنوان یک نخ در نظر گرفته می شود و نخ ها به طور مساوی بین بلوک های نخ توزیع شده اند. به منظور بهبود پهنای حافظه هسته، بعضی از ساختارهای داده در حافظه اشتراکی on-chip قرار داده شده اند. لیست select_prob و ملاقات شده ها بهترین کاندید می باشند. حافظه اشتراکی یک منبع محدود در کودا می باشد که در سطح بلوک نخ های کودا تخصیص و به اشتراک گذاشته می شود. در این حالت مورچه ها به طور مستقیم به حافظه اشتراکی دسترسی دارند.

تنظیم سیستم های P برای حل مسئله SAT روی GPUها

مسئله رضایت SAT تعیین می کند که آیا فرمول دودوئی برای فرم نرمال عطفی (CNF) صحیح می باشد یا خیر؟ این مسئله برای چک کردن مدل و تولید کننده تست اتوماتیک برای VLSI مورد استفاده قرار می گیرد. این گونه سیستم ها برای حل مسائل تصمیم گیری مورد استفاده قرار می گیرد. علاوه بر این، محاسبات سیستم P می تواند برای استخراج بهتر تحت این معماری باشد. در این مقاله طریقه بهبود  شبیه ساز سیستم P برای حل مسئله SAT روی GPU ها نشان داده می شود.

شبیه ساز مبنا: سازگار کردن شبیه ساز برای مسئله SAT

به منظور سازگار کردن شبیه ساز برای مسئله SAT از دو هسته کودایی و یک مرحله CPU استفاده می شود: الف: یک هسته که پوسته را تولید می کند و هدف را در درون پوسته ارزیابی می کند. ب: همگام سازی و اتمام مراحل که در هسته تنها گسترش می یابد. ج: مرحله خروجی روی CPU برای یک تکرار سراسری از رفتار سیستم P اجرا می شود. به منظور تضمین موازی سازی در میان پوسته ها یک بلوک نخی کودایی برای هر پوسته اختصاص داده می شود.

شبیه ساز پیشرفته: افزایش موازی سازی

همان طور که در شکل 3 نشان داده شده است الگوریتم 3 یک شبه کد داده چندگانه و برنامه تنها (SPMA) برای شبیه ساز پیشرفته را نشان می دهد. هسته های کودایی که قبلاً وابسته به مرحله نسل بود در این روش در داخل یک هسته تنها گروه بندی شده است. پوسته ها تقسیم بندی شده و ارزیابی اهداف به طور هم زمان انجام می شود.

شکل 3: شبه کد برای شبیه ساز SPMD پیشرفته افزایش موازی سازی

شبیه ساز کاشی (Tiling): استخراج محلی داده ها

Tiling یا کاشی سازی یک تکنیک برای بهبود داده ها به طور محلی در سلسله مراتب حافظه ها می باشد. این شبیه ساز هسته نسل که شامل پیش پردازش بلوک ها (BP) می باشد را تقویت می کند. به طوری که مجموعه ای از پوسته ها به طور جزئی ایجاد شده و در میان اندازه بلوک قرار می گیرد تا مکان حافظه بهبود پیدا کند. این شبیه ساز در شکل 4 نشان داده شده است.

شکل 4: شبیه ساز کاشی کاری شده روی GPU تنها

نتایج:

در جدول 1 زمان اجرا روی سیستم GPU برای هسته انتخاب اطلاعات و همچنین موازی سازی ساخت مسیر برای الگوریتم ACO روی واحد پردازش گرافیکی  Tesla C2050 نشان داده شده است.

جدول 1: زمان اجرا روی سیستم GPU برای هسته و موازی سازی ساخت مسیر برای الگوریتم ACO

در جدول 2 زمان اجرای برای مرحله ساخت مسیر الگوریتم ACO را روی سکوی سخت افزاری مختلف را نشان داده شده است. همچنین، فعال سازی موازی سازی داده روی GPU به تصویر کشیده شده است.

جدول 2: زمان اجرای برای مرحله ساخت مسیر الگوریتم ACO را روی سکوی سخت افزاری مختلف

در جدول 3 زمان اجرا برای SAT روی پلتفرم های سخت افزاری مختلف نشان داده شده است. همچنین، بهترین پیکربندی برای شبیه ساز کاشی در GPU در هر مورد نشان داده شده است. ( منظور از n.a. بدین معنی است که به علت محدودیت حافظه مشترک در دسترس نمی باشد)

جدول 3: مدت زمان اجرا برای SAT روی پلتفرم های سخت افزاری مختلف

در جدول 4 زمان اجرا روی GPU تنها برای مورد ویژه ای از سیستم P که با  2²¹ پوسته ترکیب شده است،  نشان داده شده است.

جدول 4: مدت زمان اجرا روی GPU تنها برای مورد ویژه ای از سیستم P

  [1].  José M. Cecilia · Andy Nisbet · Martyn Amos · José M. García · Manuel Ujaldón,” Enhancing GPU parallelism in nature-inspired  algorithms”, Springer,2012.