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.

MSC:
 68M99 Computer system organization
Keywords:
list-ranking problem
Full Text: