EECC756 - Shaaban #39 lec # 3 Spring2008 3-20-2008 Amdahl's Law Example: A Pictorial Depiction Amdahl's Law Example: 2-Phase n-by-n Grid Computation A Pictorial Depiction 1 p 1 p 1 n 2 /p n2n2 p work done concurrently n2n2 n2n2 Time n 2 /p (c) (b) (a) Phase 1Phase 2 Sequential Execution Parallel Execution on p processors Phase 1: time reduced by p Phase 2: sequential Parallel Execution on p processors Phase 1: time reduced by p Phase 2: divided into two steps (see previous slide) 1 0.5 p + 0.5 Speedup= 2n 2 2n 2 + p 2 Speedup= Maximum Possible Speedup = 2 s= 0.5 1 1/p + p/2n 2 = For large n Speedup ~ p
{}