AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors
AA-Sort: A New Parallel Sorting Algorithm for Multi-Core SIMD Processors
复制标题
DOI：
10.1109/pact.2007.12
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
H. Inoue;T. Moriyama;H. Komatsu;T. Nakatani
中科院分区：
文献类型：
--
作者：
H. Inoue;T. Moriyama;H. Komatsu;T. Nakatani
过去已经研究了许多排序算法，但只有少数算法能够有效地利用 SIMD 指令和线程级并行性。在本文中，我们提出了一种用于共享内存多处理器的新并行排序算法，称为对齐访问排序（AA-sort）。 AA 排序算法利用 SIMD 指令。高性能的关键是消除会降低 SIMD 指令有效性的未对齐内存访问。我们在 PowerPCreg 970MP 和 Cell Broadband Enginetrade 上实施并评估了 AA 排序。总之，在对 32 M 随机 32 位整数进行排序时，在 PowerPC 970MP 上，使用 SIMD 指令的 AA 排序顺序版本的性能比 IBM 优化的顺序排序库高 1.8 倍，比使用 SIMD 指令的 GPUTeraSort 的性能高 3.3 倍。此外，随着内核数量的增加，AA 排序的并行版本在两个平台上都表现出了比 GPUTeraSort 的并行版本更好的可扩展性。
Many sorting algorithms have been studied in the past, but there are only a few algorithms that can effectively exploit both SIMD instructions and thread-level parallelism. In this paper, we propose a new parallel sorting algorithm, called aligned-access sort (AA-sort), for shared-memory multi processors. The AA-sort algorithm takes advantage of SIMD instructions. The key to high performance is eliminating unaligned memory accesses that would reduce the effectiveness of SIMD instructions. We implemented and evaluated the AA-sort on PowerPCreg 970MP and Cell Broadband Enginetrade. In summary, a sequential version of the AA-sort using SIMD instructions outperformed IBM's optimized sequential sorting library by 1.8 times and GPUTeraSort using SIMD instructions by 3.3 times on PowerPC 970MP when sorting 32 M of random 32-bit integers. Furthermore, a parallel version of AA-sort demonstrated better scalability with increasing numbers of cores than a parallel version of GPUTeraSort on both platforms.