Item

Abstract

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.