CellSort: High Performance Sorting on the Cell Processor

In this paper the authors describe the design and implementation of CellSort a high performance distributed sort algorithm for the Cell processor. They 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, they 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.