This paper describes a hybrid sorting which is the combination of radix sort and selection sort on graphic processing unit (GPU). The proposed algorithm is based on “Split and Concurrent Selection” (SCS) strategy. First, the data sequence is split in several pieces that are sorted in parallel using Radix sort. After that it applies parallel selection sort to obtain the final sorted sequence. Parallel selection sort finds the correct position of each elements of a data sequence and then copy the elements of a data sequence to corresponding position to obtain the final sorted data sequence. This paper analyses the computational complexity of proposed parallel sorting algorithm and compares it with other existing algorithms. It is implemented using CUDA 5.0 and results are evaluated on Tesla C2075 GPU. Experimental results of proposed algorithm are compared with results of best sequential sorting algorithm and odd- even merge sort based parallel sorting algorithm. Proposed algorithm shows up to 50 times speed up as compare to serial and two fold speedup as compare to parallel algorithm

چکیده

این مقاله مرتب ­سازی ترکیبی را شرح می­ دهد که ترکیبی از مرتب کردن پایه ­ای و انتخابی در واحد پردازش گرافیکی (GPU) است. الگوریتم پیشنهادی بر اساس استراتژی "تقسیم و انتخاب همزمان" (SCS) است. اول، ترتیب داده­ ها به چندین بخش تقسیم می ­شود که بطور موازی با استفاده از مرتب سازی پایه ­ای مرتب شده ­اند. سپس مرتب ­سازی انتخابی موازی برای به دست آوردن دنباله مرتب شده نهایی اعمال می ­شود. مرتب­ سازی انتخاب موازی، موقعیت درست هر یک از عناصر توالی داده را می یابد و عناصر یک توالی داده را به موقعیت متناظر کپی می­ کند تا توالی داده مرتب شده نهایی را به دست آورد. این مقاله، پیچیدگی محاسباتی الگوریتم مرتب­ سازی موازی پیشنهادی را تجزیه و تحلیل کرده و آن را با دیگر الگوریتم­ های موجود مقایسه می ­کند. این مقایسه با استفاده از CUDA 5.0 پیاده سازی شده و نتایج به دست آمده در تسلا GPU C2075 مورد بررسی قرار گرفته است. نتایج تجربی، الگوریتم پیشنهادی را با نتایج حاصل از بهترین الگوریتم مرتب ­سازی متوالی و ادغام مرتب شده زوج- فرد و الگوریتم مرتب ­سازی موازی مقایسه می­ کند. الگوریتم پیشنهادی، سرعت 50 برابر نسبت به الگوریتم سریالی و سرعت دو برابر نسبت به الگوریتم موازی را نشان می ­دهد.

1-مقدمه                                                              

مرتب­ سازی عناصر یک توالی داده، یکی از مشکلات الگوریتمی است که به طور گسترده مورد مطالعه قرار گرفته است. مرتب ­سازی به معنای مرتب نمودن سیستماتیک عناصر توالی داده در گروه­ها و یا جداسازی با توجه به نوع آنها است. مرتب ­سازی یک کار بسیار رایج است که در بسیاری از برنامه ­های زمان واقعی مانند سناریوهای گرافیک زمان واقعی، مرتب ­سازی بر نمودارها [1]، سیستم های مدیریت پایگاه داده [2]، پردازش تصویر و شبیه­ سازی عددی مورد استفاده قرار می­ گیرد...