| Optimal Separation of EROW and CROW PRAMs (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract We consider the problem of evaluating a booleanfunction on PRAMs. We exhibit a boolean function f: {0, 1}n! {0, 1} that can be evaluated in time O(log log n) in a deterministic CROW (ConcurrentRead Owner Write) PRAM model, but requires time \Omega (log n) in EROW (Exclusive Read Owner Write)PRAM. Our lower bound also holds in the randomized Monte Carlo EROW model. This boolean function isderived from the well-known pointer chasing problem, and was first considered by Nisan and Bar-Yossef [10].Our lower bound improves a special case of the previous result of Nisan and Bar-Yossef, who proved a lowerbound of \Omega (plog n) for this function in the deterministicEREW model (and hence in the EROW model). Our result is the first to achieve the best possible separationbetween the CROW and EROW PRAM models for functions on complete domains (boolean or nonboolean),improving the previous results ([7, 6, 10]). | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||