Comparison of Hybrid Sorting Algorithms Implemented on Different Parallel Hardware Platforms

Dominik Zurek; Marcin Pietron; Maciej Wielgosz; Kazimierz Wiatr

doi:10.7494/csci.2013.14.4.679

Authors

Dominik Zurek
Marcin Pietron
Maciej Wielgosz
Kazimierz Wiatr

DOI:

https://doi.org/10.7494/csci.2013.14.4.679

Keywords:

parallel algorithms, GPU, OpenMP, CUDA, sorting networks, merge-sort

Abstract

Sorting is a common problem in computer science. There are lot of well-known sorting algorithms created for sequential execution on a single processor. Recently, hardware platforms enable to create wide parallel algorithms. We have standard processors consist of multiple cores and hardware accelerators like GPU. The graphic cards with their parallel architecture give new possibility to speed up many algorithms. In this paper we describe results of implementation of a few different sorting algorithms on GPU cards and multicore processors. Then hybrid algorithm will be presented which consists of parts executed on both platforms, standard CPU and GPU.

Downloads

Download data is not yet available.

References

E. Sintorn, U. Assarson: “Fast parallel GPU-sorting using a hybrid algorithm. Journal of Parallel and Distibuted Computing”, 68 (2008) 1381-1388, Elsevier, 2008

N. K. Govindaraju, J.Gray, R.Kumar, D. Manocha: “Gputerasort: High performance graphics coprocesor sorting for large database management”, in proceedings of ACM SIGMOD International Conferenence on Management of Data, 2006.

N. K. Greβ, G.Zachmann: “Gpu-abisort: Optimal parallel sorting on stream architectures”, in proceedings of the 20th IEEE International Parallel and Distributed Processing Symposium IPDPS'06, 2006. International Conferenence on Management of Data, 2006.

NVIDIA CUDA Compute Uni_ed Device Architecture-Programming Guide, 2007.

K. E. Batcher. Sorting networks and their applications. In AFIPS '68 (Spring): Proceedings of the April 30-May 2, 1968, spring joint computer conference, pages 307-314, New York, NY, USA, 1968, ACM.

G. Bilardi and A. Nicolau. Adaptive bitonic sorting: An optimal parallel algorithm for shared memory machines. Technical report, Ithaca, NY, USA, 1986.

D. Cederman and P. Tsigas. A practical quicksort algorithm for graphics processors. In ESA '08: Proceedings of the 16th annual European symposium on Algorithms, pages 246-258, Berlin, Heidelberg, 2008. Springer-Verlag.

R. Baraglia, G. Capannini, F. Silvestri, F.Nardini: Sorting using BItonic netwoRk wIth CUDA