Advanced Search
    Shi Song, Li Hongliang, Zhu Wei. Efficient Merge Sort Algorithms on Array-Based Manycore Architectures[J]. Journal of Computer Research and Development, 2016, 53(2): 362-373. DOI: 10.7544/issn1000-1239.2016.20148246
    Citation: Shi Song, Li Hongliang, Zhu Wei. Efficient Merge Sort Algorithms on Array-Based Manycore Architectures[J]. Journal of Computer Research and Development, 2016, 53(2): 362-373. DOI: 10.7544/issn1000-1239.2016.20148246

    Efficient Merge Sort Algorithms on Array-Based Manycore Architectures

    • Sorting is one of the most fundamental problems in the field of computer science. With the rapid development of manycore processors, it shows great importance to design efficient sort algorithms on manycore architecture. An important trend of manycore processors is array-based manycore architecture. This paper presents two efficient merge sort algorithms on array-based manycore architectures. Our algorithms achieve high performance by using DMA(direct memory access) multi-buffering strategy to improve the memory accessing efficiency, deeply balanced merging strategy to keep load-balancing between cores, SIMD(single instruction multiple data) merging method to exploit fine-grained parallelism and on-chip swap merging strategy to reuse on-chip data. Experimental results on DFMC(deeply-fused many-core) prototype system achieve a sorting rate of 647 MKeys/s(million keys per second), and the sorting efficiency(sorting rate/peak performance) is 3.3x higher than state-of-the-art GPU merge sort on GTX580, and 2.7x higher than the fastest merge sort on Intel Xeon Phi. Additionally, this paper establishes an analytical model to characterize the performance of our algorithms. Based on the analytical model, we analyze the influence of the main structural parameters to the performance of the algorithms, which will contribute to the study of many-core architecture.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return