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

مقاله و تحقیق تحليل الگوريتم شاخه و قيد موازی آسنكرون در قالب فایل ورد 32 صفحه ای آماده پرینت میباشد.این مقاله مناسب دانشجویان رشته مهندسی کامپیوتر بوده و کامپیوتر های موازی و ویژگی الگوریتم های موازی branch & bound  را به صورت تحلیلی مورد بررسی قرار داده است. در ادامه به خلاصه ای از متون تحقیق میپردازیم تا در صورت نیاز از باکس انتهای صفحه دانلود نمایید.

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

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

تعريف Knowledge:

Redundant knowledge (دانش افزونه) دانشي است كه در گذشته توسط الگوريتم توليد شده ولي از الان به بعد هرگز مورد استفاده الگوريتم نخواهد بود. مانند حل ممكن جديدي كه منجر به باطل شدن حل ممكن قبلي مي‌شود. از آنجائيكه دانش افزونه هرگز مورد استفاده مجدد الگوريتم قرار نمي‌گيرد، نيازي به نگهداري آن نيست. بر اساس ويژگيهاي كامل يك الگوريتم b&b ثابت مي‌شود بخشي از دانش توليد شده، افزونه است.Valid Knowledge (دانش معتبر) دانشي است كه الگوريتم هنوز نتوانسته تصميم بگيرد كه اين دانش افزونه است.

Algorithm
Algorithm

الگوريتم شاخه و قيد موازي: (Parallel B&B Algorithms):

عده‌اي الگوريتمها را در دو سطح low و high دسته‌بندي مي‌كنند و عده‌اي الگوريتمها را بصورت سنكرون و آسنكرون تقسيم‌بندي مي‌كنند. (low معادل با سنكرون و high معادل با آسنكرون) الگوريتمها در دو سطح lowو high مي‌توانند موازي شوندموازي سازي در سطح low: الگوريتم خطي بعنوان نقطه شروع داده مي‌شود و فقط بخشي از الگوريتم موازي مي‌شود، بطوريكه محاوره بين بخش موازي و ديگر بخشهاي الگوريتم تغيير نمي‌كند در   الگوريتم های B&B «محاسبه حد پايين»، «انتخاب زير مسئله براي انشعاب بعدي» يا «كاربرد قانون حذف» مي‌تواند توسط چندين پروسس بطور موازي انجام شود.از آنجائيكه محاوره بين بخشهاي مختلف الگوريتم تغيير نمي كند، موازي سازي در سطح پايين در كل الگوريتم تاثيري ندارد. در كل الگوريتم موازي توليد شده، رفتار الگوريتم خطي اصلي را بازسازي مي‌كند. يعني در الگوريتم B&B از همان زير مسئله‌ها و به همان ترتيب انشعاب خواهد گرفت بنابراین  نياز به مطالعه كل الگوريتم موازي نيست بلكه فقط كافيست آن بخش كه واقعاً موازي است را مطالعه كنيم. يكبار كه اثر موازي سازي شناخته شود، رفتار الگوريتم موازي كاملاً قابل پيشگويي خواهد بود.

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

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

هر بخش از الگوريتم كه گامهاي زيادي براي اجرا داشته باشد يك كانديد طبيعي براي موازي سازي است. كانديداهاي ممكن عبارتند از:

1- lower bound calculation (محاسبه حد پايين): بعضي از الگوريتمهاي B&B از تابعهاي حد پاييني استفاده مي‌كنند كه محاسبه آنها دشوار است. وابستگي به يك تابع حد پايين استفاده شده خاص موازي سازي در اين بخش از الگوريتم را نشان مي‌دهد. اگرچه الگوريتمهاي محاسبه حد پايين بطور ذاتي خطي هستند مثل الگوريتمهاي greedy.

