The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
Martin Dietzfelbinger, Miroslaw Kutylowski, Rudiger Reischuk,
Pages. 1196-1230
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 $varphi(n)approx 0.72log_2 n$. On the other hand, it is known that every Boolean function of $n$ arguments can be computed in $varphi(n)+1$ steps on a CREW PRAM with $ncdot 2^{n-1}$ processors and memory cells. In the case of the OR of $n$ bits, $n$ processors and cells are sufficient that 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 $varphi(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 following: the PARITY function and,
more generally, all symmetric functions; a large class of Boolean formulas; some functions over non-Boolean domains
${0,cdots,k-1}$ for small $k$, in particular, parallel-prefix 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, depth $d$, and size a can be evaluated by CREW PRAMs with fewer than $s$ processors in $varphi(2^d)+o(d)approx 0.72 d+o(d)$ steps. For the exclusive-read exclusive-write (EREW) PRAM model, a feasible algorithm is described that computes PARITY of $n$ bits in 0.86$log_2 n$ steps.
Contents 1. Introduction
1.1. Motivation
1.2. Lower and upper bounds
1.3. Results
2. Preliminaries
3. Fast computating of PARITY on EREW PRAMs
4. A time-optimal CREW algorithm for PARITY with subexponentially many processors
5. Fast formula and circuit evaluation by CREW PRAMs with a linear number of processors
6. Many-valued formulas and circuits
7. Parallel prefix and addition
8. Symmetric functions
9. Sorting algorithms
Key words parallel random-access machine, exclusive-write, concurrent-read, exclusive-read, parallel time complexity, Boolean functions, Boolean formulas, Boolean circuits, symmetric functions, parallel prefix, parity, addition, sorting.
Mathmatical Subject Classification 68Q10, 68Q05, 68Q25