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

مقاله و تحقیق تحلیل الگوریتم شاخه و قید موازی آسنکرون در قالب فایل ورد ۳۲ صفحه ای آماده پرینت میباشد.این مقاله مناسب دانشجویان رشته مهندسی کامپیوتر بوده و کامپیوتر های موازی و ویژگی الگوریتم های موازی 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 چند تا تکرار از حلقه اصلی می‌تواند بصورت موازی انجام شود. چون تکرارهای این حلقه نسبتاً مستقل از یکدیگر هستند، ترتیبی که این تکرارها مجدداً مرتب می‌شوند یا انجام چندین تکرار بطور موازی در صحت الگوریتم تاثیری ندارد.

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

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

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

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

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

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

سطح موازی سازی که از طریق روش ۴ تولید می‌شود بالاتر از سطح موازی سازی تولید شده توسط ۱ و ۲و ۳ است. یعنی روش ۴ موازی سازی در سطح high است.

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

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

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

پاسخ دهید

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