T1: PRAM Model: All Basics

February 06, 2025

• Basic three types of PRAM
• Lower bounds
  • CREW RRAM
  • EREW
• Reference

Previously, I know PRAM model. But I cannot like it. It is an old model and it is also hard to read the old e-books. Recently, I found the beauty of this model. Then, I found I am into this model. Humanity is mysterious.

This post will show the basics of PRAM model.

Basic three types of PRAM

1. EREW: Exclusive Read Exclusive Write PRAM: no two processors can read/write the same shared memory cell.
2. CREW: Concurrent Read Exclusive Write PRAM: simultaneous read is allowed, but only one processor can write.

3. CRCW: All processor can simultaneously read and write.

          +-------------------------+
          |      Input Data          |
          +-------------------------+
                         |
                         v
          +-------------------------+
          |    Shared Memory         |
          +-------------------------+
            /|\                /|\
             |                  |
       +-------------+     +-------------+
       | Processor 1 |     | Processor P |
       +-------------+     +-------------+
   

Lower bounds

Let $f(x_1,\ldots,x_n)$ be a Boolean function with $n$ inputs. We shall use the notation $I = x_1,\ldots, x_n$ to denote the input $(x_1,\ldots, x_n)$ and $I(i)$ to denote the input $I$ whose $i$-th component is complemented. An input $I$ is critical if and only if $f(I) \neq f(I(i))$ for $1\leq i \leq n$.

CREW RRAM

$\textbf{Theorem 1}$. Let $f: \{0,1 \}^n \to \{0, 1\}$ have a critical input. The $\Omega(\log n)$ time is required to compute any $f$ on CREW PRAM with any number of processors, which includes the following functions:

1. Sorting a sequence
2. Computing the sum
3. Computing the maximum

EREW

$\textbf{Theorem 2}$. Given a monotonic binary sequence of length $n$, the problem of finding the number of zeros requires $\Omega(\log n - \log p)$ time in CREW PRAM model with $p$ processors.

Reference

[1]. JáJá, J., 1992. Parallel algorithms.