# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Better Trade-offs for Parallel List Ranking

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Sibeyn, J. F. (1997). Better Trade-offs for Parallel List Ranking. In *Proceedings
of the 9th Symposium on Parallel Algorithms and Architectures (SPAA-97)* (pp. 221-230). New York: ACM Press.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-38FC-2

##### 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.