The parallel complexity of integer prefix summation

DOI10.1016/0020-0190(95)00119-WMaRDI QIDQ1350241zbMATH OpenWikidataFDO

Authors Torben Hagerup

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Parallel algorithmsConcurrent writingCRCW PRAMsPrefix summation

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• An Improved Parallel Prefix Sums Algorithm
• The complexity of parallel prefix problems on small domains
• Publication:3128883
• New lower bounds for parallel computation

Cites work

• scientific article; zbMATH DE number 4090816 (Why is no real title available?)
• Faster optimal parallel prefix sums and list ranking
• Limits on the power of concurrent-write parallel machines
• New lower bounds for parallel computation
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Optimal bounds for decision problems on the CRCW PRAM
• Parallel computation with threshold functions
• The Parallel Simplicity of Compaction and Chaining
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(9)

• scientific article; zbMATH DE number 4170913 (Why is no real title available?)
• An Improved Parallel Prefix Sums Algorithm
• scientific article; zbMATH DE number 3982516 (Why is no real title available?)
• \(k\)-block parallel addition versus 1-block parallel addition in non-standard numeration systems
• A sound and complete abstraction for reasoning about parallel prefix sums
• scientific article; zbMATH DE number 6479070 (Why is no real title available?)
• THE COMPLEXITY OF COMPUTING PARTIAL SUMS OFF-LINE
• The complexity of parallel prefix problems on small domains
• A class of almost-optimal size-independent parallel prefix circuits

This page was built for publication: The parallel complexity of integer prefix summation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1350241)