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 ₁ 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.

Simultaneous read and write access to identical memory cells

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 .

Write access to CRCWs

In the case of a CRCW PRAM, it must still be clarified what should happen in the event of simultaneous write access when different processors want to write different values ​​to the memory cell. There are 3 modes:

• common: Only the writing of identical values ​​is allowed.
• arbitrary: A random value is selected and written.
• priority: The processor with the lowest address receives write access.

With specific algorithms, the different variations of PRAM lead to different complexities in resource consumption. The above-mentioned algorithm for maximum search is dependent on simultaneous read and write access as described, i.e. on a CRCW PRAM. A solution in constant time would not be possible on a PRAM that does not allow this. Which PRAM model you choose for a specific investigation therefore depends on the analysis goals you pursue with it.