__
TR95-004 | 1st January 1995 00:00
__

#### Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write PRAMs

TR95-004
Authors:

Martin Dietzfelbinger,

Miroslaw Kutylowski,

RĂ¼diger Reischuk
Publication: 1st January 1995 00:00

Downloads: 1981

Keywords:

addition,

Boolean circuits,

Boolean formulas,

Boolean Functions,

concurrent-read,

exclusive-read,

exclusive-write,

parallel prefix,

parallel random-access machine,

parallel time complexity,

parity,

sorting,

symmetric functions
**Abstract:**

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 f(n) = 0.72 log n.

On the other hand, it is known that every Boolean function of n

arguments can be computed in f(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 f(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,\ldots ,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 f(2^d)+o(d) = 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.86 log n steps.