Faster optimal parallel prefix sums and list ranking

Richard Cole, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

Abstract

We present a parallel algorithm for the prefix sums problem which runs in time O( log n log log n) using n log log n log n processors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs in O(log n) time using n log n processors (optimal speedup).

Original languageEnglish (US)
Pages (from-to)334-352
Number of pages19
JournalInformation and Computation
Volume81
Issue number3
DOIs
StatePublished - Jun 1989

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Faster optimal parallel prefix sums and list ranking'. Together they form a unique fingerprint.

Cite this