It is hard to achieve good speed‐ups for parallel list ranking on distributed‐memory machines because the problem requires a substantial number of communication rounds, each incurring some start‐up delay. For input sizes Nthat are very large in comparison with the number of processors Pthese start‐up costs can be amortized to a certain extent. For modest N/Pvalues, so far the best approach was the basic pointer‐jumping approach. In this paper a novel algorithm, one‐by‐one cleaning , is presented. It has the unique property that the routing consists of O(P)rounds in which each processing unit (PU) sends a packet to only one other PU. Pointer jumping requires a logarithmic number of rounds in which each PU sends a packet to all other PUs. Because the constants are small, and the internal work performed is less than that of pointer jumping, one‐by‐one cleaning is about twice as fast, which is demonstrated by comparing the performance of implementations of both algorithms on the Intel Paragon.
