Optimal computation of prefix sums on a binary tree of processors

DOI10.1007/BF01379098MaRDI QIDQ1099947zbMATH OpenFDO

Authors Selim G. Akl, Henk Meijer

Publication date 1987

Published in International Journal of Parallel Programming (Search for Journal in Brave)

zbMATH Keywords

knapsack problemparallel computationjob schedulingdeadlinesmodel of computationrecursive doublingbinary tree of processorsinverse perfect shuffleoptimal-cost algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Recommendations

• 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

Cites work

• scientific article; zbMATH DE number 3690676 (Why is no real title available?)
• scientific article; zbMATH DE number 3504426 (Why is no real title available?)
• A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations
• Binary Trees and Parallel Scheduling Algorithms
• Parallel Prefix Computation
• Parallel Solution of Recurrence Problems
• The Parallel Evaluation of General Arithmetic Expressions
• Ultracomputers

Cited in

(13)

• An Improved Parallel Prefix Sums Algorithm
• Parallel prefix computation with few processors
• Parallel general prefix computations with geometric, algebraic, and other applications
• The strict time lower bound and optimal schedules for parallel prefix with resource constraints
• A chained-matrices approach for parallel computation of continued fractions and its applications
• A local-sparing design methodology for fault-tolerant multiprocessors
• OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES
• scientific article; zbMATH DE number 17559 (Why is no real title available?)
• Parallel algorithms for tree accumulations
• Parallel newton interpolation on mesh-of-unshuffle network
• Parallel algorithms for connectivity problems on interval graphs
• Optimal and efficient algorithms for summing and prefix summing on parallel machines
• Minimizing roundoff errors of prefix sums via dynamic construction of Huffman trees

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)