Feasible Time-Optimal Algorithms for Boolean Functions
on Exclusive-Write PRAMs
Martin Dietzfelbinger, Miroslaw Kutylowski, Ruediger Reischuk
It was shown some years ago that the computation time for many important
Boolean functions of $n$ arguments on concurrent-read exclusive-write
parallel random-access machines (CREW PRAMs) of unlimited size is at
least phi(n) or approximately 0.72log n. On the other hand, it is known
that every Boolean function of n arguments can be computed in phi(n)+1
steps on a CREW PRAM with n 2^{n-1} processors and memory cells. In the
case of the OR of n bits, n processors and cells are sufficient. In this
paper it is shown that for many important functions there are CREW PRAM
algorithms that almost meet the lower bound in that they take phi(n) +
o(log n) steps, but use only a small number of processors and memory
cells (in most cases, n$. In addition, the cells only have to store
binary words of bounded length (in most cases, length 1). We call such
algorithms ``feasible''. The functions concerned include:
-- the PARITY function and, more generally,
all symmetric functions;
-- a large class
of Boolean formulas;
-- some functions over
non-Boolean domains {0, ... ,k-1} for small k, in particular
parallel prefix sums;
-- addition of n-bit-numbers;
-- sorting n/l binary numbers
of length l.
Further, it is shown that Boolean circuits with fan-in 2, depth d, and
size s can be evaluated by CREW PRAMs with fewer than s processors in
phi(2^d)+o(d) or approximately 0.72d+ o(d) steps. For the exclusive-read
exclusive-write model (EREW PRAM) a feasible algorithm is described that
computes PARITY of n bits in 0.86log_2 n steps.