FEASIBLE TIME-OPTIMAL ALGORITHMS FOR BOOLEAN FUNCTIONS ON EXCLUSIVE-WRITE PARALLEL RANDOM-ACCESS MACHINES

It was shown some years ago that. the computation time for many import ant Boolean functions of n arguments on concurrent-read exclusive-writ e parallel random-access machines (CREW PRAMs) of unlimited size is at least rho(n) approximate to 0.72log(2) n. On the other hand, it is kn own that every Boolean function of n arguments can be computed in rho( n) fl steps on a CREW PRAM with n . 2(n-1) processors and memory cells . In the case of the OR of a bits, n processors and cells are sufficie nt. In this paper, it is shown that for many important functions, ther e are CREW PRAM algorithms that almost meet the lower bound in that th ey take rho(n)+ o(logn) steps but use only a small number of processor s and memory cells (in most cases, a). In addition, the cells only hav e to store binary words of bounded length (in most cases, length 1). W e call such algorithms ''feasible.'' The functions concerned include t he following: the PARITY function and, more generally, all symmetric f unctions; a large class of Boolean formulas; some functions over non-B oolean domains {0,..., k - 1} for small k, in particular, parallel-pre fix sums; addition of n-bit numbers; and sorting n/l binary numbers of length l. Further, it is shown that Boolean circuits with fan-in 2, d epth d, and size s can be evaluated by CREW PRAMs with fewer than s pr ocessors in rho(2(d)) + o(d) approximate to 0.72d + old) steps. For th e exclusive-read exclusive-write (EREW) PRAM model, a feasible algorit hm is described that computes PARITY of a bits in 0.86 log(2) n steps.