# Parallel random access machine

In computer science, a parallel random access machine , or PRAM for short , is a machine for analyzing parallel algorithms . It is a register machine that has been expanded to include the ability to process commands in parallel. As with all register machine models, there are different variations of the PRAM. The idea common to all models is that several registers can perform calculations at the same time and store the result in memory cells . The PRAM serves u. a. in complexity theory for the definition of the class NC of efficiently parallel decidable problems.

## Example of a realization

Even if register machines in the narrower sense only support a very simple set of instructions , equivalent register machines can be defined whose programs can be specified in a high-level programming language . The parallel processing of commands can now be done by introducing a new statement that looks something like this:

for <condition> pardo <instructions>

pardo stands for do in parallel . An example:

for i = 1 to 100 pardo x i  : = 0

This instruction initializes 100 memory locations with the value 0 at the same time. For example, x can be thought of as an array with fields indexed from 1 to 100. The more general notation x i does not include such implementation details . The example given is of course not of great practical importance. So here is a more sensible example that demonstrates the capabilities of a PRAM well:

A list of n different values ​​is given, which are stored unsorted in the memory cells x 1 to x n . We look for that x i that contains the greatest value. Surprisingly, this search can be carried out in parallel on a PRIORITY-CRCW-PRAM (see below), which does not require activation of the processors, for n of any size in constant time :

```for i=1 to n pardo
bi := 1
for i,j=1 to n pardo
if xj > xi
then
bi := 0
fi
for i=1 to n pardo
if bi = 1
then
m := i
fi
```

After the second for loop, b i only has the value 1 if x i is the maximum. All other b j with j ≠ i have the value 0. The i with b i = 1 is therefore the index sought and can be found in after executing the program `m`. The maximum in an unsorted list of any length n can therefore be calculated with constant effort, i.e. in O (1) time.

## Different PRAM models

### SIMD and MIMD PRAMs

The pardo instruction described above enables the simultaneous execution of a certain instruction on different variables within a time cycle . Such parallel models are known as single instruction multiple data models or SIMD for short . If different commands are allowed within a time cycle, this is referred to as a multiple instruction multiple data model ( MIMD ). The pardo statement is too narrowly defined for such a model.

It must be defined whether simultaneous read and write access to identical memory cells should be permitted or not. The above algorithm for maximum search requires both: Within the second pardo instruction, identical memory cells x i are accessed simultaneously by different processors in order to compare them with one another, and memory cell b i is simultaneously accessed for writing . You don't always want to allow such freedoms. A distinction is therefore made:

• CRCW PRAM: Concurrent Read, Concurrent Write - simultaneous read and write access possible
• CREW PRAM: Concurrent Read, Exclusive Write - simultaneous read access, but only exclusive write access allowed
• EREW PRAM: Exclusive Read, Exclusive Write - only exclusive read and write access allowed
• ERCW PRAM: Exclusive Read, Concurrent Write - exclusive read, but simultaneous write access allowed

In the case of an EREW, for example, only one processor may have read or write access to a specific memory cell. Otherwise the program will be terminated .