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