Derive Amdahl's law starting from the expression execution_time_old overall_speedup = ------------------ execution_time_new +----------+---------+ | 1-f | f | execution_time_old = T*[ (1-f) + f ] = T +----------+---------+ . . . . . s . s is the speedup of a fraction f of . . . program execution time . . . +----------+-----+ | 1-f | f/s | execution_time_new = T*[ (1-f) + f/s ] +----------+-----+ T 1 overall_speedup = ----------------- = --------------- T*[ (1-f) + f/s ] [ (1-f) + f/s ] law of diminishing returns +--------+--------+ | .5 | .5 | time = .5 + .5 = 1 +--------+--------+ . . . . . s . speedup of 1000 infinite speedup . . . +--------+-+ | | | time = .5 + .5/1000 = .505 .5 + 0 = .5 +--------+-+ overall speedup = 1/.505 1/.5 >> overall_speedup limited to 1/(1-f) << must work on on speeding up both parts Consider memory access time. If a cache is ten times faster than main memory, and if the cache can be used 90% of the time, what overall speedup in memory access time do we gain by using the cache? overall_speedup = 1/[ (1-f) + f/s ] = 1/[ (1-.9) + .9/10 ] = 1/[ .1 + .09 ] = 1/.19 = 5.26 Consider enhancing a scalar machine by providing a vector mode. When a computation is run in vector mode it is 16 times faster than the normal mode of operation. What percent of vectorization is needed to achieve an overall speedup of 4? overall_speedup = 1/[ (1-f) + f/s ] 4 = 1/[ (1-f) + f/16 ] so f = ? Consider the following instruction mix IC_i / IC CPI_i operation frequency cycle count weighted CPI_i --------- --------- ----------- -------------- ALU op 50% 1 _____ Loads 20% 2 _____ Stores 10% 3 _____ Branches 20% 4 _____ average CPI (sum of weighted CPI_i's) _____ avg CPI = .5*1 + .2*2 + .1*3 + .2*4 = _____ If Branch cycles are reduced to 2, do you have enough information to determine how much faster the modified processor will be than the original processor? CPU_time_old IC * CPI_old * CCT CPI_old speedup = ------------ = ------------------ = ------- CPU_time_new IC * CPI_new * CCT CPI_new IC_i / IC CPI_i operation frequency cycle count weighted CPI_i --------- --------- ----------- -------------- ALU op 50% 1 _____ Loads 20% 2 _____ Stores 10% 3 _____ Branches 20% 2 _____ average CPI (sum of weighted CPI_i's) _____ avg CPI = .5*1 + .2*2 + .1*3 + .2*2 = _____ CPI_old speedup = ------- = ------ = _____ CPI_new Show this same result by Amdahl's law overall_speedup = 1/[ (1-f) + f/s ] s is 2, f is ? instruction count Given MIPS = ---------------------, find MIPS in terms of clock rate and CPI. execution time * 10^6