Clyde P. Kruskal, Larry Rudolph, Marc Snir

Research output: Chapter in Book/Report/Conference proceedingConference contribution


An O((log n/log(2n/p)) (n/p) time, deterministic, parallel algorithm using p less than equivalent to n processors to solve the parallel prefix problem, when the order is specified by a linked list. For p less than equivalent to O(n+ZZ epsilon ) ( epsilon less than 0 any constant), this algorithm achieves linear speedup. Such optimal speedup was previously achieved only by probabilistic algorithms. These algorithms assume the weakest PRAM model, where shared memory locations can only be exclusively read or written (the EREW model).

Original languageEnglish (US)
Title of host publicationProceedings of the International Conference on Parallel Processing
EditorsDouglas DeGroot
Number of pages6
ISBN (Print)0818606371
StatePublished - Dec 1 1985

Publication series

NameProceedings of the International Conference on Parallel Processing
ISSN (Print)0190-3918

ASJC Scopus subject areas

  • Hardware and Architecture

Fingerprint Dive into the research topics of 'POWER OF PARALLEL PREFIX.'. Together they form a unique fingerprint.

Cite this