Çok Çekirdekli İşlemciler İçin Yük Dengelemeli Melez Bir Paralel Sıralama Metodu

Abstract

Sıralama işlemi, bilgisayar bilimlerinin en temel problemlerindendir. Karmaşık verilerin, sıralama işlemleriyle düzenli hale getirilmesi birçok yararlar sağlamaktadır. Sıralama gereksinimi de aslında düzensiz verilerin işlenmesinde yaşanan sıkıntılardan kaynaklanır. Metinlerde alfabetik sıralama yapılması veya sayısal verilerin büyükten küçüğe (veya tersine) sıralanması buna örnek olarak verilebilir. Bu çalışmada bilinen sayısal sırama işleminin günümüz ev bilgisayarlarında dahi mevcut olan çok çekirdekli işlemcilerin kullanımı ile ne kadar hızlandırılabileceğini gösterilmektedir. Eğer basitçe ve hızlıca sayı sıralanması istenirse, quicksort veya merge-sort kullanılabilir, en çok bilinen sıralama algoritmaları da bunlardır. Bu algoritmaların işlem karmaşıklığı literatürde O( n lg n ) olarak verilir. Özel şartlara sahip sayılarla yapılan sıralamalarda ise O( n ) karmaşıklığa kadar inilebilir. Ancak bu değerlerle sıralama işleminin çalışma süresi kesin olarak bilinemez, sadece tahmin edilebilir. Öyle ki, işlem karmaşıklığı aynı kalsa da algoritmalar hızlandırılabilir. Bunun yöntemi paralel hesaplama teknikleridir. Bu çalışmada standart bir i5 işlemcili bir bilgisayarda OpenMP kütüphanesi ile 8 çekirdek üzerinde çalışılmış, 45 kata kadar önemli hız değerleri elde edilmiştir.

Keywords

• Sıralama algoritmaları
• Paralel hesaplama
• Çekirdek programlama
• OpenMP

A Hybrid Parallel Sorting Method For Multi-Core CPU’s

Abstract

Sorting of given random data is putting them into a certain order. For example, alphabetical sorting of texts, or sorting numerical data in ascending or descending order. The requirement of sorting jobs is actually caused by difficulties in processing unsorted data as accessing on non-indexed data in databases. This study focused to how many times can be accelerated for the numerical sorting process by using processors and its cores of today's home computers. If data hasn’t any form of special numbers, the aim is simply and quickly sort of some numbers, the well-known fastest sort algorithms are quicksort or merge-sort. The processing complexity of these algorithms is given in the literature as O(n lg n). However, this formula certainly does not give an idea of the working time of the sorting process. Although the complexity remains the same, the algorithms can be accelerated. The suggested method in this work uses parallel computing techniques for speed-up. In this study, we used OpenMP library on a standard i5 computer with 8 cores and speed-up values is reached to 45 times.

Keywords

• Sorted algorithms
• Parallel computing
• Core programming
• OpenMP

References

1. Akl S. G. ve Santoro, N., 1987, Optimal Parallel Merging and Sorting Without Memory Conflicts, IEEE Transactions on Computers, vol. C-36, no. 11, 367-1369
2. Alyasseri, Z.. Parallelize Bubble Sort Algorithm Using OpenMP, Eprint Arşiv: 4(2014):103-110.
3. Berney K. ve Sitchinava, N., 2020, Engineering Worst-Case Inputs for Pairwise Merge Sort on GPUs, 2020 IEEE International Parallel and Distributed Processing Symposium (IPDPS), 1133-1142
4. Cho, M., Brand, D., Kulandaisamy, V., Bordawekar, R. ve Puri, R. 2015, PARADIS: An efficient parallel algorithm for in-place radix sort, Proceedings of the VLDB Endowment 8.12(2015):1518-1529
5. Chowdhury, R.A., Ramachandran, V., Silvestri, F. ve Blakeley, B., Oblivious algorithms for multicores and network of processors, Journal of Parallel & Distributed Computing 73.7(2013), 911-925.
6. Cole, R., 1988, Parallel merge sort , SIAM Journal on ComputingVol. 17, Iss. 4, 770-785
7. Cole, R. ve Ramachandran, V. 2017, ACM Transactions on Parallel Computing, Vol.3-4, Article 23, 1–31
8. Green, O., Mccoll, R. ve Bader, D., 2014. GPU merge path: a GPU merging algorithm. 26th ACM international conference on Supercomputing, 331-340. Web: https://github.com/liuvince/polytech-cuda-project

