رفع مشکلات بهینه‌سازی بسیار بزرگ با نوعی الگوریتم تکاملی موازی در CPU و GPU

رفع مشکلات بهینه‌سازی بسیار بزرگ با نوعی الگوریتم تکاملی موازی در CPU و GPU


اگر به خاطر داشته باشید در قسمت پیشین مقاله به معرفی مشکلات موجود در حوزه مورد بحث و معرفی مسائل OneMax و الگوریتم‌های تکاملی موازی پرداختیم. بر همین اساس به‌منظور پیشبرد نوشته و اتمام آن، بخش فعلی از مطلب پیرامون نحوه پیاده‌سازی الگوریتم‌های طراحی شده و بررسی نتایج آن متمرکز گشته است.

پلتفرم‌های نوین چندهسته‌ای

این بخش به‌صورت خلاصه به معرفی پلتفرم‌های محاسباتی چند هسته‌ای مورد استفاده در این نوشته می‌پردازد.

واحدهای پردازنده مرکزی چند هسته‌ای

در یک پردازنده چندهسته‌ای، تعداد چندین واحد پردازشگر مجزا و غیر وابسته (هسته) به‌منظور اجرای دستورالعمل‌های گوناگون حاضر می‌باشند. اجرای دستورات مختلف در سرتاسر چندین هسته به‌صورت هم‌زمان با استفاده از اعمال تکنیک‌های محاسباتی موازی، افزایش راندمان پردازشی کلی را امکان‌پذیر می‌نماید که این مهم، به‌خصوص در کاربرد نرم‌افزارهای نیازمند سرعت بالا و وابسته به واحد پردازنده مرکزی می‌تواند مفید واقع شود. امروزه، پردازنده‌های مرکزی چند هسته‌ای به‌صورت گسترده‌ای در حوزه‌های مختلف جهت حل مسائل پیچیده به‌کار گرفته می‌شوند. فناوری‌های مدرن نظیر Opteron Magny-Course (استفاده شده در تجزیه و تحلیل تجربی این مقاله) امکان یکپارچه‌سازی و ترکیب تعداد بیش از 24 هسته در یک پردازشگر/رایانه را فراهم می‌آورد.

محاسبات واحد شتاب‌دهنده گرافیکی (GPU)

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

معماری نرم‌افزاری کودا امکان مدیریت تراشه شتاب‌دهنده گرافیکی به‌عنوان نوعی دستگاه محاسباتی موازی با توانایی اجرای حجم عظیمی از دستورالعمل‌های متفاوت به‌صورت موازی را میسر می‌نماید. دستورالعملی ویژه و به‌خصوص که باید به دفعات متعدد در قالب داده‌های گوناگون مورد اجرا قرار گیرد می‌تواند در بستر یک تابع وابسته به GPU با استفاده از رشته‌های پردازشی مختلف ایزوله شود. تابع مربوطه با استفاده از دسته‌ای از دستورالعمل‌های گوناگون کامپایل شده و برنامه خروجی (به نام کرنل) در تراشه GPU بارگذاری می‌گردد. تراشه شتاب‌دهنده گرافیکی از حافظه اصلی دینامیک (DRAM) خود برخوردار بوده و داده‌ها از حافظه GPU به حافظه اصلی سیستم میزبان (و بالعکس) با استفاده از توابع بهینه فراخوانی گشته از رابط برنامه‌نویسی کودا (CUDA API) منتقل می‌گردند.

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

الگوریتم ژنتیک فشرده (cGA) در CPU و GPU

این بخش به ارائه جزئیات یکپارچه‌سازی الگوریتم ژنتیک فشرده موازی در واحدهای پردازنده مرکزی و گرافیکی می‌پردازد.

تجزیه و تحلیل عملکرد الگوریتم cGA در قالب مسئله OneMax

