Modelling Parallel Computation and Interconnection Networks

A computation model abstracts relevant properties of a computation from the irrelevant ones.

Random access machine (RAM) is a sequential computation model. It consists of:

1.A processing element (PE) (or processing unit (PU))

2.A memory

PRAM

A natural extension of RAM to parallel computation consists of multiple processing elements and a global memory of unbounded size that is uniformly accessible to all PEs.

The generalization of RAM to parallel computing can be done in 3 different ways:

1)Parallel RAM (PRAM)

2)Local memory machine (LMM)

3)Modular memory machine (MMM

Types of PRAM:

1)Exclusive read exclusive write PRAM (EREW-PRAM): It does not support simultaneous access to the same memory location - any access to any memory location must be exclusive.

2)Concurrent read exclusive write PRAM (CREW-PRAM): Allows simultaneous reads from the same memory location, but writing to a memory location must be exclusive.

3)Concurrent read concurrent write (CRCW-PRAM): Supports simultaneous reads from the same memory location; simultaneous writes to the same memory location, and simultaneous reads and writes to the same memory location

CRCW-PRAM: The unpredictability is handled in different ways:

1)Consistent CRCW-PRAM: PEs may simultaneously write to the same memory location, but they need to write the same value;

2)Abstract CRCW-PRAM: PEs may simultaneously try to write to the same memory location (not necessarily the same value), but only one of them will succeed, and it is unpredictable which one will succeed.

3)Priority CRCW-PRAM: There is a priority order imposed on PEs.

4)Fusion CRCW-PRAM: PEs may simultaneously try to write to the same memory location, but it is assumed that a particular operation is first performed on fly, and only the result of such operation will be written. Such operation should be associative and commutative, which includes sum, product, max, min, and logical AND and logical OR

Note that the restriction of simultaneous access is relaxed from EREW-PRAM, to CREW-PRAM, and to CRCW-PRAM.

This leads to some power gain from EREW-PRAM to CRCW-PRAM gradually, but not much, it is only in the order of logarithms

LMM and MMM

LMM: Each PE has its own local memory; accessing such memory is fast; A PE can access non-local memory via interconnect network

MMM: No local memory to PEs;