$1$ Background

The microprocessor cache has a set of flag bits. We have used only one so far, the valid bit which

indicates if a row is in use. There are other bits: ${?}^1$

Least recently used bit$($s$)($LRU$).$ Some bits used as meta data to determine which is the

oldest block in the row. This determine which block gets evicted during a capacity miss.

Dirty bit. In multi$-$level caches, the dirty bit indicates if the current cache level has a modified

version of a block that is inconsistent with lower cache levels $($and the virtual memory$).$

Here is an example of a $2-$way set associative cache with the flag bits described above:

In this assignment we will distinguish between load and store operations. Store operations

introduce a complication: if a change is made to a block how do you update all levels of cache $($and

the virtual memory$)?$ The simplest approach is called write$-$through, where on a store operation

the entire processor stalls as the block is copied into the L$1,$ L$2,$ etc. and the virtual memory. This

costs as much time as a hit, and is sub$-$optimal.

Instead, modern microprocessors use a technique called write$-$back. When a block is written,

you only change the value in the L$1$ cache, and set the dirty bit. The change is not copied into the

L$2$ or virtual memory. This means that with write$-$back, values written to memory are inconsistent

across all cache levels $($and the virtual memory$).$ If a block with a dirty bit is evicted from a row the

change is pushed down one level below. The value is updated in the lower level making it consistent,

and setting the dirty bit in the lower level.

For example, if you initialize $i=0,$ this change is only written to the level one cache$-$the value

of $i$ is garbage or unknown in all other cache levels and the virtual memory. If somehow the block

containing the concept of $i=0$ is evicted from the level one cache due to a capacity miss we note

that its dirty bit was set during the store operation. Then, the concept of $i=0$ is pushed to the level

two cache $($but not any lower$)$ and the dirty bit is set. If again, the concept of $i=0$ gets evicted

from the level two cache the process repeats. The change is pushed to a lower level. This created

an unusual phenomenon where variables in primary storage $($virtual memory$)$ are totally different

than the values the processor is using.

At a glance, you can see that this would resolve the issue from the last problem of the last

activity, you would not need to juggle the values in row $00,$ it could hold both values. Real numbers

for set associativity range from $4$ to $16.$

$2$ Direct Instruction

The instructor will review these examples in class:

A system has two cache levels. The L$1$ cache has $4$ rows. The L$2$ cache has $8$ rows. Both

caches are two$-$way set associative and the block size is $8$ bytes. Ignore the LRU bit. You

must use write$-$back methodology. Profile the following memory requests to the cache:

$($a$)$ Store $i=0$ to $100010100000$

$($b$)$ Store $j=1$ to $100010000000$

$($c$)$ Store $i=1$ to $100010100000$

$($d$)$ Store $k=20$ to $111111100000$

$3$ Activity

A system has two cache levels. The L$1$ cache has $4$ rows. The L$2$ cache has $3$ rows. Both

caches are $2-$way set associative and the block size is $16$ bytes. Profile the following memory

requests to the cache:

$($a$)$ Write $i=0$ to $0b1010100010110000$

$($b$)$ Write $j=1$ to $0b1010100100100000$

$($c$)$ Write $k=5$ to $0b1010101000100000$

$($d$)$ Write $1=4$ to $0b1010011100110000$

$($e$)$ Write $m=7$ to $0b1010000011010000$

$($f$)$ Write $n=10$ to $0b1010101001011000$

$($g$)$ Write $o=11$ to $0b1010111101100000$

$($h$)$ Write $p=73$ to $0b1010110010010000$

Ignore the LRU bit, and profile these requests with write$-$back methodology. Assume the

virtual memory has garbage values for these variables to start.

What are the final values of each variable in each cache level?