Cache Technology
1. The Basic Principle of the Cache
The Principle of Locality
Temporal locality:
- A program tends to access the same data repeatedly
- Data that was recently accessed is likely to be accessed again
- Exploiting temporal locality raises the hit rate
Spatial locality:
- A program tends to access adjacent data
- After accessing one item, the items next to it are likely to be accessed
- Exploiting spatial locality raises the hit rate
How the Cache Works
The basic concept:
- Places a high-speed cache between the CPU and the main memory
- Stores recently accessed data
- Reduces the number of accesses to the main memory
The working process:
- The CPU issues an access request
- The lookup happens in the cache first
- On a hit, the data is returned directly
- On a miss, the data is fetched from the main memory
The Cache Performance Metrics
The hit rate:
- Hits / total accesses
- Reflects how effective the cache is
- Goal: raise the hit rate
The access time:
- On a hit: the cache access time
- On a miss: the main memory access time
- Goal: reduce the average access time
The cache efficiency:
- Average access time = hit rate × cache time + (1 - hit rate) × main memory time
- Reflects the overall performance improvement
2. The Mapping Schemes of the Cache
Direct Mapping
The basic principle:
- The main memory address is divided into blocks according to the cache size
- Each main memory block can only map to a fixed position in the cache
- The mapping relation: cache line number = main memory block number mod the number of cache lines
The address structure:
- Tag bits: identify the main memory block
- Line number: the address of the cache line
- Block offset: the byte address within the block
Characteristics:
- Advantages: simple to implement, fast to access
- Disadvantages: a high conflict rate and a low hit rate
- Applications: small caches
Fully Associative Mapping
The basic principle:
- A main memory block can map to any position in the cache
- The tags of all the cache lines have to be compared
- A completely free mapping relation
The address structure:
- Tag bits: the complete main memory address
- Block offset: the byte address within the block
Characteristics:
- Advantages: a low conflict rate and a high hit rate
- Disadvantages: complex to implement, slow to access
- Applications: small caches
Set Associative Mapping
The basic principle:
- Divides the cache into a number of sets
- A main memory block maps to any line within a fixed set
- Combines the advantages of direct mapping and full associativity
The address structure:
- Tag bits: identify the main memory block
- Set number: the address of the cache set
- Block offset: the byte address within the block
Characteristics:
- Advantages: a moderate conflict rate and a fairly high hit rate
- Disadvantages: moderate implementation complexity
- Applications: most caches
3. The Replacement Algorithms of the Cache
FIFO (First In First Out)
The basic principle:
- The block that entered the cache first is replaced first
- Manages the cache lines in time order
- Ignores how often the blocks are accessed
The implementation:
- A queue records the order of entry
- On a replacement the head of the queue is chosen
- New data is appended to the tail of the queue
Characteristics:
- Advantages: simple to implement
- Disadvantages: ignores the access pattern
- Applications: the cases with a uniform access pattern
LRU (Least Recently Used)
The basic principle:
- The block that has not been accessed for the longest time is replaced first
- Records the access time of every block
- Keeps the recently accessed blocks in preference
The implementation:
- A counter records the access time
- The counter is updated on every access
- On a replacement the block with the smallest counter is chosen
Characteristics:
- Advantages: a fairly high hit rate
- Disadvantages: complex to implement
- Applications: most applications
LFU (Least Frequently Used)
The basic principle:
- The block that has been accessed the fewest times is replaced first
- Records the number of accesses of every block
- Keeps the frequently accessed blocks in preference
The implementation:
- A counter records the number of accesses
- The counter is incremented on every access
- On a replacement the block with the smallest counter is chosen
Characteristics:
- Advantages: suits the cases where the access frequencies differ a lot
- Disadvantages: cannot reflect the most recent accesses
- Applications: the cases with a stable access pattern
The CLOCK Algorithm
The basic principle:
- Combines the advantages of LRU and FIFO
- Uses a reference bit to mark the access state
- Scans in a circle to choose the block to replace
The implementation:
- Every cache line has a reference bit
- The reference bit is set to 1 on access
- On a replacement the lines are scanned, the reference bits are cleared, and the block with a reference bit of 0 is chosen
Characteristics:
- Advantages: comparatively simple to implement, with a good effect
- Disadvantages: not as precise as LRU
- Applications: medium-sized caches
4. The Write Policies of the Cache
Write-Through
The basic principle:
- Writes to the cache and to the main memory at the same time
- Guarantees the consistency of the data
- The main memory always holds the most recent data
Characteristics:
- Advantages: good data consistency
- Disadvantages: the write operation is slow
- Applications: the cases that demand a high level of consistency
Write-Back
The basic principle:
- Writes only to the cache and does not write to the main memory immediately
- Uses a dirty bit to mark the modification state
- Writes back to the main memory only on replacement
Characteristics:
- Advantages: the write operation is fast
- Disadvantages: the data consistency is complex
- Applications: most modern caches
Write-Allocate
The basic principle:
- On a write miss, fetches the data block first
- Then modifies the data in the cache
- Used together with the write-back policy
Characteristics:
- Advantages: raises the hit rate of the later accesses
- Disadvantages: adds the overhead of the write miss
- Applications: the cases with good spatial locality
Write-No-Allocate
The basic principle:
- On a write miss, writes straight to the main memory
- Does not fetch the data block into the cache
- Used together with the write-through policy
Characteristics:
- Advantages: reduces cache pollution
- Disadvantages: may lower the hit rate
- Applications: the cases with random write accesses
5. Multilevel Caches
The Two-Level Cache Structure
L1 cache:
- Small in capacity, fast
- Integrated with the CPU
- Separates the instruction cache from the data cache
L2 cache:
- Relatively large in capacity, relatively slow
- A unified cache
- Compensates for the shortcomings of the L1 cache
The Advantages of a Multilevel Cache
Performance improvement:
- Reduces the average access time
- Raises the overall hit rate
- Lowers the frequency of the accesses to the main memory
Cost control:
- Allocates the storage resources sensibly
- Lowers the overall cost
- Meets the performance requirements
Exercise 1
What are the three mapping schemes of the cache?
Approach: Take the three schemes in turn, giving for each how a main memory block is placed, the mapping relation, and the trade-off between the conflict rate and the hardware cost.
Steps:
- Direct mapping:
- A main memory block maps to a fixed position in the cache
- The mapping relation: cache line number = main memory block number mod the number of cache lines
- Advantages: simple to implement, fast to access
- Disadvantages: a high conflict rate and a low hit rate
- Fully associative mapping:
- A main memory block can map to any position in the cache
- The tags of all the cache lines have to be compared
- Advantages: a low conflict rate and a high hit rate
- Disadvantages: complex to implement, slow to access
- Set associative mapping:
- A main memory block maps to any line within a fixed set
- Combines the advantages of direct mapping and full associativity
- Advantages: a moderate conflict rate and a fairly high hit rate
- Disadvantages: moderate implementation complexity
Answer: The three mapping schemes are direct mapping, in which each main memory block maps to a fixed cache line according to cache line number = main memory block number mod the number of cache lines, which is the simplest and the fastest but suffers from a high conflict rate; full associative mapping, in which a block may map anywhere and all the tags have to be compared, which gives the lowest conflict rate and the highest hit rate at the cost of slow access; and set associative mapping, in which a block maps to any line of a fixed set, which combines the advantages of the two and is what most caches use.
Exercise 2
What is the basic principle of virtual memory? What are the common page replacement algorithms?
Approach: Answer the two halves of the question separately: first the principle, in three layers — the concept, the working mechanism, and the advantages — and then the four replacement algorithms with the rule each one uses and the trade-off it makes.
Steps:
- The basic principle of virtual memory:
- The basic concept:
- Extends the external storage space into main memory space
- A program can address a space larger than the physical memory
- Automates the memory management
- The working principle:
- The program uses virtual addresses
- The physical address is obtained by address translation
- The pages are brought into memory on demand
- The advantages:
- Enlarges the address space
- Raises the memory utilisation
- Simplifies program development
- The basic concept:
- The common page replacement algorithms:
- OPT (the optimal algorithm):
- Chooses the page that will not be used for the longest time in the future
- Theoretically optimal, but impossible to implement in practice
- FIFO (first in first out):
- Chooses the page that entered the memory first
- Simple to implement, with a mediocre effect
- LRU (least recently used):
- Chooses the page that has not been accessed for the longest time
- A good effect, but complex to implement
- The CLOCK algorithm:
- Combines the advantages of LRU and FIFO
- Uses a reference bit and scans in a circle
- Comparatively simple to implement, with a good effect
- OPT (the optimal algorithm):
Answer: Virtual memory extends the external storage into the main memory space, so a program can address more than the physical memory holds, the virtual addresses are translated into physical addresses through a page or segment table, and the pages are brought in on demand; the result is a larger address space, better memory utilisation, and simpler program development. The common page replacement algorithms are OPT, which evicts the page that will not be used for the longest time and is theoretically optimal but unrealisable; FIFO, which evicts the page that entered first and is simple but only moderately effective; LRU, which evicts the page that has not been used for the longest time and works well but is complex; and CLOCK, which uses a reference bit and a circular scan to combine the strengths of LRU and FIFO at a comparatively low implementation cost.
| Term | Abbreviation | Explanation |
|---|---|---|
| Cache | - | The high-speed cache between the CPU and the main memory |
| Hit rate | - | The proportion of the cache accesses that hit |
| Miss rate | - | The proportion of the cache accesses that miss |
| Hit time | - | The time taken by a cache access that hits |
| Miss penalty | - | The extra overhead incurred on a cache miss |
| Average Memory Access Time | AMAT | The average time per memory access |
| Direct mapping | - | Each main memory block maps to a fixed cache line |
| Fully associative mapping | - | A main memory block may map to any cache line |
| Set associative mapping | - | A main memory block maps to any line of a fixed set |
| Replacement algorithm | - | The algorithm that picks the line to replace when the cache is full |
| First In First Out | FIFO | The earliest entry is replaced first |
| Least Recently Used | LRU | The least recently used block is replaced first |
| Least Frequently Used | LFU | The least frequently used block is replaced first |
| Clock algorithm | - | A circular scan that approximates LRU |
| Write through | - | Writes the cache and the main memory at the same time |
| Write back | - | Writes only the cache and writes back on replacement |
| Write allocate | - | Fetches the block into the cache on a write miss |
| Write no allocate | - | Writes straight to the main memory on a write miss |
| Multilevel cache | - | The L1/L2/L3 multilevel caching |
| Split cache | - | The instruction cache and the data cache are separated |
| Unified cache | - | A cache shared by the instructions and the data |
| Cache line / block | - | The basic storage unit of a cache |
| Valid bit | - | Marks whether the cache line is valid |
| Tag bit | - | Identifies the address of the main memory block |
| Dirty bit | - | Marks whether the cache line has been modified |