Record Details

A simple optimal list ranking algorithm

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title A simple optimal list ranking algorithm
 
Creator RANADE, A
 
Description We consider the problem of ranking an N element fist 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 fist ranking algorithms are known, Reid-Miller and Blelloch recently showed that these do not lend to good implementations in practice[6, 7], 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 + log(2) P) time coarse grained randomized algorithm devised by them. I;Ve build upon their idea ann present a coarse-grained randomized algorithm that runs in time O(N/P +/- log P), mid is thus also optimal. Our algorithm simplifies some of the ideas from [6, 7] - these simplifications might be of interest to implementors.
 
Publisher IEEE COMPUTER SOC
 
Date 2011-10-24T12:57:52Z
2011-12-15T09:11:37Z
2011-10-24T12:57:52Z
2011-12-15T09:11:37Z
1998
 
Type Proceedings Paper
 
Identifier FIFTH INTERNATIONAL CONFERENCE ON HIGH PERFORMANCE COMPUTING, PROCEEDINGS,60-64
0-8186-9194-8
1094-7256
http://dx.doi.org/10.1109/HIPC.1998.737971
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15424
http://hdl.handle.net/100/2185
 
Source 5th International Conference on High Performance Computing,CHENNAI, INDIA,DEC 17-20, 1998
 
Language English