Optimal parallel randomized algorithms for sparse addition and identification (Q1103402)

Although many sophisticated parallel algorithms now exist, most of them are not sensitive to properties of the input which can be determined only at run-time. For example, in the case of parallel addition in shared memory models, we intuitively understand that we should not add those inputs whose value is zero. A technique which exploits this idea may beat the general lower bound for addition if the count of nonzero operants is much smaller than the numbers to be added. In this paper, we device such algorithms for two fundamental problems of parallel computation. Our model of computation is the CRCW PRAM. We first provide a randomized algorithm for parallel addition which never errs and computes the result in O(log m) expected parallel time, where m is the count of nonzero entries among the n numbers to be added. This algorithm uses O(m) shared space. We then use this result to solve an interesting problem of processor identification. All our techniques enjoy the following properties: (1) They never produce an erroneous answer. (2) If T is the actual parallel time and E(T) its expected value, then \(\Pr ob\{T>k\cdot E(T)\}\leq n^{-c}\), where k is arbitrary and \(c>1\) is linear on k and can be specified by the implementor of the algorithm. (3) Our algorithms do not know m initially, but they produce an accurate estimate for it.