مقاله الگوریتم مرتب سازی انتخاب موازی در GPU ها با استفاده از جستجوی دودویی باینریA Parallel Selection Sorting Algorithm on GPUs Using Binary Search

چکیده فارسی :

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

کلید واژه ­ها: مرتب­ سازی انتخابی، مرتب­ سازی پایه­ای، جستجوی دودویی، GPUها

چکیده انگلیسی:

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.

Keywords-Selection sort, Radix sort, Binary search,GPUs