| One, Two, Three... Infinity: (2008) | |||||||||||||
Abstract | |||||||||||||
| In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRI-ORITY PRAM. These models d%er in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds. We consider PRAM’s with n processors, each having arbitrary computational power. We provide the Brst separation results between these two models in two extreme cases: when the size m of the shared memory is small (m 5 nc, c < I), and when it is infinite. In the cue of small memory, the PRIORITY model can be faster than the COMMON model by a factor of 9(logn), and this lower bound holds even if the COMMON model is probabilistic. In the case of infinite memorv, the gap between the models can be a Support for this reseucb wu provided by am IBM Faculty | |||||||||||||
Details der Publikation | |||||||||||||
| |||||||||||||