PRAM model and its variations

The purpose of the theoretical models for parallel computation is to give frameworks by which we can describe and analyze algorithms. These ideal models are used to obtain performance bounds and complexity estimates. The parallel random access machine (PRAM) model has been used extensively. The PRAM model was introduced by Fortune and Wyllie in 1978 for modeling idealized parallel computers in which communication cost and synchronization overhead are negligible.

A PRAM consists of a control unit, a global memory shared by $p$ processors, each of which has a unique index as follows: $P_1$, $P_2$, ..., $P_p$. In addition to the global memory via which the processors can communicate, each processor has its own private memory. The $p$ processors operate on a synchronized read, compute, and write cycle. During a computational step, an active processor may read a data value from a memory location, perform a single operation, and finally write back the result into a memory location. Active processors must execute the same instruction, generally, on different data. Hence, this model is sometimes called the shared memory, single instruction, multiple data (SM SIMD) machine.

Algorithms are assumed to run without interference as long as only one memory access is permitted at a time. We say that PRAM guarantees atomic access to data located in shared memory. An operation is considered to be atomic if it is completed in its entirety or it is not performed at all (all or nothing).

There are different modes for read and write operations in a PRAM. These different modes are summarized as follows:

1. Exclusive read (ER): Only one processor can read from any memory location at a time.

2. Exclusive write (EW): Only one processor can write to any memory location at a time.

3. Concurrent read (CR): Multiple processors can read from the same memory location simultaneously