Journal of Information Science and Engineering, Vol. 16 No. 1, pp. 41-64

Efficient Parallel Prefix Algorithms on Multicomputers

Given n values v(0), v(1),..., v(n - 1) and an associative binary operation, denoted by o, the prefix computation problem, or simply the prefix problem, is to compute the n prefixes v(0) o v(1) o ... o v(i), 0 £ i £ n - 1. We are interested in performing prefix computation on message-passing completely connected multicomputers with the weakest communication capability in as few communication steps as possible. An efficient algorithm is presented to solve the prefix problem on a system of n processors. To explore the possibility of obtaining a faster algorithm, a class of algorithms is then presented. It is shown that the algorithm in this class requiring the fewest communication steps is equivalent to the first algorithm presented.

Keywords:
completely connected multicomputers, message-passing, parallel algorithms, prefix computation, send-or-receive