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

در اين مقاله توضيحي درباره كامپيوترهاي موازي مي‌دهيم و بعد الگوريتمهاي موازي را بررسي مي‌كنيم. ويژگيهاي الگوريتم 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 ها بطور موازي وجود داشته باشد، قدرت محاسبه يك كامپيوتر موازي نامحدود است. اما در عمل اين دو شرط بطور كامل برقرار نمي‌شوند