Lower Bounds for Randomized Exclusive Write PRAMs |
| |
Authors: | P D MacKenzie |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, Boise State University, Boise, ID 83725, USA philmac@cs.idbsu.edu, US |
| |
Abstract: | In this paper we study the question: How useful is randomization in speeding up Exclusive Write PRAM computations? Our results
give further evidence that randomization is of limited use in these types of computations. First we examine a compaction problem
on both the CREW and EREW PRAM models, and we present randomized lower bounds which match the best deterministic lower bounds
known. (For the CREW PRAM model, the lower bound is asymptotically optimal.) These are the first nontrivial randomized lower
bounds known for the compaction problem on these models. We show that our lower bounds also apply to the problem of approximate
compaction. Next we examine the problem of computing boolean functions on the CREW PRAM model, and we present a randomized
lower bound which improves on the previous best randomized lower bound for many boolean functions, including the OR function.
(The previous lower bounds for these functions were asymptotically optimal, but we improve the constant multiplicative factor.)
We also give an alternate proof for the randomized lower bound on PARITY, which was already optimal to within a constant additive
factor. Lastly, we give a randomized lower bound for integer merging on an EREW PRAM which matches the best deterministic
lower bound known. In all our proofs, we use the Random Adversary method, which has previously only been used for proving
lower bounds on models with Concurrent Write capabilities. Thus this paper also serves to illustrate the power and generality
of this method for proving parallel randomized lower bounds.
Received October 2, 1995, and in final form January 29, 1997. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|