Communication conscious radix sort
Daniel Jiménez-González, Josep-L. Larriba-Pey, Juan J. Navarro · 1999
The exploitation of data locality in parallel computers is paramount to reduce the memory traffic 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 at most once between processing nodes. Also, our algorithm reduces the amount of data communicated. Finally, the new algorithm achieves a good load 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 -R...