The comparison of parallel sorting algorithms implemented on different hardware platforms

• Autorzy: Żurek D. , Pietroń M. , Wielgosz M. , Wiatr K.
• Języki publikacji: EN

Abstrakty

EN

Sorting is a common problem in computer science. There are a lot of well-known sorting algorithms created for sequential execution on a single processor. Recently, many-core and multi-core platforms have enabled the creation of wide parallel algorithms. We have standard processors that consist of multiple cores and hardware accelerators, like the GPU. Graphic cards, with their parallel architecture, provide new opportunities to speed up many algorithms. In this paper, we describe the results from the implementation of a few different parallel sorting algorithms on GPU cards and multi-core processors. Then, a hybrid algorithm will be presented, consisting of parts executed on both platforms (a standard CPU and GPU). In recent literature about the implementation of sorting algorithms in the GPU, a fair comparison between many core and multi-core platforms is lacking. In most cases, these describe the resulting time of sorting algorithm executions on the GPU platform and a single CPU core.

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2013
• Tom: Vol. 14 (4)
• Strony: 679--691
• Opis fizyczny: Bibliogr. 11 poz., rys., wykr.

Twórcy

autor

Żurek D.

• ACC AGH Cyfronet, Krakow, Poland

autor

Pietroń M.

• ACC AGH Cyfronet, Krakow, Poland

autor

Wielgosz M.

• AGH University of Science and Technology, Faculty of Computer Science, Electronics and Telecommunications, ACC AGH Cyfronet, Krakow, Poland

autor

Wiatr K.

• AGH University of Science and Technology, Faculty of Computer Science, Electronics and Telecommunications, ACC AGH Cyfronet, Krakow, Poland

Bibliografia

• [1] Sintorn E., Assarson U.: Fast parallel GPU-sorting using a hybrid algorithm. Journal of Parallel and Distributed Computing, vol. 68, pp. 1381–1388, 2008.
• [2] Cederman D., Tsigas P.: A practical quick-sort algorithm for graphics processors. Proc. of the 16th annual European Symposium on Algorithms, Heidelberg, pp. 246–258, 2008, Springer-Verlag.
• [3] Govindaraju N. K., Gray J., Kumar R., Manocha D.: Gputerasort: High performance graphics co-processor sorting for large database management. Proc. of ACM SIGMOD International Conference on Management of Data, Chicago, United States, June 2006.
• [4] Greß N. K., Zachmann G.: Gpuabisort: Optimal parallel sorting on stream architectures. Proc. of the 20th IEEE International Parallel and Distributed Processing Symposium IPDPS , Heidelberg, 2006.
• [5] Bilardi G., Nicolau A.: Adaptive bitonic sorting: An optimal parallel algorithm for shared memory machines. Technical report, Ithaca, NY, USA, 1986.
• [6] Batcher K. E.: Sorting networks and their applications. Proc. of the AFIPS’68, April 30-May 2, pp. 307–314, New York, NY, USA.
• [7] NVIDIA: NVIDIA CUDA. Compute Unified Device Architecture-Programming Guide. 2007.
• [8] OpenMP: OpenMP website – www.openmp.org.
• [9] Peters H., Schulz-Hildebrandt O., Luttenberger N.: A Novel Sorting Algorithm for Many-core Architectures Based on Adaptive Bitonic Sort. Proc. of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium, pp. 227–237, IEEE Computer Society Washington, DC, USA, 2012.
• [10] Szymczyk M.: Równoległy algorytm typu quicksort. Automatyka, vol. 1, z. 1, pp. 402–408, 1997.
• [11] Sequential and parallel algorithms –http://www.iti.fhflensburg.de/lang/algorithmen/sortieren/algo.htm