Optimal computation of prefix sums on a binary tree of processors

DOI10.1007/BF01379098zbMath0639.68032MaRDI QIDQ1099947

Selim G. Akl, Henk G. Meijer

Publication date: 1987

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

zbMATH Keywords

parallel computationknapsack problemdeadlinesjob schedulingmodel 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)

Related Items (7)

A chained-matrices approach for parallel computation of continued fractions and its applications ⋮ Parallel algorithms for connectivity problems on interval graphs ⋮ OPTIMAL PARALLEL PREFIX ON MESH ARCHITECTURES ⋮ Parallel newton interpolation on mesh-of-unshuffle network ⋮ A local-sparing design methodology for fault-tolerant multiprocessors ⋮ Parallel general prefix computations with geometric, algebraic, and other applications ⋮ Parallel prefix computation with few processors

Cites Work

• Unnamed Item
• Unnamed Item
• Binary Trees and Parallel Scheduling Algorithms
• Parallel Prefix Computation
• Ultracomputers
• Parallel Solution of Recurrence Problems
• The Parallel Evaluation of General Arithmetic Expressions
• A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equations

This page was built for publication: Optimal computation of prefix sums on a binary tree of processors