Efficient implementation of sorting on multi-core SIMD CPU architecture
Efficient implementation of sorting on multi-core SIMD CPU architecture
复制标题
DOI：
10.14778/1454159.1454171
复制
发表时间：
2008-08
期刊：
影响因子：
--
通讯作者：
J. Chhugani;A. Nguyen;V. Lee;William Macy;Mostafa Hagog;Yen-kuang Chen;A. Baransi;Sanjeev Kumar;P. Dubey
中科院分区：
文献类型：
--
作者：
J. Chhugani;A. Nguyen;V. Lee;William Macy;Mostafa Hagog;Yen-kuang Chen;A. Baransi;Sanjeev Kumar;P. Dubey
对输入数字列表进行排序是计算机科学领域中最基本的问题之一，特别是在高吞吐量数据库应用中。虽然文献中有很多不同风格的排序算法，但不同的架构需要定制的实现来实现更快的排序时间。本文提出了一个有效的实现和详细的分析，合并排序在当前的CPU架构。我们的SIMD实现与128位SSE是3.3倍的速度比标量版本。此外，我们的算法执行一个有效的多路合并，并且不受内存带宽的限制。我们的多线程SIMD实现在不到0.5秒的时间内对6400万个浮点数进行排序。这一测量的性能与所有先前公布的结果相比毫不逊色。此外，本文证明了性能的可扩展性，所提出的排序算法相对于现代芯片多处理器（CMP）架构，包括SIMD宽度和核心数的某些显着的架构特征。基于我们对各种架构配置的分析模型，我们看到我们的实现具有出色的可扩展性，SIMD宽度扩展到比当前128位SSE宽度宽16倍，CMP核心数量扩展远远超过32个核心。对英特尔即将推出的x86众核Larrabee架构的周期准确模拟证实了我们提出的算法的可扩展性。
Sorting a list of input numbers is one of the most fundamental problems in the field of computer science in general and high-throughput database applications in particular. Although literature abounds with various flavors of sorting algorithms, different architectures call for customized implementations to achieve faster sorting times. This paper presents an efficient implementation and detailed analysis of MergeSort on current CPU architectures. Our SIMD implementation with 128-bit SSE is 3.3X faster than the scalar version. In addition, our algorithm performs an efficient multiway merge, and is not constrained by the memory bandwidth. Our multi-threaded, SIMD implementation sorts 64 million floating point numbers in less than0.5 seconds on a commodity 4-core Intel processor. This measured performance compares favorably with all previously published results. Additionally, the paper demonstrates performance scalability of the proposed sorting algorithm with respect to certain salient architectural features of modern chip multiprocessor (CMP) architectures, including SIMD width and core-count. Based on our analytical models of various architectural configurations, we see excellent scalability of our implementation with SIMD width scaling up to 16X wider than current SSE width of 128-bits, and CMP core-count scaling well beyond 32 cores. Cycle-accurate simulation of Intel's upcoming x86 many-core Larrabee architecture confirms scalability of our proposed algorithm.