@inproceedings{09fcda4b144b49c99839ed375460c21c,

title = "POWER OF PARALLEL PREFIX.",

abstract = "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).",

author = "Kruskal, {Clyde P.} and Larry Rudolph and Marc Snir",

year = "1985",

language = "English (US)",

isbn = "0818606371",

series = "Proceedings of the International Conference on Parallel Processing",

publisher = "IEEE",

pages = "180--185",

editor = "Douglas DeGroot",

booktitle = "Proceedings of the International Conference on Parallel Processing",

}