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