Communication Conscious Radix Sort

The explotation of data locality in parallel computers is paramount to reduce the memory trac and communication among processing nodes. We focus on the exploitation of locality by Parallel Radix sort. The original Parallel Radix sort has several communication steps in which one sorting key may have to visit several processing nodes. In response to this, we propose a reorganization of Radix sort that leads to a highly local version of the algorithm at a very low cost. As a key feature, our algorithm performs one only communication step, forcing keys to move only once between processing nodes. Also, it reduces the amount of data communicated. Finally, the new algorithm achieves a good load and communication balance which makes it insensitive to skewed data distributions. We call the new version of Parallel Radix sort that combines locality and load balance, Communication and Cache Conscious Radix sort (C 3-Radix sort). Our results on 16 processors of the SGI O2000 show that C 3-Radix sort reduces the execution time of the previous fastest version of Parallel Radix sort by 3 times for data sets larger than 8M keys and by almost 2 times for smaller data sets.