The complexity of parallel prefix problems on small domains

The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the pre...

Full description

Saved in:
Bibliographic Details
Main Authors: Chaudhuri, S., Radhakrishnan, J.
Format: Conference Proceeding
Language:English
Subjects:
Computer science
Concurrent computing
Joining processes
Law
Legal factors
Parallel algorithms
Phase change random access memory
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1,...,n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems.< >
DOI:10.1109/SFCS.1992.267787