Better Trade-offs for Parallel List Ranking

An earlier parallel list ranking algorithm performs well for problem sizes $N$ that are extremely large in comparison to the number of PUs $P$. However, no existing algorithm gives good performance for reasonable loads. We present a novel family of algorithms, that achieve a better trade-off between the number of start-ups and the routing volume. We have implemented them on an Intel Paragon, and they turn out to considerably outperform all earlier algorithms: with $P = 2$ the sequential algorithm is already beaten for $N = \mbox{25,000}$; for $P = 100$ and $N = 10^7$, the speed-up is 21, and for $N = 10^8$ it even reaches 30. A modification of one of our algorithms solves a theoretical question: we show that on one-dimensional processor arrays, list ranking can be solved with a number of steps equal to the diameter of the network