EFFICIENT LIST RANKING ON THE RECONFIGURABLE MESH, WITH APPLICATIONS

Finding a vast array of applications, the list-ranking problem has eme rged as one of the fundamental techniques in parallel algorithm design . Surprisingly, the best previously known algorithm to rank a list of it items on a reconfigurable mesh of size n x n was running in O (log n) time. It was open for more than 8 years to obtain a faster algorith m 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 x n, Our resu lts open the door to a large number of efficient list-ranking-based al gorithms on reconfigurable meshes.