Optimal computation of prefix sums on a binary tree of processors |
| |
Authors: | Henk Meijer Selim G. Akl |
| |
Affiliation: | (1) Department of Computing and Information Science, Queen's University, Kingston, Ontario, Canada |
| |
Abstract: | Givenn numbersa0,a1,...,an–1, it is required to compute all sums of the forma0+a1+...+ai, 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.This work was supported by the Natural Sciences and Engineering Research Council of Canada under Grants A0282 and A3336. |
| |
Keywords: | Binary processor tree cost-optimality inverse perfect shuffle parallel algorithm prefix sums recursive doubling scheduling |
本文献已被 SpringerLink 等数据库收录! |
|