Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Conference Paper

Better Trade-offs for Parallel List Ranking


Sibeyn,  Jop F.
Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
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: https://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.