مقصود اصلی از تجزیه و تحلیل تجربی، مطالعه توانایی‌های موجود جهت حل مسائل بهینه‌سازی بسیار بزرگ با استفاده از الگوریتم cGA می‌باشد. بنابراین، در ابتدا ما به اجرای یک آنالیز عملکردی برای شناسایی بهترین عملگر با توجه به زمان کلی اجرا اقدام کردیم. تجزیه و تحلیل مربوطه با استفاده از ابزار gprof برای نمایه‌های ++C/C در واحد پردازنده مرکزی و رابط برنامه‌نویسی کودا Event در تراشه شتاب‌دهنده گرافیکی انجام شده است. به‌عنوان مثال، عکس زیر خلاصه‌ای از نتایج مشارکت توابع اصلی الگوریتم cGA هنگام حل یک مسئله مبتنی بر تعداد یک میلیون متغیر با استفاده از واحدهای پردازنده مرکزی و گرافیکی را نمایانگر می‌باشد.

موازی

نتایج موجود در عکس فوق حاکی از آن‌اند که عملگر تولید اعداد به‌صورت تصادفی تابعی است که در مقایسه با دیگر موارد موجود (با توجه به زمان اجرای کلی) از ارجحیت چشمگیر بیشتری برخوردار می‌باشد.

الگوریتم cGA به تعداد  عدد تصادفی برای تولید اشخاص نمونه‌برداری شده در هر نسل نیازمند می‌باشد، بنابراین برای اجرای یک بازنما (در حدود 50 هزار نسل) و  متغیر، 100 میلیارد فراخوان به عملگر تولید اعداد تصادفی الزامی به شمار می‌رود.

جزئیات تعبیه‌سازی

به‌منظور کاهش مدت زمان مورد نیاز جهت انجام فرآیند شبیه‌سازی، پیشنهادات مطرح شده برای تعبیه‌سازی الگوریتم‌های تکاملی بهینه در عمل، تصمیمات زیر مورد اتخاذ قرار گرفته‌اند:

ازآنجایی‌که فرآیند تولید اعداد تصادفی در نیازمندی‌های محاسباتی الگوریتم cGA نقش پررنگی را ایفا می‌کند، تصمیم به استفاده از تولیدکننده اعداد Mersenne Twister گرفته شده است که در زمینه فراهم آوردن دوره زمانی بسیار بزرگ و بهبود چشمگیر در میزان بهره‌وری در مقایسه با تولیدکننده تصادفی اعداد سنتی تأثیرات فراوانی را به خود اختصاص می‌دهد.

استفاده از حافظه دینامیک جهت نگهداری متغیرهای بزرگ در الگوریتم cGA (بردار احتمال و دو شخص نمونه‌برداری شده) اجتناب شده است؛

استفاده از نوع متغیر char جهت نمایش متغیرهای باینری نیز اجتناب شده است؛

تعداد دفعات فراخوانی توابع نیز با کاهش همراه گشته‌اند؛

به‌منظور جلوگیری از عملیات گران قیمت و بهینه‌سازی هزینه، چندین تغییر دیگر در تولیدکننده اعداد Mersenne Twister نیز اعمال گشتند.

نمونه موازی

عکس زیر یک نمای کلی از نمونه موازی در تعبیه‌سازی الگوریتم cGA در واحدهای پردازنده مرکزی و تراشه شتاب‌دهنده گرافیکی را نشان‌گر است. مدل موازی ذیل از یک استراتژی تجزیه دامنه تبعیت می‌کند که بر طبق آن، دامنه مسئله (منظور متغیرها) به‌منظور پردازش به‌صورت موازی به قطعه‌های مساوی تقسیم‌بندی می‌شود. ما یک طرح تعبیه‌سازی چند رشته‌ای برای الگوریتم cGA را ارائه دادیم که از منابع محاسباتی در دسترس برای اجرای رشته‌های موازی موجود در واحدهای پردازنده مرکزی و گرافیکی جهت انجام عملیان گزاف در الگوریتم cGA به نفع خود بهره می‌برد:

1) قدم تکامل، که به اجرای نمونه مدل احتمال، تولید اشخاص داوطلب  و  و ارزیابی جزئی میزان سازگاری قطعات پردازش شده توسط هر رشته؛

2) به‌روزرسانی بردار احتمال، که به محاسبه مقادیر بردار احتمال با توجه به فرد پیروز در مرحله اعمال الگوریتم مسابقه می‌پردازد. همگام‌سازی داخلی به‌منظور محاسبه کلی درجه سازگاری راه‌حل‌های نهایی از راه‌حل‌های جزئی مورد نیاز می‌باشد.

