Title :
A simple optimal list ranking algorithm
Author_Institution :
Dept. of Comput. Sci. & Eng., Indian Inst. of Technol., Mumbai, India
Abstract :
We consider the problem of ranking an N element list on a P processor EREW PRAM. Recent work on this problem has shown the importance of grain size. While several optimal O(N/P+log P) time list ranking algorithms are known, Reid-Miller and Blelloch (1994) recently showed that these do not lead to good implementations in practice, because of the fine-grained nature of these algorithms. In Reid-Miller and Blelloch´s experiments the best performance was obtained by an O(N/P+log2 P) time coarse grained randomized algorithm devised by them. We build upon their idea and present a coarse-grained randomized algorithm that runs in time O(N/P+log P), and is thus also optimal. Our algorithm simplifies some of the ideas from [6, 7]-these simplifications might be of interest to implementers
Keywords :
computational complexity; concurrency theory; parallel algorithms; randomised algorithms; N element list ranking; P processor EREW PRAM; coarse grained randomized algorithm; computation time; grain size; performance; simple optimal list ranking algorithm; Algorithm design and analysis; Computational geometry; Computer science; Concurrent computing; Grain size; National electric code; Parallel algorithms; Partitioning algorithms; Phase change random access memory; Radio access networks;
Conference_Titel :
High Performance Computing, 1998. HIPC '98. 5th International Conference On
Conference_Location :
Madras
Print_ISBN :
0-8186-9194-8
DOI :
10.1109/HIPC.1998.737971