2- Selection (انتخاب): در بعضي از مراحل اجرا تعداد زير مسئله‌ها در مجموعه فعال ممكن است خيلي زياد باشد، لذا انتخاب زير مسئله بعدي براي انشعاب و استخراج آن زير مسئله مستلزم مقدار كار زيادي است كه اين كار مي‌تواند بطور موازي انجام شود.

3- Elimination (حذف): بررسي اينكه bound يك زير مسئله همچنان بهتر از حل ممكن شناخته شده تا كنون است يا نه ساده است. با اينحال بكار بردن dominance test و بررسي اينكه يك زير مسئله مي‌تواند يك حل ممكن توليد كند خيلي دشوار است. زيرا dominance test مستلزم مقايسه زير مسئله فعلي با تمام زير مسئله‌هايي كه توليد شده‌اند ولي تا كنون تحت سلطه قرار نگرفته‌اند مي‌باشد. حال اين امكان وجود دارد كه (بخشي از) اين تستها بطور موازي انجام شوند.

4- Branching (انشعاب) : بجاي انتخاب و انشعاب يك زير مسئله در يك زمان مي‌توان چندين زيرمسئله را يكبار انتخاب كرد و بطور موازي آنها را انشعاب داد. براي آنكه عنصر پردازشي كارايي بيشتري داشته باشد، تعداد زير مسئله‌هاي فعال بايد حداقل برابر با تعداد عناصر پردازشي باشد.

سطح موازي سازي كه از طريق روش 4 توليد مي‌شود بالاتر از سطح موازي سازي توليد شده توسط 1 و 2و 3 است. يعني روش 4 موازي سازي در سطح high است.

كاري كه در حين انشعاب از چندين زيرمسئله بطور موازي انجام مي‌شود مي‌تواند متفاوت از كاري باشد كه در اجراي الگوريتم خطي مشابه انجام مي‌شود، بعبارت ديگر درخت جستجوي توليد شده مي‌تواند متفاوت باشد، چون بعضي از زيرمسئله‌ها كه بطور موازي انشعاب يافته‌اند ممكن است در حالت خطي اصلاً حذف مي‌شوند يا هرگز توليد نمي‌شوند. انشعاب چندين زير مسئله بطور موازي اساساً منجر به تغيير استراتژي جستجو مي‌شود. به دليل اينكه چندين subproblem بطور موازي در حال انشعاب دادن هستند. دانش بدست آمده در يك نقطه از اجرا متفاوت از دانش بدست آمده در حالت خطي است، لذا اين مسئله مي‌تواند بر روي انتخاب زير مسئله‌ها براي انشعاب بعدي تاثير بگذارد. نتايج اين تغيير كاملاً واضح نيست، اما انواع آنوماليها رخ مي‌دهد و تسريع‌ها و كاهش‌هاي بي‌دليل ايجاد مي‌شود.نتيجه الگوريتم موازي سنكرون قطبي است. به جهت اين همزماني، دانش بدست آمده همواره از روش يكساني Combine مي‌شود. بنابراين اجراهاي متوالي از الگوريتم همواره منجر به جواب مشابهي مي‌شود.

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

  • خلاصه و معرفی كامپيوترهاي موازي (Parallel computers)
  • الگوريتمهاي موازي (Parallel Algorithm)
  • شاخه و قيد (Branch and Bound)
  • الگوريتم موازي شاخه و قيد آسنكرون
  • پارامترهاي الگوريتمهاي شاخه و قيد موازي آسنكرون
  • بررسی Knowledge sharing
  • بررسی  Knowledge use
مطلب بالا چکیده‌ای از تحقیق و پژوهش اصلی میباشد جهت تهیه نسخه کامل آن از باکس زیر اقدام به خرید و دانلود نمایید
لینک خرید پژوهش مقاله تحليل الگوريتم شاخه و قيد موازی آسنكرون:
تحویل فوری و خودکار فایل با لینک مستقیم بعد از پرداخت
تعداد صفحه: 32
قالب: فایل word
توضیحات: فهرست و منبع ندارد

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *