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).
ASJC Scopus subject areas
- Theoretical Computer Science
- Information Systems
- Computer Science Applications
- Computational Theory and Mathematics