Concurrent Algorithms & PRAM.

Concurrent Algorithms.

As computers evolved into concurrent machines, concurrent algorithms were developed.

Concurrent Algorithms allow for more than one operation be executed at any given moment.

Concurrent Algorithms are tied to Concurrent Computation Models, such as PRAM (Parallel Random Access Machine).

Parallel Random Access Machine.

PRAM Basic Architecture.

PRAM Machine (Machine with PRAM Architecture) consits of:

- Shared Memory,
- n processors P0, P1, ... , Pn-1 connected to the same Shared Memory.

Shared Memory Speed.

How much time takes Shared Memory Access Operation?

Basicly the more of Processors competing, the more time they lose on accessing Shared Memory. Otherwise it's a constant time O(1).

Concurrent Algorithm's work time depends both on amount of data to be processed & on amount of Processors.

Memory Access Modes & Types of PRAM Machines.

We can say that there are four concurrent memory access modes:

- CR: Concurrent Read: more than one read at given moment from the same memory cell,
- ER: Exclusive Read: only one read at given moment from the same memory cell,
- CW: Concurrent Write: more than one write at given moment to the same memory cell,
- EW: Exclusive Write: only one write at given moment to the same memory cell.

We can say there are Concurrent Algorithms of Classes:


There are different PRAM machines that can handle different concurrent algorithms classes:

- EREW PRAM (simplest hardware solution, highest software writing costs),
- CRCW PRAM (most complex hardware solution, lowest software writing costs).

CRCW PRAM can handle EREW Concurrent Algorithms, but EREW PRAM can't handle directly CRCW Concurrent Algorithms.

Without additional assumptions, when multiple Processors write to the CRCW machine at the same moment, it's not determined what will be written.

In common-CRCW model, if multiple Processors write the same value to the same memory cell, they must write the same value.


PRAM Machines are fully synchronized - no Processor will execute two instructions until all Processors finalize their current instructions.

See also: [4], Distributed Shared Memory.

No comments:

Post a Comment