تحليل الگوريتم شاخه و قيد موازي آسنكرون

Asynchronous Parallel Branch and Bound Algorithm

 1- خلاصه:

در اين مقاله توضيحي درباره كامپيوترهاي موازي مي‌دهيم و بعد الگوريتمهاي موازي را بررسي مي‌كنيم. ويژگيهاي الگوريتم branch & bound را بيان مي‌كنيم و الگوريتمهاي b&b موازي را ارائه مي‌دهيم و دسته‌اي از الگوريتمهاي b&b آسنكرون براي اجرا روي سيستم MIMD را توسعه مي‌دهيم. سپس اين الگوريتم را كه توسط عناصر پردازشي ناهمگن اجرا شده است بررسي مي‌كنيم.

نمادهاي perfect parallel و achieved effiency را كه بطور تجربي معيار مناسبي براي موازي‌سازي است معرفي مي‌كنيم زيرا نمادهاي قبلي speed up (تسريع) و efficiency (كارايي) توانايي كامل را براي اجراي واقعي الگوريتم موازي آسنكرون نداشتند. و نيز شرايي را فراهم كرديم كه از آنوماليهايي كه به جهت موازي‌سازي و آسنكرون بودن و يا عدم قطعيت باعث كاهش كارايي الگوريتم شده بود، جلوگيري كند.

2- معرفي:

هميشه نياز به كامپيوترهاي قدرتمند وجود داشته است. در مدل سنتي محاسبات، يك عنصر پردازشي منحصر تمام taskها را بصورت خطي (Seqventia) انجام ميدهد. به جهت اجراي يك دستورالعمل داده بايستي از محل يك كامپيوتر به محل ديگري منتقل مي‌شد، لذا نياز هب كامپيوترهاي قدرتمند اهميت روز افزون پيدا كرد. يك مدل جديد از محاسبات توسعه داده شد، كه در اين مدل جديد چندين عنصر پردازشي در اجراي يك task واحد با هم همكاري مي‌كنند. ايده اصل اين مدل بر اساس تقسيم يك task به subtask‌هاي مستقل از يكديگر است كه مي‌توانند هر كدام بصورت parallel (موازي) اجرا شوند. اين نوع از كامپيوتر را كامپيوتر موازي گويند.

تا زمانيكه اين امكان وجود داشته باشد كه يك task را به زير taskهايي تقسيم كنيم كه اندازه بزرگترين زير task همچنان به گونه‌اي باشد كه باز هم بتوان آنرا كاهش داد و البته تا زمانيكه عناصر پردازشي كافي براي اجراي اين sub task ها بطور موازي وجود داشته باشد، قدرت محاسبه يك كامپيوتر موازي نامحدود است. اما در عمل اين دو شرط بطور كامل برقرار نمي‌شوند:

اولاً: اين امكان وجود ندارد كه هر taskي را بطور دلخواه به تعدادي زير task‌هاي مستقل تقسيم كنيم. چون همواره تعدادي زير task هاي وابسته وجود دارد كه بايستي بطور خطي اجرا شوند. از اينرو زمان مورد نياز براي اجراي يك task بطور موازي يك حد پايين دارد.

دوماً: هر كامپيوتر موازي كه عملاً ساخته مي‌شود شامل تعداد معيني عناصر پردازشي (Processing element) است. به محض آنكه تعداد taskها فراتر از تعداد عناصر پردازشي برود، بعضي از sub task ها بايستي بصورت خطي اجرا شوند و بعنوان يك فاكتور ثابت در تسريع كامپيوتر موازي تصور مي‌شود.

الگوريتمهاي B&B مسائل بهينه سازي گسسته را به روش تقسيم فضاي حالت حل مي‌كنند. در تمام اين مقاله فرض بر اين است كه تمام مسائل بهينه سازي مسائل مي‌نيمم كردن هستند و منظور از حل يك مسئله پيدا كردن يك حل ممكن با مقدار مي‌نيمم است. اگر چندين حل وجود داشته باشد، مهم نيست كداميك از آنها پيدا شده.

الگوريتم B&B يك مسئله را به زير مسئله‌هاي كوچكتر بوسيله تقسيم فضاي حالت به زير فضاهاي (Subspace) كوچكتر، تجزيه مي‌كند. هر زير مسئله توليد شده يا حل است و يا ثابت مي‌شود كه به حل بهينه براي مسئله اصلي (Original) نمي‌انجامد و حذف مي‌شود. اگر براي يك زير مسئله هيچ كدام از اين دو امكان بلافاصله استنباط نشود، آن زير مسئله به زيرمسئله‌هاي كوچكتر دوباره تجزيه مي‌شود. اين پروسه آنقدر ادامه پيدا مي‌كند تا تمام زير مسئله‌هاي توليد شده يا حل شوند يا حذف شوند.

در الگوريتمهاي B&B كار انجام شده در حين اجرا به شدت تحت تاثير نمونه مسئله خاص قرار مي‌گيرد. بدون انجام دادن اجراي واقعي الگوريتم اين امكان وجود ندارد كه تخمين درستي از كار انجام شده بدست آورد. علاوه برآن، روشي كه كار بايد سازمان‌دهي شود بر روي كار انجام شده تاثير مي‌گذارد. هر گامي كه در اجراي الگوريتم b&b ي موازي بطور موفقيت‌آميزي انجام مي‌شود و البته به دانشي است كه تاكنون بدست آورده. لذا استفاده از استراتژي جستجوي متفاوت يا انشعاب دادن چندين زير مسئله بطور موازي باعث بدست آمدن دانشي متفاوت مي‌شود پس مي‌توان با ترتيب متفاوتي زير مسئله‌ها را انشعاب داد.

دقت كنيد كه در يك بدل محاسبه خطي افزايش قدرت محاسبه فقط بر روي تسريع الگوريتم اثر مي‌كند وگرنه كار انجام شده همچنان يكسان است.

با اين حال اگر قدرت محاسبه يك كامپيوتر موازي با اضافه كردن عناصر پردازشي اضافه افزايش پيدا كند. اجراي الگوريتم b&b بطور آشكاري تغيير مي‌كند (به عبارت ديگر ترتيبي كه در آن زير برنامه‌ها انشعاب پيدا مي‌كنند تغيير مي‌كند). بنابراين حل مسائل بهينه‌سازي گسسته سرسع بوسيله يك كامپيوتر موازي نه تنها باعث افزايش قدرت محاسبه كامپيوتر موازي شده است بلكه باعث گسترش الگوريتمهاي موازي نيز گشته است.

فرمت : قابل ویرایش | WORD | صفحات : /37 – منابع ندارد

*************************************

نکته : فایل فوق قابل ویرایش می باشد