Fig.IBM's Blue Gene/P massively parallel supercomputer.
Q.1 Define Speedup, efficiency, cost of parallel system.
Speedup :
> Speedup measures increase in running time due to parallelism
> No. of PEs = n
> Based on running time :
Speedup S= Ts/Tp where
Ts = Execution Time on single processor, using fastest known sequential algorithm
Tp = Execution Time using parallel processor i.e.
Efficiency
Cost
Cost = parallel running time x number of processors
> Also called “Algorithm cost” for clarity
> Parallel algorithm whose cost is big-oh of running time of optimal sequential algorithm is called “Cost optimal”
Q.2. Explain cost optimal algorithm for addition of n numbers on p processors where p <<n.
Steps :
- Distribute n/p elements to p PEs.
- Each processor adds n/p elements locally in O(n/p).
- Propagate partial sums up a logical binary tree of PEs in O(log p).
Parallel Runtime :
As long as n=O(plogp), Cost is O(n) which is same as serial runtime. Hence Cost-Optimal.
Fig. cost optimal way of adding 16 numbers using 4 PEs
