Practical Parallel List Ranking

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 to just 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 \cdot 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 sparse-ruling-set algorithm the speed-up strongly increases with the number $k$ of nodes per PU, to finally reach $27$ with 100 PUs, for $k = 2 \cdot 10^6$