Q3. A program P running on a single-processor system takes time T to complete. Let us assume that 40% of the program’s code is associated with “data management housekeeping” (according to Amdahl) and, therefore, can only execute sequentially on a single processor. Let us further assume that the rest of the program (60%) is “embarrassingly parallel” in that it can easily be divided into smaller tasks executing concurrently across multiple processors (without any interdependencies or communications among the tasks).
1. Calculate T2, T4, T8, which are the times to execute program P on two-,four-,eight-processor system respectively.
2. Calculate T∞on a system with an infinite number of processors. Calculate the speedup of the program on this system, where speedup is defined as T/T∞. What does this correspond to?
Solution: Assume single instruction takes 1 time unit to execute. As we know 40% of instructions are dependent then minimum 40 time unit will be required.
1.T2 (Time for system having 2 processors)
Processor P1 and P2 can execute program instructions simultaneously which are not independent.
P1 executes 40% instructions which are dependent. It takes 40 time unit and same time P2 can execute 40% instructions which are independent. Now removing 20% independent instructions can execute on both the processors.
T2 = 40 max(10,10)
= 50 time units (minimum)
T4 (Time for system having 4 processors)
T4 = 40 + max(3,3,2,2)
= 43 time units (minimum)
T8 (Time for system having 8 processors)
T8 = 40 + max(2,2,1,1,1,1,1,1)
= 42 time units (minimum)
2. T∞ = 40 time units
Speed up = T/T∞ defines how much the new (T∞) system is efficient S= T2/T∞ = 50/40 = 1.25 (means T∞ system type is 1.25 times efficient than T2).