Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper revisits the classical list ranking problem in parallel computing, enhancing the sparse ruling-set algorithm originally proposed by Sibeyn to effectively scale across large machines and input sizes. By employing advanced algorithm and performance engineering techniques, the authors achieve significant improvements in scalability, enabling the processing of billions of elements on up to 24,576 cores. Their extensive experimental analysis reveals the critical impact of algorithm parameters and optimizations such as indirect communication and message coalescing on performance outcomes.
Scaling list ranking to billions of elements on thousands of cores reveals new efficiencies in parallel computing that could transform algorithm design.
The list ranking problem is one of the classical problems of parallel computing, with nontrivial algorithms and many applications as a subroutine for solving other problems. While it has been intensively studied in the early days of parallel computing, few things happened in the last 20 years. In particular, there is little work on scaling list ranking to large machines and input sizes. We reconsider list ranking starting from the ground-breaking results of Sibeyn a quarter century ago. We employ algorithm and performance engineering to improve his sparse ruling-set algorithm, making it capable of scaling to many processors, and provide a more detailed analysis of the impact of the algorithm's parameters, further guiding our practical implementation. We perform an extensive experimental study across a variety of input instances with different structural properties. We demonstrate that indirect communication, exploiting input locality, and message coalescing allows scaling to billions of elements on up to 24,576 cores.