Parallel Computing

Page 1

Exercises – Parallel Computing and Availability 18 / 6 / 2013 1. Exercise: Amdahl Law (1) A program requires 100 sec on a single core architecture, and its sequential fraction is about 1%. How long will it take when executed on a 10 core system? Which is its speed-up? Its efficiency when executed on 100 processors? Solution: S10= 10 / (10 x 0.01 + .99) = 10/1.09 = 9.174 T10= T1/ S10= 100 / 9.174 = 10.9 s E10= 9.174 / 10 = 91.7% S100= 100 / (100 x 0.01 + .99) = 100 / 1.99 = 50.25 T100= T1/ S100= 100/50.25 = 1.99 s E100= 50.25/100 = 50% 2. Exercise: Amdahl Law (2) A program requires 20 sec on a single processor architecture, and 11 sec on a quad-core architecture. How many core would it be required to obtain an execution time of 10 sec? Which will be the speed up and the efficiency in this case? Solution: Ts+ Tp= 20; Ts+ (Tp/4) = 11; (subtracting the two eq.) 0.75 Tp= 9; Tp= 12; Ts= 8; Ts+(Tp/ n) = 10; 8 + (12 / n) = 10; n = 12 / (10 – 8) = 6; S6= T1/ T6= 20 / 10 = 2; E6= S6/ 6 = 2 / 6 = 0.333; 3. Exercise: Amdahl Law (3) A computer program, has a serial fraction fs= 20 % , and it takes 24 hours when executed on a single system (single processor). It is necessary to deploy the software on a parallel architecture to obtain a computation time less than 6 hours. Each machine costs 5000$, and the software could be optimized to reduce its serial fraction to fs‘ = 10 % w ith an additional expense of 20 000$. There are two possibilities: (1) buy several other machines or (2) optimize the software. Which solution is more convenient? Would it be possible to reduce the computation time to 4 hours? Solution: 1) fs = 20%; Ts = 4.8; Tp = 19.2; 2) fs‘ = 10%; Ts‘ = 2.4; Tp‘ = 21.6; Objective: Ts+ (Tp/ n) = 6; n = Tp/ (6 -Ts) 1) n = 19.2 / (6 – 4.8) = 16 C = 16 x 5000$ = 80000$ (cost…