The parallel complexity of integer prefix summation

DOI10.1016/0020-0190(95)00119-WzbMath0875.68504WikidataQ126408249 ScholiaQ126408249MaRDI QIDQ1350241

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)

Related Items

A class of almost-optimal size-independent parallel prefix circuits

Cites Work

• Limits on the power of concurrent-write parallel machines
• Parallel computation with threshold functions
• Faster optimal parallel prefix sums and list ranking
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• The Parallel Simplicity of Compaction and Chaining
• Optimal bounds for decision problems on the CRCW PRAM
• New lower bounds for parallel computation
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• Unnamed Item