Reminder: This post contains 1444 words
· 5 min read
· by Xianbin
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
- EREW: Exclusive Read Exclusive Write PRAM: no two processors can read/write the same shared memory cell.
- CREW: Concurrent Read Exclusive Write PRAM: simultaneous read is allowed, but only one processor can write.
-
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:
- Sorting a sequence
- Computing the sum
- 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.