Optimal computation of prefix sums on a binary tree of processors (Q1099947): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q1379022 |
Changed an Item |
||
Property / author | |||
Property / author: Henk G. Meijer / rank | |||
Normal rank |
Revision as of 17:54, 28 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Optimal computation of prefix sums on a binary tree of processors |
scientific article |
Statements
Optimal computation of prefix sums on a binary tree of processors (English)
0 references
1987
0 references
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.
0 references
parallel computation
0 references
recursive doubling
0 references
model of computation
0 references
inverse perfect shuffle
0 references
binary tree of processors
0 references
optimal-cost algorithm
0 references
job scheduling
0 references
deadlines
0 references
knapsack problem
0 references