zbMATH — the first resource for mathematics

Efficient list ranking on the reconfigurable mesh, with applications. (English) Zbl 0910.68025
Summary: Finding a vast array of applications, the list-ranking problem has emerged as one of the fundamental techniques in parallel algorithm design. Surprisingly, the best previously known algorithm to rank a list of \(n\) items on a reconfigurable mesh of size \(n\times n\) was running in \(O(\log n)\) time. It was open for more than 8 years to obtain a faster algorithm for this important problem.
Our main contribution is to provide the first breakthrough: we propose a deterministic list ranking algorithm that runs in \(O(\log^*n)\) time as well as a randomized one running in \(O(1)\) expected time, both on a reconfigurable mesh of size \(n\times n\). Our results open the door to a large number of efficient list-ranking-based algorithms on reconfigurable meshes.

68M99 Computer system organization
Full Text: DOI