PRAM models classification

Written by Abhishek Ghosh

Various PRAM models differ in how they handle read or write conflicts; i.e, when two or more processors attempt to read from, or write to, the same global memory location. Listed below are the different types of PRAM models.

1. EREW ( Exclusive Read Exclusive Write ) : Read or write conflicts are not allowed.

2. CREW ( Concurrent Read Exclusive Write ) : Concurrent reading allowed; i.e, multiple processors may read from the same global memory location during the same instruction step. Write conflicts are not allowed (This is the default PRAM model).

3. CRCW (Concurrent Read Concurrent Write ) : Concurrent reading and concurrent writing allowed. A variety of CRCW models exists with different policies for handling concurrent writes to the same global address. Three different models are :

a. COMMON :
All processors concurrently writing into the same global address must be writing the same value.

b. ARBITRARY :
If multiple processors concurrently write to the same global address, one of the competing processors is arbitrarily chosen as the 'winner'  and its value is written into the register.

c. PRIORITY :
If multiple processors concurrently write to the same global address, the processor with the lowest index succeeds in writing its value into the memory location.

The EREW PRAM model is the weakest.Clearly a CREW PRAM model can execute any EREW PRAM algorithm in the same amount of time; the concurrent read facility is simply not used. Similarly, a CRCW PRAM can execute any EREW PRAM algorithm in the same amount of time.

The PRIORITY PRAM model is the strongest. Any algorithm designed for the common PRAM model will execute with the same complexity on the ARBITRARY PRAM and the PRIORITY PRAM models as well, for if all processors writing to the same location write the same value, chossing an arbitrary processor would cause the same result.