Metrics and Evaluations/Problem06

Memory operations currently take 30% of execution time.

  • A new widget called a “cache” speeds up 80% of memory operations by a factor of 4
  • A second new widget called a “L2 cache” speeds up 1/2 the remaining 20% by a factor or 2.

    What is the total speed up?

Solution

Amdahls's Law Reminder You cannot trivially apply optimizations one at a time with Amdahl’s law.

Multiple optimizations: The WRONG way

Just the L1 cache

 S1 = 4

 x1 = .8*.3

 Stotal_L1 = 1/(x1/S1 + (1-x1))

 Stotal_L1 = 1/(0.8*0.3/4 + (1-(0.8*0.3))) = 1/(0.06 + 0.76) = 1.2195 times

Just the L2 cache

 SL2 = 2

 xL2 = 0.3*(1 - 0.8)/2 = 0.03

 Stotal_L2’ = 1/(0.03/2 + (1-0.03)) = 1/(.015 + .97) = 1.015times

Combine

 Stotal_L2 = Stotal_L2’ * Stotal_L1 = 1.02*1.21 = 1.237  <- *This is wrong!*

What’s wrong? — after we do the L1 cache, the execution time changes, so the fraction of execution that the L2 effects actually grows

Multiple optimizations: The right way

We can apply the law for multiple optimizations

Optimization 1 speeds up x1 of the program by S1

Optimization 2 speeds up x2 of the program by S2

Stotal = 1/(x1/S1 + x2/S2 + (1-x1-x2))

Note that x1 and x2 must be disjoint! i.e., S1 and S2 must not apply to the same portion of execution. If not then, treat the overlap as a separate portion of execution and measure it’s speed up independently.

Combine both the L1 and the L2

 memory operations = 0.3

 SL1 = 4

 xL1 = 0.3*0.8 = .24

 SL2 = 2

 xL2 = 0.3*(1 - 0.8)/2 = 0.03

 StotalL2 = 1/(xL1/SLl + xL2/SL2 + (1 - xL1 - xL2))

 StotalL2 = 1/(0.24/4 + 0.03/2 + (1-.24-0.03)) = 1/(0.06+0.015+.73)) = 1.24 times

Screen Shot 2014-03-31 at 2.59.07 PM.png

This problem is adapted from the UCSD CS141 lecture notes