موازی

تعبیه‌سازی واحد پردازنده مرکزی

یک مدل سنتی ارباب-برده برای الگوریتم‌های تکاملی مورد اعمال قرار گرفته است که بر طبق آن، یک فرآیند ارباب مسئولیت ساخت، مدیریت و همگام‌سازی انباره رشته‌ها را بر عهده دارد که به انجام اقدامات نمونه‌برداری از مدل و تولید اشخاص نمونه‌برداری شده مبادرت می‌ورزد. پس از همگام‌سازی مربوطه جهت مقایسه میزان سازگاری اشخاص مختلف با یکدیگر، هر کدام از رشته‌های موجود در انباره به به‌روزرسانی بردار احتمال اقدام می‌نمایند. پشتیبانی رشته توسط کتابخانه استاندارد POSIX در زبان برنامه‌نویسی C (ptthread) پیاده‌سازی شده است.

یکپارچه‌سازی واحد پردازنده مرکزی از روشی جهت پشتیبانی از بسته‌بندی و از حالت بسته‌بندی خارج نمودن اشخاص مورد آزمایش پشتیبانی نمی‌کند، زیرا میزان حافظه در دسترس جهت نگهداری بردار احتمال و دو فرد نمونه‌برداری شده برای ابعاد بیش از یک میلیون متغیر کافی است.

تعبیه‌سازی تراشه شتاب‌دهنده گرافیکی

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

قدم ابتدایی در الگوریتم، مقداردهی اولیه دستگاه گرافیکی است. این مقداردهی چند دقیقه به طول می‌انجامد، اما تنها یک مرتبه در طول اجرای الگوریتم صورت می‌پذیرد. پس از مقداردهی اولیه دستگاه‌ها، الگوی یک رشته CPU بر هر دستگاه گرافیکی راه‌اندازی می‌گردد. الگوریتم زیر کدهای دستور هر رشته پردازنده مرکزی از الگوریتم cGA برای تراشه GPU را نمایانگر می‌باشد.

موازی

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

تجزیه و تحلیل تجربی

این بخش به توصیف تجزیه و تحلیل آماری هنگام حل مسائل OneMax و OneMax دارای نویز (مقدار نویز برابر با 0.5 درصد) توسط الگوریتم cGA در واحدهای پردازنده مرکزی و گرافیکی می‌پردازد.

پلتفرم توسعه و اجرا

الگوریتم cGA برای واحد پردازنده مرکزی توسط زبان برنامه‌نویسی C و با استفاده از کتابخانه ptthread پیاده‌سازی و به‌وسیله پردازشگر Opteron 3172 Magny-Cours با برخورداری از تعداد 24 هسته مرکزی در فرکانس 2.1 گیگاهرتز، 24 گیگابایت حافظه اصلی و سیستم‌عامل لینوکس CentOS به اجرا در آمده است. علاوه بر آن الگوریتم cGA برای تراشه شتاب‌دهنده گرافیکی نیز توسط نسخه سوم معماری کودا (CUDA v3.0) و رابط برنامه‌نویسی OpenMP برای مدیریت رشته‌ها پیاده‌سازی شده و به‌وسیله یک واحد پردازنده مرکزی هشته‌ای Xeon در فرکانس 2.33 گیگاهرتز، 8 گیگابایت حافظه اصلی و چهار کارت گرافیک Tesla C1060 به اجرا در آمده است. زیرساخت محاسباتی مورد استفاده در تجزیه و تحلیل آماری از جانب کمپانی Cluster FING فراهم آورده شده است.

نتایج و بررسی

جدول زیر نتایج گزارشات مربوطه هنگام حل مسائل OneMax و OneMax دارای نویز به‌وسیله الگوریتم cGA را در بطن خود جای داده است. در هنگام استفاده از واحد پردازنده مرکزی، نمونه‌های مبتنی بر تعداد 1، 8 و 24 میلیون متغیر بر طبق نتایج حل شده‌اند (رایانه چندهسته‌ای مورد استفاده امکان گسترش مقیاس جهت حل مسائل بزرگ‌تر را فراهم نمی‌آورد). در هنگام استفاده از تراشه شتاب‌دهنده گرافیکی، نمونه‌های مبتنی بر تعداد 1، 8 و 32 میلیون، و نمونه‌ای بسیار عظیم با برخورداری از بیش از 1 میلیارد متغیر بر طبق نتایج حل شده‌اند.

