RAM model of serial computation and the PRAM model of parallel computation.

on

RAM model

Random Access Machine is a favorite model of a sequential computer. Its main features are:
  1. Computation unit with a user defined program.
  2. Read-only input tape and write-only output tape.
  3. Unbounded number of local memory cells.
  4. Each memory cell is capable of holding an integer of unbounded size.
  5. Instruction set includes operations for moving data between memory cells, comparisons and conditional branches, and simple arithmetic operations.
  6. Execution starts with the first instruction and ends when a HALT instruction is executed.
  7. All operations take unit time regardless of the lengths of operands.
  8. Time complexity = the number of instructions executed.
  9. Space complexity = the number of memory cells accessed.

PRAM model

Parallel Random Access Machine is a straightforward and natural generalization of RAM. It is an idealized model of a shared memory SIMD machine. Its main features are:
  1. Unbounded collection of numbered RAM processors P0, P1, P2,... (without tapes).
  2. Unbounded collection of shared memory cells M[0], M[1], M[2],....
  3. Each Pi has its own (unbounded) local memory (registers) and knows its index i.
  4. Each processor can access any shared memory cell (unless there is an access conflict, see further) in unit time.
  5. Input af a PRAM algorithm consists of n items stored in (usually the first) n shared memory cells.
  6. Output of a PRAM algorithm consists of n' items stored in n' shared memory cells.
  7. PRAM instructions execute in 3-phase cycles.
    1. Read (if any) from a shared memory cell.
    2. Local computation (if any).
    3. Write (if any) to a shared memory cell.
  8. Processors execute these 3-phase PRAM instructions synchronously.
  9. Special assumptions have to be made about R-R and W-W shared memory access conflicts.
  10. The only way processors can exchange data is by writing into and reading from memory cells.
  11. P0 has a special activation register specifying the maximum index of an active processor. Initially, only P0 is active, it computes the number of required active processors and loads this register, and then the other corresponding processors start executing their programs.
  12. Parallel time complexity = the time elapsed for P0's computation.
  13. Space complexity = the number of shared memory cells accessed.

Comments

Post a Comment