title: ExampleAssume a memory consists of $2^{14}$ words and each block has $8$ words.1. How many blocks does main memory have? $$ \text{blocks} = \frac{\text{number of words}}{\text{block size}} = \frac{2^{14}}{2^3} = 2^{11} $$2. How many bits does an address have? We need to uniquely identify every word in the system. $$ \text{bits} = \lceil \log_2 (2^{14}) \rceil = 14 \text{ bits} $$3. What are the field sizes of the address? $11$ bits to identify block, $3$ bits for the offset.
Financial cost can be a limitation to creating the most efficient computer system. Memory can typical have a small size and low latency or a large size and high latency.
Naive approach: Exposed Hierarchy
One naive approach to memory hierarchy is to have all the memory components exposed to the processor. It is then the programmer’s responsibility to decide where to store data.
Problems include that it requires complex load and store instructions in the instruction set. Programs will be competing against each other.
Better approach: implicit memory hierarchy
Complexities of the memory are hidden from the processor. The hardware handles whether data is stored in fast or slow memory depending on usage patterns.
The processor will see fast memory as long as hardware keeps the required data within the cache. But the processor needs to handle different latencies on the fly (sometimes data will come in fast, sometimes slow)
The processor sends an access request for a particular address to the cache. If we get a cache hit then the data for the address is in the cache and we can immediately return it.
If we get a cache miss then the data for the address is not in the cache, so the request is passed to the main memory (causing high latency), the memory returns data to the processor via the cache. We can choose to retain this data using a number of strategies including spacial locality, temporal locality, and sequential locality.
Effective Access Time
Hit ratio
Hit ratio is the fraction of hits to total attempts, $HR = \frac{\text{hits}}{\text{hits} + \text{misses}}$.
With cache, access can also be overlapped: the cache is checked in parallel with checking main memory. If the address is not found in the cache, there is slightly less of a penalty. However, this requires more advanced hardware and more power. With overlapped access, the effective access time becomes:
title: Example 1
title: Example 2
Instead of placing memory blocks in specific cache locations based on memory address, in a fully-associative cache, we can allow a block to go anywhere in cache.
A fully-associative cache address is composed of two fields:
?
the tag field: the block of main memory
the offset field: the position of the word within the block
In fully-associative caches, we may have to search the entire cache to find a particular tag which is an expensive process. In a direct-mapped cache, the search is fast as there is only one location where a particular address can be stored, so there is no search needed.
However, direct-mapped cache is overly rigid. Say the addresses were 000000 then 110000 then 000000 then 110000. In this case, the addresses map to different memory blocks but the same cache block.
We would be constantly removing and adding the same blocks to the cache (thrashing) even though we are only accessing two blocks which is an expensive process.
title: Example 1
title: Example 2
title: Example 3
With associative caches, a replacement policy is required when deciding which block to remove from a **full cache**. The block to be removed is called the **victim block**.
In most domains, the optimal replacement policy is not possible.
LRU
If we want to optimise for temporal locality we will want to kepe the most recently used blocks in the cache and remove blocks that have not been used for a long time.
We can use least-recently used (LRU) algorithm to keep track of the last time each cache block was accessed. The victim block is then the block which has been unused for the longest period of time. The LRU algorithm is complex; we have to maintain an access history for each block.
FIFO
A First-In First-Out (FIFO) policy is a popular and simple cache replacement policy. The block that has been in cache the longest is the victim block.
There is still a small overhead of keeping track of when things were added.
Random
A random policy is where we select a victim block at random and replace it with a new block. There is no overhead but we are equally as likely to remove the best and worst blocks.