موازی

نتایج گردآوری شده در جدول فوق حاکی از آن‌اند که الگوریتم cGA پیاده‌سازی شده در واحد پردازنده مرکزی قادر به حل مسائل مبتنی بر بیش از 8 میلیون متغیر به‌صورت بهینه می‌باشد، اما میزان بهره‌وری برای مسائل 24 میلیون متغیره به طرز چشمگیری کاهش پیدا می‌کند. از طرفی دیگر، پیاده‌سازی تراشه شتاب‌دهنده گرافیکی (به‌خصوص نسخه ناهمگام) جهت کسب نتایج مشابه با نسخه وابسته به واحد پردازنده مرکزی نیازمند مدت زمان اجرای کمتری بوده و علاوه بر آن امکان گسترش مقیاس جهت حل نمونه مسائل بسیار بزرگ را نیز امکان‌پذیر می‌نماید. پیاده‌سازی الگوریتم cGA در سه حالت مختلف رفتار بسیار قدرتمندی را از خود بروز می‌دهند: نتایج در هنگام حل مسئله OneMax دارای نویز از تفاوت‌های چشمگیری نسبت به هم برخوردار نمی‌باشند.

تجزیه و تحلیل‌های تجربی نشان دادند که الگوریتم cGA  به‌منظور حل بهینه مسائل بهینه‌سازی بزرگ، به دلیل الگوی تکامل بسیار اندک آن بهترین انتخاب به شمار نمی‌رود. الگوریتم cGA  جهت دستیابی به مقدار میانگین سازگاری 66.8 درصد جهت حل بزرگ‌ترین نمونه مسئله مربوطه نیازمند تعداد 100 هزار نسل مختلف بود. اگرچه تعبیه‌سازی‌های تراشه شتاب‌دهنده گرافیکی پیشنهادی در این نوشته قادر به اجرای تعداد نسول نامبرده با درصد بهینگی قابل قبولی هستند که امکان اجرای تعداد 20 عملیات مبتنی بر یک میلیون بیت بر یک دقیقه را فراهم می‌آورند.

تصاویر زیر نتایج مقایسه‌ای تجزیه و تحلیل پیاده‌سازی موازی الگوریتم cGA در واحد پردازنده مرکزی و تراشه شتاب‌دهنده گرافیکی را نمایانگر می‌باشند.

نتیجه‌گیری و اقدامات آینده

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

موازی

تعداد سه نسخه موازی مختلف از الگوریتم تکاملی تحت پیاده‌سازی قرار گرفته بودند: الگوریتم cGA همگام در CPU و GPU و یک نسخه ناهمگام در تراشه شتاب‌دهنده گرافیکی (قابل استفاده تنها برای مسائل بهینه‌سازی تفکیک‌پذیر).

موازی

تجزیه و تحلیل‌های تجربی نشان دادند که پیاده‌سازی الگوریتم cGA مبتنی بر تراشه شتاب‌دهنده گرافیکی در هنگام حل مسائل گوناگون با برخورداری از تعداد بیش از 8 میلیون متغیر موفق به دستیابی به بهترین نتیجه خروجی و میزان بهره‌وری گردیده است. این حقیقت نمایانگر آن می‌باشد که زیرساخت‌های گرافیکی چند هسته‌ای جدید و نوین در زمینه فراهم آوردن پلتفرمی قابل اتکا جهت تعبیه‌سازی الگوریتم‌های تکاملی بهینه برای حل مسائل بهینه‌سازی بسیار بزرگ از پتانسیل بالایی برخوردار می‌باشند.

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

جهت مطالعه بخش اول مقاله به لینک زیر مراجعه فرمایید:

“رفع مشکلات بهینه‌سازی بسیار بزرگ با نوعی الگوریتم تکاملی موازی در CPU و GPU – بخش اول”

پست های مرتبط

دیدگاه خود را بنویسید