بهینه سازی الگوریتم مرتب سازی موازی با کاهش تعداد پردازنده در سیستم های SIMD

موازی سازی یکی از راهکارهای کاهش زمان اجرا برنامه ها می باشد. مرتب سازی یکی از عملیات مهم و مورد استفاده سیستم های مختلف است به طوری که عملکرد صحیح بسیاری از الگوریتم ها و عملیات وابسته به مرتب بودن داده ها می باشد. الگوریتم SRCW SORT عمل مرتب سازی N عنصر را در زمان (1)O بر روی کامپیوترهای SIMD با تعداد 2/n-2/n پردازنده انجام می دهد. در این مقاله با ارائه راهکاری به وسیله تقسیم کردن رشته ورودی بر اساس عنصر لولا به دو رشته کوچکتر، تعداد پردازنده های مورد استفاده جهت انجام عملیات مرتب سازی N عنصر را در زمان (1) O در بهترین حالت به 4/n-8/n کاهش یافته است. در این راهکار بهترین حالت زمانی است که عنصر لولا عنصر میانه باشد و بدترین حالت زمانی است که عنصر لولا مینیمم باشد. نتایج حاصل از ارزیابی الگوریتم پیشنهادی با روش های دیگر روی مجموعه داده ها و تعداد پردازنده نشان می دهد که الگوریتم پیشنهادی نسبت به روش های دیگر تعداد پردازنده های کمتری را جهت انجام عمل مرتب سازی به هنگام اجرا استفاده می کند.

کلیدواژه ها:

الگوریتم موازی ، تعداد پردازنده ، CRCW ، کامپیوترهای SIMD