15-05-2013, 04:09 PM
PRAM MODEL
[attachment=53954]
Introduction
Pram model is Parallel Random Access machine model, where there are n number of processors working synchronously.
Fast processing and immediate result is the need of our day-to-day life.
Parallel method of computation evolved due to shortfalls in sequential processing which was unable to solve problems with huge calculations in short amount of time.
Structure of Pram Model
PRAM consists of N number of processors and each processor is itself a RAM.
Each processor has its own local memory and along with it they also share a same memory.
Each processor is given a unique id.
Execution takes over a global clock.
Communication between processors
Processors within Pram communicate in two unit time.
One processor writes to the shared memory in the first step, while in the second step second processor reads through the same memory location.
Memory location is to be specified by the user.
Strength of Models
These models have different strengths, like,
All CRCW’s
CREW
EREW
Program written for the lower model definitely runs on a higher model, just that the extra features don’t run.
Work and Efficiency
The work done by an algorithm, let it be sequential or parallel, to be the product of p*t, where p is the no of processors while t is the running time.
Same algorithm may require different number of processors, the work done in such case can be measured by ∑ i*ti, ti is the time during which exactly i processors are active.
Efficiency ‘Ep’= S(n)/p*Tp.
Ep lies between 0 and 1.
Speed-Up
Speed-up can be defined as the ratio of run time of the best known sequential algorithm to that of parallel algorithm with p processors.
Speed-up= ‘S’ = S(n)/T(n, p), where S(n) is the run time for best known sequential algorithm while T(n, p) is run time for parallel algorithm of size n and p processors.
If S is equal to p, then the speed-up is linear.
A parallel algorithm is work optimal only if the speed-up is linear.
Conclusion
Pram model is used for parallel computation of the algorithms.
Parallel algorithms provide quick results than the sequential algorithms.
[attachment=53954]
Introduction
Pram model is Parallel Random Access machine model, where there are n number of processors working synchronously.
Fast processing and immediate result is the need of our day-to-day life.
Parallel method of computation evolved due to shortfalls in sequential processing which was unable to solve problems with huge calculations in short amount of time.
Structure of Pram Model
PRAM consists of N number of processors and each processor is itself a RAM.
Each processor has its own local memory and along with it they also share a same memory.
Each processor is given a unique id.
Execution takes over a global clock.
Communication between processors
Processors within Pram communicate in two unit time.
One processor writes to the shared memory in the first step, while in the second step second processor reads through the same memory location.
Memory location is to be specified by the user.
Strength of Models
These models have different strengths, like,
All CRCW’s
CREW
EREW
Program written for the lower model definitely runs on a higher model, just that the extra features don’t run.
Work and Efficiency
The work done by an algorithm, let it be sequential or parallel, to be the product of p*t, where p is the no of processors while t is the running time.
Same algorithm may require different number of processors, the work done in such case can be measured by ∑ i*ti, ti is the time during which exactly i processors are active.
Efficiency ‘Ep’= S(n)/p*Tp.
Ep lies between 0 and 1.
Speed-Up
Speed-up can be defined as the ratio of run time of the best known sequential algorithm to that of parallel algorithm with p processors.
Speed-up= ‘S’ = S(n)/T(n, p), where S(n) is the run time for best known sequential algorithm while T(n, p) is run time for parallel algorithm of size n and p processors.
If S is equal to p, then the speed-up is linear.
A parallel algorithm is work optimal only if the speed-up is linear.
Conclusion
Pram model is used for parallel computation of the algorithms.
Parallel algorithms provide quick results than the sequential algorithms.