User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Better Trade-offs for Parallel List Ranking


Sibeyn,  Jop F.
Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

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