What is PRAM Model: PRAM stands for parallel random access machine ( Generally Parallel random access memory) which is the extension of RAM model for sequential algorithm. PRAM is a model, which is considered for the use of parallel computation named parallel algorithms.
In PRAM model multiple processors are attached to a single block of memory called global memory. In the above block diagram of PRAM model of parallel computation, p number of processors can perform independent operations on p number of data in a particular unit of time. This may result in simultaneous access of same memory location by different processors. A PRAM model consist the following−
- PRAM model consist a finite set of similar type of processors. Every processor has a unique index which is used to enable or disable the processor. This unique index number identifies which memory location accesses by a processor. These unbounded set of processors have their own private memory for local data store.
- PRAM model consist a common memory unit called global memory or shared memory. Every processor in PRAM shares this common memory unit. Processors can communicate among themselves through the shared memory only.
- PRAM model consist of a control unit to control the instruction fetched by all processors in PRAM model.
- A memory access unit (MAU) is connects the processors with the single shared memory.
- PRAM processors have a read, compute and write phases that happen synchronously.
PRAM instruction execute in three phase cycle:
- Read instruction execution:
- Local computation:
- Write instruction execution:
Steps involved in PRAM computation:
- A PRAM computation begins with a single active processing elements and the input stored in global memory.
- During each step of computation an active enabled process may read a value from single private or global memory location. Perform a single RAM operation and write into one local or global memory location.
- During computation step processors have a special activation register that specifying the maximum index of an active processor. Initially, only the first processor is in active mode, it computes the number of required active processors and loads this register, and then the other corresponding processors start executing their programs. The computation will proceeds until the first processor halts, at which time all other active processors are halted.
The cost of PRAM computation is the product of parallel time of algorithm complexity and numbers of processors used under. The parallel time complexity is equal to the time elapsed in executing all the instruction simultaneously. i.e.;
Cost of PRAM computation = Parallel time complexity × Number of processors used
Also Check: Digital Logic circuits
The space complexity of PRAM model is equal to the number of shared memory cells accessed.
Features of PRAM model:
To design parallel algorithm PRAM is an attractive and important model because of its features as follows;
- PRAM model is natural: The number of operations executed per one cycle on p processors is at most p.
- PRAM model is strong: any processor can read or write any shared memory cell in unit time.
- PRAM model is simple: It abstracts from any communication or synchronization overhead, which makes the complexity and correctness analysis of PRAM algorithms easier. Therefore, It can be used as a benchmark: If a problem has no feasible/efficient solution on PRAM, it has no feasible/efficient solution on any parallel machine.
- PRAM model is useful: It is an idealization of existing (and nowaday more and more abundant) shared memory parallel machines.
Constrained on PRAM Model:
Bounded number of shared memory cells: This may be called a small memory PRAM. If the input data set or set of instruction exceeds the capacity of the shared memory then the input and/or output values of shared memory cells can be distributed evenly among the processors.
Bounded size of a machine word and/or memory cell: The parameter of memory cell in PRAM model is presenting the size of a machine word.
Bounded number of processors: If the number of threads of execution is higher, processors may interleave several threads sometime it named as a small PRAM.
Constraints on simultaneous access to shared memory cells: It is based on handling the memory access conflicts.
The limited amount of PRAM global memory unit corresponds to restricting the amount of information that can be communicated between processors in single step. For example, in a distributed memory machine with processors interconnected by a shared bus can be modeled as a PRAM with one shared memory cell.
