ISSN:
1573-7640
Keywords:
Binary processor tree
;
cost-optimality
;
inverse perfect shuffle
;
parallel algorithm
;
prefix sums
;
recursive doubling
;
scheduling
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract Givenn numbersa 0,a 1,...,a n −1, it is required to compute all sums of the forma 0+a 1+...+a i , fori=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 asrecursive doubling allows all sums to be computed in O(logn) time on a model of computation wheren processors communicate through aninverse perfect suffle interconnection network. In this paper we show how the problem can be solved on a simple network, namely abinary tree of processors. In addition, we show how to extend our solution to obtain an optimal-cost algorithm. The algorithm usesp processors and runs in O((n/p)+logp) time, for a cost of O(n+p logp). This cost is optimal whenp logp=O(n). Finally, two applications of our results are illustrated, namely job scheduling with deadlines and the knapsack problem.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01379098
Permalink
