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.