Modelling Parallel Computation and Interconnection Networks

What does a computation model abstract from a computation?

Relevant properties from the irrelevant ones.

What is a Random Access Machine (RAM)?

A sequential computation model consisting of a processing element and memory.

What does PRAM stand for?

Parallel Random Access Machine.

What are the three different ways to generalize RAM to parallel computing?

Parallel RAM (PRAM), Local Memory Machine (LMM), Modular Memory Machine (MMM).

What does EREW-PRAM stand for?

Exclusive Read Exclusive Write PRAM.

What is a key feature of EREW-PRAM?

It does not support simultaneous access to the same memory location.

What does CREW-PRAM allow?

Simultaneous reads from the same memory location but exclusive writes.

What is a notable characteristic of CRCW-PRAM?

Supports simultaneous reads and simultaneous writes to the same memory location.

How does Consistent CRCW-PRAM handle simultaneous writes?

It allows PEs to write to the same memory location if they write the same value.

What happens in Abstract CRCW-PRAM with simultaneous writes?

Only one PE's write will succeed, and it is unpredictable which one it will be.

What is the priority order in Priority CRCW-PRAM?

A predefined order determining which PE's write will succeed during simultaneous writes.

What type of operations does Fusion CRCW-PRAM assume for writing?

Operations that are associative and commutative, like sum, product, max, min, logical AND, and logical OR.

What is a unique feature of Local Memory Machine (LMM) regarding memory access?

Each processing element has its own local memory and can quickly access it.

Describe the Modular Memory Machine (MMM).

It has no local memory to processing elements.