CellSort: High Performance Sorting on the Cell Processor
CellSort: High Performance Sorting on the Cell Processor
复制标题
DOI：
--
复制
发表时间：
2007-09
期刊：
影响因子：
--
通讯作者：
B. Gedik;R. Bordawekar;Philip S. Yu
中科院分区：
文献类型：
--
作者：
B. Gedik;R. Bordawekar;Philip S. Yu
在本文中，我们描述的设计和实现CellSort -一个高性能的分布式排序算法的细胞处理器。我们设计的CellSort作为一个分布式的双调合并与数据并行双调排序内核。为了最好地利用细胞处理器的架构，并利用所有可用的形式的并行性，以实现良好的可扩展性，我们的结构CellSort作为一个三层排序。第一层是SIMD（单指令多数据）优化的双调排序，它对最多128 KB的项进行排序，这些项可以放入一个SPE（Cell上的协处理器）的本地存储中。我们设计了一个全面的SIMD化方案，采用数据并行，即使是最细粒度的步骤的双调排序内核。我们的研究结果表明，SIMD化的双调排序内核大大上级SPE上的其他替代方案，与3.2GHz Intel Xeon上的快速排序相比，其执行速度快1.7倍。第二层是针对通过异步DMA进行的跨SPE数据传输而优化的核内双调合并，并对足够数量的项进行排序，这些项可以容纳参与SPE的本地存储上的累积可用空间。我们设计的数据传输和同步模式，最大限度地减少串行部分的代码，利用高聚合跨SPE的细胞带宽。结果表明，随着SPE数量的增加，核内双调排序在Cell处理器上扩展良好，并且与双3.2 GHz Intel Xeon上的并行快速排序相比，使用16个SPE的性能快10倍。第三层是核外双调合并，它对存储在主存中的大量项进行排序。结果表明，当正确实现时，Cell上的分布式核外双调排序可以显著优于渐进（平均情况）的上级快速排序，用于大量内存驻留项（与双3.2GHz Intel Xeon相比，使用16个SPE对0.5GB数据进行排序时，速度快4倍）。
In this paper we describe the design and implementation of CellSort - a high performance distributed sort algorithm for the Cell processor. We design CellSort as a distributed bitonic merge with a data-parallel bitonic sorting kernel. In order to best exploit the architecture of the Cell processor and make use of all available forms of parallelism to achieve good scalability, we structure CellSort as a three-tiered sort. The first tier is a SIMD (single-instruction multiple data) optimized bitonic sort, which sorts up to 128KB of items that cat fit into one SPE's (a co-processor on Cell) local store. We design a comprehensive SIMDization scheme that employs data parallelism even for the most fine-grained steps of the bitonic sorting kernel. Our results show that, SIMDized bitonic sorting kernel is vastly superior to other alternatives on the SPE and performs up to 1.7 times faster compared to quick sort on 3.2GHz Intel Xeon. The second tier is an in-core bitonic merge optimized for cross-SPE data transfers via asynchronous DMAs, and sorts enough number of items that can fit into the cumulative space available on the local stores of the participating SPEs. We design data transfer and synchronization patters that minimize serial sections of the code by taking advantage of the high aggregate cross-SPE bandwidth available on Cell. Results show that, in-core bitonic sort scales well on the Cell processor with increasing number of SPEs, and performs up to 10 times faster with 16 SPEs compared to parallel quick sort on dual-3.2 GHz Intel Xeon. The third tier is an out-of-core bitonic merge which sorts large number of items stored in the main memory. Results show that, when properly implemented, distributed out-of-core bitonic sort on Cell can significantly outperform the asymptotically (average case) superior quick sort for large number of memory resident items (up to 4 times faster when sorting 0.5GB of data with 16 SPEs, compared to dual-3.2GHz Intel Xeon).