TY - JOUR T1 - Çok Çekirdekli İşlemciler İçin Yük Dengelemeli Melez Bir Paralel Sıralama Metodu TT - A Hybrid Parallel Sorting Method For Multi-Core CPU’s AU - Güngör, Cengiz PY - 2022 DA - December JF - Gaziosmanpaşa Bilimsel Araştırma Dergisi JO - GBAD PB - Tokat Gaziosmanpasa University WT - DergiPark SN - 2146-8168 SP - 69 EP - 83 VL - 11 IS - 3 LA - tr AB - 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. KW - Sıralama algoritmaları KW - Paralel hesaplama KW - Çekirdek programlama KW - OpenMP N2 - 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. CR - 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 CR - Alyasseri, Z.. Parallelize Bubble Sort Algorithm Using OpenMP, Eprint Arşiv: 4(2014):103-110. CR - 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 CR - 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 CR - 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. CR - Cole, R., 1988, Parallel merge sort , SIAM Journal on ComputingVol. 17, Iss. 4, 770-785 CR - Cole, R. ve Ramachandran, V. 2017, ACM Transactions on Parallel Computing, Vol.3-4, Article 23, 1–31 CR - 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 CR - 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 CR - 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 CR - Jeon, M. ve Kim, D., 2003, Parallel Merge Sort with Load Balancing. International Journal of Parallel Programming 31, 21–33 CR - Langr, D. ve Schovánková, K., 2021, A parallel quicksort based on C++ threading, Concurrency and Computation Practice and Experience CR - Lumunge, E., 2021, Paralel Quick Sort, Web sayfası, ziyaret: 2022, https://iq.opengenus.org/parallel-quicksort/amp/ CR - 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. CR - 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 CR - 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. CR - 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 CR - Sedgewick, R. ve Wayne, K., 2011 (1), Algorithms, 4th edition, Princeton University Press, 288-307, Web link: https://algs4.cs.princeton.edu/23quicksort/ CR - Sedgewick, R. ve Wayne, K., 2011 (2), Algorithms, 4th edition, Princeton University Press, 270-287, Web link: https://algs4.cs.princeton.edu/22mergesort/ CR - Sedgewick, R. ve Wayne, K., 2011 (3), Algorithms, 4th edition, Princeton University Press, 248-249, Web link: https://algs4.cs.princeton.edu/21elementary/ CR - Sintorn, E. ve Assarsson, U., 2008, Fast parallel GPU-sorting using a hybrid algorithm. Journal of Parallel Distributed Computing 68(10), 1381-1388 CR - 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 CR - 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 CR - Wikipedia, OpenMP sayfası, Ziyaret tarihi: 2022, https://tr.wikipedia.org/wiki/OpenMP CR - Wikipedia, Radix Sort sayfası, Ziyaret tarihi: 2022, https://en.wikipedia.org/wiki/Radix_sort CR - 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 CR - Yu, T. ve Li. W, 2022, A Creativity Survey of Parallel Sorting Algorithm, Cornel Univeristy Press, arXiv preprint CR - 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 UR - https://dergipark.org.tr/en/pub/gbad/issue//1176934 L1 - https://dergipark.org.tr/en/download/article-file/2657453 ER -