Faster optimal parallel prefix sums and list ranking
Richard Cole, Uzi Vishkin · Information and Computation · 1989
We present a parallel algorithm for the prefix sums problem which runs in timeO( logn/log logn) usingnlog logn/lognprocessors (optimal speedup). This algorithm leads to a parallel list ranking algorithm which runs inO(logn) time usingn/lognprocessors (optimal speedup).