zbMATH — the first resource for mathematics

Optimal computation of prefix sums on a binary tree of processors. (English) Zbl 0639.68032
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.

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68N25 Theory of operating systems
68Q25 Analysis of algorithms and problem complexity
90C35 Programming involving graphs or networks
Full Text: DOI
[1] S. G. Akl,Parallel Sorting Algorithms, Academic Press, Orlando, Florida (1985).
[2] E. Dekel and S. Sahni, Binary Trees and Parallel Scheduling Algorithms,IEEE Transactions on Computers C-32(3):307-315 (March 1983). · Zbl 0513.68031
[3] F. E. Fich, New Bounds For Parallel Prefix Circuits,Proc. of the 15th Annual ACM Symposium on Theory of Computing, Boston, Massachusetts, pp. 100-109 (May 1983).
[4] P. M. Kogge, Parallel Solution of Recurrence Problems,IBM Journal of Research and Development, pp. 138-148 (March 1974). · Zbl 0307.65080
[5] P. M. Kogge and H. S. Stone, A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations,IEEE Transactions on Computers C-22(8):786-792 (August 1973). · Zbl 0262.68015
[6] C. P. Kruskal, L. Rudolph, and M. Snir, The Power of Parallel Prefix,IEEE Transactions on Computers C-34 (10):965-968 (October 1985).
[7] R. E. Ladner and M. J. Fischer, Parallel Prefix Computation,Journal of the ACM 27(4):831-838 (October 1980). · Zbl 0445.68066
[8] H. Meijer and S. G. Akl, Bit Serial Addition Trees and Their Applications,Proceedings of the Canadian Information Processing Society Congress ’87, Winnipeg, Manitoba, pp. 319-322 (May 1987).
[9] J. Reif, Probabilistic Parallel Prefix Computation,Proceeding of the International Conference on Parallel Processing, Bellaire, Michigan, pp. 291-298 (August 1984).
[10] J. T. Schwartz, Ultracomputers,ACM Transactions on Programming Languages and Systems 2(4):484-521 (October 1980). · Zbl 0468.68027
[11] H. S. Stone, (ed.),Introduction to Computer Architecture, Science Research Associates, Chicago, Illinois (1980). · Zbl 0322.68004
[12] R. Wagner and Y. Han, Parallel Algorithms For Bucket Sorting and the Data Dependent Prefix Problem,Proceedings of the Internatinal Conference on Parallel Processing, St. Charles, Illinois, pp. 924-930 (August 1986).
[13] R. P. Brent, The Parallel Evaluation of General Arithmetic Expressions,Journal of the ACM 21(2):201-206 (1974). · Zbl 0276.68010
[14] E. Horowitz and S. Sahni,Fundamentals of Computer Algorithms, Computer Science Press, Potomac, Maryland (1978). · Zbl 0442.68022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.