Optimal computation of prefix sums on a binary tree of processors
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.
- scientific article; zbMATH DE number 1304056
- An Improved Parallel Prefix Sums Algorithm
- The strict time lower bound and optimal schedules for parallel prefix with resource constraints
- Faster optimal parallel prefix sums and list ranking
- Parallel general prefix computations with geometric, algebraic, and other applications
- A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
- Binary Trees and Parallel Scheduling Algorithms
- scientific article; zbMATH DE number 3690676 (Why is no real title available?)
- scientific article; zbMATH DE number 3504426 (Why is no real title available?)
- Parallel Prefix Computation
- Parallel Solution of Recurrence Problems
- The Parallel Evaluation of General Arithmetic Expressions
- Ultracomputers
- Parallel prefix computation with few processors
- A chained-matrices approach for parallel computation of continued fractions and its applications
- Parallel algorithms for connectivity problems on interval graphs
- A local-sparing design methodology for fault-tolerant multiprocessors
- Summing up function values in parallel: A complexity analysis
- Parallel algorithms for tree accumulations
- scientific article; zbMATH DE number 17559 (Why is no real title available?)
- scientific article; zbMATH DE number 1304056 (Why is no real title available?)
- Parallel newton interpolation on mesh-of-unshuffle network
- The strict time lower bound and optimal schedules for parallel prefix with resource constraints
- OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES
- Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees
- An Improved Parallel Prefix Sums Algorithm
- Optimal and efficient algorithms for summing and prefix summing on parallel machines
- Parallel general prefix computations with geometric, algebraic, and other applications
This page was built for publication: Optimal computation of prefix sums on a binary tree of processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099947)
