access icon openaccess Array sort: an adaptive sorting algorithm on multi-thread

This is an open access article published by the IET under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/)
Received 23/07/2018, Accepted 07/02/2019, Revised 20/01/2019, Published 27/02/2019

Sorting is the most fundamental operation in database system. There are many classical sorting algorithms and among them the most commonly-used sorting algorithm in modern database system is merge sort. Merge sort is an efficient, general-purpose, comparison-based sorting algorithm. As merge sort is based on a divide and conquer model, it has found wide use in parallel computing algorithms. In this study, the authors present an adaptive sorting algorithm based on merge sort which is called array sort. Array sort not only takes advantages of merge sort, but also simplify the merge step by using a tag array. The proposed implementation consists of three phases: tag array creation phase, tag array split phase and list merge phase. Instead of just evaluating array sort in a single thread environment, the authors also run their experiments on multi-thread to test how array sort performs.

Inspec keywords: merging; database management systems; sorting; multi-threading; parallel algorithms

Other keywords: array sort algorithm; list merge phase; comparison-based sorting; divide and conquer model; single thread environment; merge sort; tag array creation phase; adaptive sorting algorithm; tag array split phase; multithread; database system; classical sorting algorithms; parallel computing algorithms

Subjects: Parallel software; Data handling techniques; Database management systems (DBMS)

References

    1. 1)
      • 6. Huang, X., Liu, Z., Yuan, T.: ‘A high-efficiency sorting algorithm on multi-core’. Electrical, Control Engineering and Computer Science: Proc. of the 2015 Int. Conf. on Electrical, Control Engineering and Computer Science (ECECS 2015), Hong Kong, May 2015.
    2. 2)
      • 3. Furtak, T., Amaral, J.N., Niewiadomski, R.: ‘Using SIMD registers and instructions to enable instruction-level parallelism in sorting algorithms’. Proc. of the ACM Symp. on Parallelism in Algorithms and Architectures, New York, 2007, pp. 348–357, doi: 10.1145/1248377.1248436.
    3. 3)
      • 5. Inoue, H., Moriyama, T., Komatsu, H., et al: ‘A high-performance sorting algorithm for multicore single-instruction multiple-data processors’, Softw., Pract. Exp., 2012, 42, pp. 753–777.
    4. 4)
      • 9. Bilardi, G., Nicolau, A.: ‘Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines’, SIAM J. Comput., 1989, 18, (2), pp. 216–228.
    5. 5)
      • 10. Greß, A., Zachmann, G.: ‘GPU-ABiSort: optimal parallel sorting on stream architectures’. Proc. of the 20th IEEE Int. Parallel and Distributed Processing Symp., Rhodes, Greece, April 2006, p. 45.
    6. 6)
      • 1. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: ‘Introduction to algorithms’ (MIT Press, Cambridge, 2000).
    7. 7)
      • 4. Satish, N., Kim, C., Chhugani, J., et al: ‘Fast sort on CPUs and GPUs:A case for bandwidth oblivious SIMD sort’. SIGMOD, Indianapolis, USA, 2010.
    8. 8)
      • 7. Batcher, K.E.: ‘Sorting networks and their applications’. Proc. of the AFIPS Spring Joint Computer Conf. 32 (AFIPS), 1968, pp. 307–314.
    9. 9)
      • 2. Martin, W.A.: ‘Sorting’, ACM Comput. Surv., 1971, 3, (4), pp. 147–174.
    10. 10)
      • 8. Govindaraju, N., Gray, J., Kumar, R., et al: ‘GPUTerasort: high performance graphics co-processor sorting for large database management’. Proc. of the ACM SIGMOD Conf., Chicago, USA, 2006, pp. 325–336.
http://iet.metastore.ingenta.com/content/journals/10.1049/joe.2018.5154
Loading

Related content

content/journals/10.1049/joe.2018.5154
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading