|
Abstract : |
Abstract. We presentarandomized parallel list ranking algorithm for distributed memory multiprocessors. A simple version requires, with high probability, log(3p) +logln(n) = ~O(log p + log log n) communi-cation rounds (h-relations with h = ~O ( n p)) and ~O ( n p) local computa-tion. An improved version requires, with high probability, only r (4k + 6) log ( 2 3 p)+8 = ~O(k log p) communication rounds where k = minfi 0j ln (i+1) n ( 2 3 p)2i+1 g.Notethat k<ln (n) is an extremely small number. For n 10 10100 and p 4, the value of k is at most2.For a given number of processors, p, the number of communication rounds required is, for all practical purposes, independent ofn. For n 10 10100 and 4 p 2048, the number of communication rounds in our algorithm is bounded, with high probability, by 118. We conjecture that the actual number of communications rounds will not exceed 50. 1, |
