Practical Parallel List Ranking

✍ Scribed by Jop F Sibeyn; Frank Guillaume; Tillmann Seidel

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 546 KB
• Volume: 56
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1998.1508

✦ Synopsis

Parallel list ranking is a hard problem due to its extreme degree of irregularity. Also, because of its linear sequential complexity, it requires considerable effort just to reach speed-up one (break even). In this paper, we address the question of how to solve the list-ranking problem for lists of length up to 2_10 8 in practice: we consider implementations on the Intel Paragon, whose PUs are laid out as a grid.

It turns out that pointer jumping, independent-set removal, and sparse ruling sets all have practical importance for current systems. For the sparseruling-set algorithm the speed-up strongly increases with the number k of nodes per PU, finally reaching 27 with 100 PUs, for k=2_10 6 .