#import "@local/note_template:0.0.1": *

#set heading(numbering: "1.1")
#outline(indent: true)

= Cache Part

== Generit Cache Memory Organization

For a computre system where each memeory address has $m$ bits, the cache memory is organized as follows:
1. The cache memory is divided into $S=2^s$ sets, each containing $E$ lines.
2. Each line contains a block of $B=2^b$ bytes, a valid bit, a $t=m-(b+s)$ tag bits.

So, in short, $S$ sets, $E$ lines per set, $B$ bytes per block, $t$ tag bits and $m$ bits wide memory address in total. Therefore, a cache memory organization can be caracterized by the tuple $(S, E, B, m)$.

- How does all these design work? Why is cache designed like this?

When the CPU need access to an address in memory, the memory address is sent to cache. The $t$ most significant bits of the address are used to determine the tag in cacheline, and the following $s$ bits are used to determine the set in cache. The remaining $b$ bits are used to determine the offset in the block. If the valid bit is set, and the tag matches, then the data is in the cache. Otherwise, the data is not in the cache, and the CPU has to access the main memory. Following the procudure above, a memory address can be mapped to a unique cacheline, and the word can be located in the cacheline by the offset. If the word is found, it is a cache hit, otherwise, it is a cache miss.

Maybe the map from memory address to cache line will vary due to different CPUs, but the basic idea is the same.

- Why index with the middle bits?

Think about the situation that we need to traverse through a long array, if we index with the high bits, then we can only cache a block-size trunk of the array in time. In detail, let's say teh parameter $E$ is 4, so as we traverse, we can only cache 4 blocks-size of the array, causing insufficient cache usage.

