Caches

The main goal of caches is to increase the performance of a computer through the memory system in order to:

Provide the user the illusion to use a memory that is simultaneously large and fast
Provide the data to the processor at high frequency

For this reason two principles are exploited:

Temporal Locality: when there is a reference to one memory element, the trend is to refer again to the same memory element soon (i.e., instruction and data reused in loop bodies)
Spatial Locality: when there is a reference to one memory element, the trend is to refer soon at other memory elements whose addresses are close by (i.e., sequence of instructions or accesses to data organized as arrays or matrices)

The resulting memory hierarchy is composed of several levels (main memory + levels of cache).

If the requested data is found in one of the cache blocks (upper level) then there is a hit in the cache access. If the requested data is not found in in one of the cache blocks (upper level) then there is a miss in the cache access. In case of a data miss, we need to:

Stall the CPU
Require to block from the main memory
Copy (write) the block in cache
Repeat the cache access (hit)

Performance metrics

Hit Rate: number of memory accesses that find the data in the upper level with respect to the total number of memory accesses.

$$\text{Hit Rate} = \frac{\text{hits}}{\text{memory accesses}}$$

Hit Time: time to access the data in the upper level of the hierarchy, including the time needed to decide if the attempt of access will result in a hit or miss.

Miss Rate: number of memory accesses that do not find the data in the upper level with respect to the total number of memory accesses. Note that $\text{Hit Rate} + \text{Miss Rate} = 1$.

$$\text{Miss Rate} = \frac{\text{misses}}{\text{memory accesses}}$$

Miss Penalty: time needed to access the lower level and to replace the block in the upper level.

Miss Time: time needed to access a block wihich is not in the cache.

$$\text{Miss Time} = \text{Hit Time} + \text{Miss Penalty}$$

Average Memory Access Time

$$AMAT = \text{Hit Rate} \times \text{Miss Time} + \text{Miss Rate} \times \text{Miss Time}$$ $$AMAT = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$$

Cache structure

Each entry in the cache includes:

Valid bit to indicate if this position contains valid data or not. At the bootstrap, all the entries in the cache are marked as INVALID.
Cache Tag contains the value that univocally identifies the memory address corresponding to the stored data.
Cache Data contains a copy of data (block or cache line)

Block placement strategies

Given the address of the block in the main memory, where the block can be placed in the cache (upper level)?

We need to find the correspondence between the memory address of the block and the cache address of the block.

1) Direct Mapped Cache

Each memory location corresponds to one and only one cache location. The cache address of the block is given by: $$lol$$ $$\text{Block Address}{\text{cache}} = \text{Block Address}{\text{mem}} \bmod \text{Num. of Cache Blocks}$$