مقاله و ترجمه مرتب سازی ادغامی موازی با تعادل بار در کامپیوترهای موازی با حافظه توزیع شده - ارائه درس الگوریتمهای موازی ارشد
مقدمه
مرتب سازی یکی از الگوریتمهای محاسباتی در بسیاری از علوم و کاربردهای مهندسی میباشد. بسیاری از الگوریتم های مرتب سازی ترتیبی با K ورودی دارای مرتبه ی زمانی O(N logN) میباشد. چند مورد از الگوریتمهای مرتب سازی موازی مثل بایتونیک سورتر[1,7]، , radix sort[8, 11] با کمترین زمان اجرا طراحی شده اند.مرتب سازی موازی اغلب نیازمند تعداد ثابتی از تبادل داده و عملیات مرتب سازی میباشد. کاهش زمان اجزا وابسته به تعداد پردازنده ها میباشد. از آنجایی که زمان به تعداد داده های هر پردازنده وابسته هست، در این حالت تعادل بار مهم میباشد. علاوه بر این ، اگر چه هزینه ارتباطی بین پردازنه های داخلی در سیستم های با حافظه مشترک ارزان نیست ، تعداد داده های رد و بدل شده و فرکانسهای ارتباطی تاثیر بسزایی در زمان اجرای کل دارند. مرتب سازی ادعامی غالبا در بسیاری از برنامه های کاربردی مورد استفاده قرار میگیرد. مرتب سازی ادغامی موازی بروی مدل های PRAM دارای زمان اجرای سریع با مرتبه O(log N) یا N ورودی و با استفاده از N پردازنده میباشد[2]. بنا براین سیست های با حافظه مشترک بر اساس مرتب سازی ادغامی موازی، کند بوده؛ زیرا به مرتب سازی محلی با تعداد تکرار ثابت ادغام نیاز دارد که شامل ارتباط طولانی ای میباشد.
فهرست مطالب :
مرتب سازی ادغامی موازی با تعادل بار در کامپیوترهای موازی با حافظه توزیع شده
مقدمه
مرتب سازی ادغام موازی : معمولی
مرتب سازی ادغام موازی با تعادل بار
تجزیه و تحلیل عملکرد
نتایج آزمایشات
نتیجه گیری