Optimal computation of prefix sums on a binary tree of processors (Q1099947)

Given n numbers \(a_ 0,a_ 1,...,a_{n-1}\), it is required to compute all sums of the form \(a_ 0+a_ 1+...+a_ i\), for \(i=0,1,...,n-1\). This problem arises in many applications and is trivial to solve sequentially in O(n) time. Besides its practical importance, the problem gains an additional theoretical interest in parallel computation. A technique known as recursive doubling allows all sums to be computed in O(log n) time on a model of computation where n processors communicate through an inverse perfect shuffle interconnection network. In this paper we show how the problem can be solved on a simple network, namely a binary tree of processors. In addition, we show how to extend our solution to obtain an optimal-cost algorithm. The algorithm uses p processors and runs in \(O((n/p)+\log p)\) time, for a cost of \(O(n+p \log p)\). This cost is optimal when p log p\(=O(n)\). Finally, two applications of our results are illustrated, namely job scheduling with deadlines and the knapsack problem.