9. Herruzo, E. Ruíz, G. ve Plata, O., 2007, A New Parallel Sorting Algorithm based on Odd-Even Mergesort, 15th EUROMICRO International Conference on Parallel, Distributed and Network-Based Processing (PDP'07), 18-22. Horowitz, E., Sahnı, S. and Rajasekaran, S., 1998, Fundamentals of Computer Algorithms, Second Edition, Computer Science Press, 154-165
10. Hou, K., Hao, W. ve Feng, W.C., 2018, A Framework for the Automatic Vectorization of Parallel Sort on x86-Based Processors, IEEE Transactions on Parallel and Distributed Systems, 99
11. Jeon, M. ve Kim, D., 2003, Parallel Merge Sort with Load Balancing. International Journal of Parallel Programming 31, 21–33
12. Langr, D. ve Schovánková, K., 2021, A parallel quicksort based on C++ threading, Concurrency and Computation Practice and Experience
13. Lumunge, E., 2021, Paralel Quick Sort, Web sayfası, ziyaret: 2022, https://iq.opengenus.org/parallel-quicksort/amp/
14. Odeh, S., Green, O. Mwassi, Z., Shmueli, O. ve Birk Y., 2012, Merge Path - Parallel Merging Made Simple, Parallel & Distributed Processing Symposium Workshops & Phd Forum IEEE.
15. OpenMP-Sort, Sorting Things Out İnternet Dökümanı, 2016, Ziyaret tarihi: 2022, https://www.openmp.org/wp-content/uploads/sc16-openmp-booth-tasking-ruud.pdf OpenMP, Ziyaret tarihi: 2022, https://www.openmp.org
16. Panwar, M., Kumar, M. ve Bhargava, S. 2014, GPU Matrix Sort (An Efficient Implementation of Merge Sort), International Journal of Computer Applications, Vol.89, 9-11.
17. Satish, N., Harris M. ve Garland, M., 2009, Designing efficient sorting algorithms for manycore GPUs, 2009 IEEE International Symposium on Parallel & Distributed Processing, 1-10
18. Sedgewick, R. ve Wayne, K., 2011 (1), Algorithms, 4th edition, Princeton University Press, 288-307, Web link: https://algs4.cs.princeton.edu/23quicksort/
19. Sedgewick, R. ve Wayne, K., 2011 (2), Algorithms, 4th edition, Princeton University Press, 270-287, Web link: https://algs4.cs.princeton.edu/22mergesort/
20. Sedgewick, R. ve Wayne, K., 2011 (3), Algorithms, 4th edition, Princeton University Press, 248-249, Web link: https://algs4.cs.princeton.edu/21elementary/
21. Sintorn, E. ve Assarsson, U., 2008, Fast parallel GPU-sorting using a hybrid algorithm. Journal of Parallel Distributed Computing 68(10), 1381-1388
22. Takayuki, U. ve Shuhei, O., 2015, Performance Comparison of Open-Source Parallel Sorting with OpenMP, Third International Symposium on Computing and Networking (CANDAR), 334-340
23. Valerievich, B.A., Anatolievna, P.T., Alekseevna, B.M. ve Vladimirovich, S.S., 2017, The implementation on CUDA platform parallel algorithms sort the data, 6th Mediterranean Conference on Embedded Computing (MECO), 1-4
24. Wikipedia, OpenMP sayfası, Ziyaret tarihi: 2022, https://tr.wikipedia.org/wiki/OpenMP
25. Wikipedia, Radix Sort sayfası, Ziyaret tarihi: 2022, https://en.wikipedia.org/wiki/Radix_sort
26. Xiao, S., Li. C., Guo, B. ve Xiao, H., 2020, A radix sorting parallel algorithm suitable for graphic processing unit computing. Concurrency and Computation Practice and Experience
27. Yu, T. ve Li. W, 2022, A Creativity Survey of Parallel Sorting Algorithm, Cornel Univeristy Press, arXiv preprint
28. Zhang, K., Li, J., Chen, G. ve Wu, B., 2011, GPU accelerate parallel Odd-Even merge sort: An OpenCL method, Proceedings of the 2011 15th International Conference on Computer Supported Cooperative Work in Design (CSCWD), 76-83