Computational bounds for the simple and the MRMW PRAM
Fabrizio Luccio, Linda Pagli · 2002
We define the simple PRAM, where consecutive transfers between memory and processors cannot be done in a single step. Some acclaimed "surprising" results in PRAM theory, as computing the OR of n bits in less that log/sub 2/n steps, are proved not to hold in the new model, and are replaced with more natural results. In particular, the OR can be computed in log/sub 2/n+O(1) steps, and this bound is tight. We then introduce the Multiple Read Multiple Write (MRMW) PRAM model, that allows a bounded amount of simultaneous transfers from m memory cells to one processor (MR), and vice-versa (MW), and derive exact computational bounds as a function of m. In particular, the OR can be computed in log/sub b/n steps, with b=(m+2+/spl radic/(m/sup 2/+4m))/2 for the MRMW model with consecutive transfers, and b=1+/spl radic/(m) for the simple model, and these bounds are tight.>