Parallel Random Access Machine

As a Parallel Random Access Machine, PRAM short, refers to a machine model for the analysis of parallel algorithms. There is a register machine, which was extended to allow for parallel processing of commands. As well as in the register machine, there are several variations of the models PRAM. The all models common notion is that several registers simultaneously perform calculations and can store the result in memory cells. The PRAM is used, inter alia, in complexity theory to define the class NC of efficient parallel decidable problems.

Example of a realization

Even if register machines in the strict sense only support a very simple instruction set, equivalent to register machines can be defined, whose programs can be specified in a high level language. The parallel processing of commands can now be done through the introduction of a new statement that looks something like this:

Pardo stands for do in parallel. An example:

This statement 100 memory locations are initialized simultaneously with the value 0. x may for example, be considered as an array, the fields are indexed by 1-100. The more general notation xi sees on such implementation details. The example given is certainly not too high practical importance. So here is a meaningful example that demonstrates the performance of a PRAM well:

Given a list of n different values ​​, which are stored in the memory cells unsorted x1 to xn. We are looking for the one xi that contains the greatest value. This search is carried out on a PRIORITY CRCW PRAM (see below) that does not require activation of processors, parallel, surprisingly, for arbitrarily large n 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 is only still in bi the value 1 if xi is the maximum. In all other bj with j ≠ i, the value 0 is The one i with bi = 1 is therefore the index searched and found after the program is in m. The maximum in an unsorted list of any length n can thus in constant time, ie in O (1) time to calculate.

Different PRAM models

SIMD and MIMD - PRAM

The above-described pardo statement allows within one clock cycle, the concurrent execution of a particular command on different variables. Such parallel models are referred to as Single Instruction Multiple Data model or short SIMD. Within one clock cycle are also different commands are allowed, so it is called a Multiple Instruction Multiple Data model ( MIMD ). The pardo statement is too narrow for such a model.

Simultaneous read and write accesses to identical memory cells

It must be defined whether simultaneous read and write accesses are allowed for identical memory cells or not. The above algorithm for the peak search is needed both: In the first Pardo instruction is accessed by different processors concurrently to identical memory cells, to compare these with each other. Within the second pardo statement can be accessed according simultaneously writing to the memory cell mi. Such freedom would not always allow you. A distinction is therefore:

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

In an Erev so only one processor may, for example, each read or write access to a specific memory cell. Otherwise, it comes to a program abort.

Write accesses at CRCWs

In a CRCW PRAM still needs to be clarified what to do in case of a simultaneous write access, if different processors want to write different values ​​into the memory cell. We distinguish three modes:

  • Common: Just writing identical values ​​is allowed.
  • Arbitrary: A random value is selected and written.
  • Priority: The processor with the lowest address receives the write authorization.

The different variations of the PRAM algorithms result in concrete at different complexities in the consumption of resources. Thus, the above mentioned algorithm for maximum search as described relies on simultaneous read and write access, so on a CRCW PRAM. On a PRAM, which does not allow this, a solution would not be in constant time. Which PRAM model is selected for a particular investigation, that depends on the analysis goals that one pursues it.

  • Theoretical computer science
  • Parallel processing
Computer memory Recursive set Statement (computer science) Abort (computing) Integrated Authority File
633162
de