Abstract: Limitations of the QRQW and EREW PRAM Models


Miroslaw Kutylowski Krzysztof Lorys


We consider parallel random  access  machines  (PRAMs)  with  restricted
access to the shared memory resulting from handling congestion of memory
requests. We study the (SIMD) QRQW PRAM model  where  multiple  requests
are  queued  and serviced one at a time. We also consider exclusive read
exclusive write (EREW) PRAM and its modification obtained  by  adding  a
single bus.

For the QRQW PRAMs we investigate the case when the machine can  measure
the  duration  of  a  single  step. Even for such a (powerful) QRQW PRAM
PARITY of n bits requires logarithmic time while OR of  n  bits  can  be
computed  deterministically  in a constant time. On randomized QRQW PRAM
PARITY of n bits is still difficult. We prove  a  lower  time  bound  of
linear  in  square  root of log(n)/loglog(n) for algorithms that succeed
with probability greater than 0.5. These bounds show  that  implementing
concurrent writes may degradate runtime of a CRCW PRAM algorithm.

The simple 2-compaction problem is known to be hard for EREW  PRAM.  The
same  time  bound  (linear in square root of log n) for this problem has
been proved for both deterministic and randomized  EREW  PRAM.  We  show
that this is not a coincidence since the time complexity of this problem
is the same for deterministic and randomized case. The  technique  which
we  apply is quite general and may be used to obtain similar results for
any problem where the number of input configurations is small.

We also prove that improving the known time bound  for  2-compaction  on
EREW PRAM requires novel and more sophisticated techniques.


Appeared in Proceedings of the 16th Conference on Software Technology 
and Theoretical Computer Science (FSTTCS'96), pp. 310-321, Hyderabad, 
India, December 18 - 20, 1996. LNCS 1180, Springer-Verlag, Berlin