In the previous activity we learned how to use a single cache level to profile requests to the memory. Today we

will learn two new concepts: cache levels and set$-$associative caches. The processor has many cache levels that are

progressively larger in size. If a row hits capacity and a block is lost, there is a chance it will still be contained in a

lower level of the cache. The general for for any cache level i is this:

$1.$ The input to the cache level is a request for an aligned memory address$\mathrm{.}1$

$2.$ Go to the appropriate row, check the valid bit, and check if the tag matches.

$($a$)$ If the valid bit is zero, it is a miss cold start. Push the request to a lower level.

$($b$)$ If the tag is mismatched, it is a miss. If there are no free blocks it is a capacity miss. Push the request to

a lower level.

$($c$)$ If the tag matches, it is a hit. Return the block in this row up to a higher level.

The levels of a cache are generally:

$1.$ Level $1($L$1).$ In practice, there are two level $1$ caches, one for instructions and one for data. For our assignments

we will have a single L$1$ to keep things simple.

$2.$ L$2$

$3.$ L$3.$ In practice, this level is shared across multiple logical processors, but this will not come into play for our

assignments because we only work with a single logical processor.

$4.$ The virtual memory.

The processor starts on level $1$ and works its way down.

n$-$way Set Associative Cache With the last question on the last activity, we experienced a major flaw in our

direct$-$mapped cache design. You worked out an example where the cache kept juggling the block in and out of row

$00.$ Each time it is a miss, this means it had to go to a lower level. The simplest way to address this is to have each

row hold multiple blocks. For example, with a direct$-$mapped cache, if you think about it in terms of a tuple:

$\{$Row$,$ Tag, v$,$ Data$\}(1)$

Where v is the valid bit. We can extend this notation so that each row holds n blocks:

$\{$Row$,$ Tag$0$

$,$ v$0,$ Data$0,$ Tag$1$

$,$ v$1,$ Data$1,...,$ Tagn, vn$,$ Datan, $\}(2)$

Note that since the row is the key, we do not need to duplicate it$.$ With this new notation we can hold n blocks. We

call this an n$-$way set$-$associative cache. For example, if n $=2,$ the table would look like:

Row Tag $0$ Valid $0$ Data $0$ Tag $1$ Valid $1$ Data $1$

$00$

$01$

$10$

$11$

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.$ The instructor will review these examples in class:

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

set associative and the block size is $16$ bytes. Profile the following memory requests to the cache:

$($a$)0$b$0111111000110000$

$($b$)0$b$0011010011111100$

$($c$)0$b$0111111000110000$

$($d$)0$b$0011010011111000$

$3$ Activity

$1.$ A system has two cache levels. The L$1$ cache has $4$ rows. The L$2$ cache has $3$ rows. Both caches are directmapped and the block size is $16$ bytes. Profile the following memory requests to the cache:

$($a$)0$b$1010100010110000$

$($b$)0$b$1010100100100000$

$($c$)0$b$1010101000100100$

$($d$)0$b$1010011100110100$

$($e$)0$b$1010000011010000$

$($f$)0$b$1010101001011000$

$($g$)0$b$1010111101100100$

$($h$)0$b$1010110010010100$