Optimal computation of prefix sums on a binary tree of processors (Q1099947): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Binary Trees and Parallel Scheduling Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel Solution of Recurrence Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel Prefix Computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Ultracomputers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4085214 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Parallel Evaluation of General Arithmetic Expressions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3885184 / rank | |||
Normal rank |
Latest revision as of 16:30, 18 June 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
0 references