# 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
``````

This problem is adapted from the UCSD CS141 lecture notes