In terms of implementation, there are different design choices of cache design, among which the most important are cache read policy, write policy and replacement policy.
Cache Read Policy
Cache can be direct mapped, fully associative, and set-associative.
For direct mapped cache, a cache block can only be placed in one specific location, determined by cache block number, and the system address can be partitioned in the following way. In this case, cache only stores the tag along with data of the whole cache block.
|Tag||Cache Block #||
For fully associative cache, a cache block can be placed anywhere in the cache, and the system address can be partitioned in the following way. In this case, cache stores the tag as well as the cache block data.
A set-associative cache is something in between direct mapped cache and fully associative cache. Cache is partitioned in sets, and a cache block can only be placed in one specific set. However, each set can have multiple ways, and ways are fully associative, thus a cache block can be stored anywhere within a set. The system address can be partitioned in the following way. Again, cache stores the tag as well as the cache block data.
|Cache Set #||
Several factors should be kept in mind when choosing the read policy:
Block conflict rate
Control logic complexity
Cache access speed
The table below shows the comparison of different read policies:
|Direct Mapped||Set Associative||Fully Associative|
|Block conflict rate||High||Medium||Low|
|Control logic complexity||Low||Medium||High|
|Cache access time||Low||Medium||High|
Cache Write Policy
There are 2 types of write policies on a cache hit: write-through and write back. Write-through cache will update both cache and main memory on a cache hit, while write-back cache will update main memory only when a cache block is evicted.
Write-back cache has lower requirement for memory bandwidth and cache-memory bus bandwidth, and it is faster on a write hit since there is no need to wait for main memory update; write-through cache simplifies the I/O because main memory is always up-to-date, but cache hit penalty is the same as miss penalty, introducing more complexed scheduling and replacement.
There are 2 types of write policies on a cache miss: no-write-allocate / write-around, and write-allocate. Write-around cache will only update main memory on a cache miss, while write-allocate cache will update main memory and fetch the cache block in cache.
Usually, the combinations are:
- Write-through + write-around
- Write-back + write allocate
The first combination makes sense: even if there are subsequent writes to the same block, the write must still go to the main memory. The second combination is in hope that subsequent write to the same block can be “captured” by cache.
Cache Replacement Policy
As we discussed in previous post, cache is limited in size, and “conflict” can cause a cache block eviction. The goal of cache replacement policy is, to identify and predict which cache block will not be needed in the future. Note cache replacement policy is not applicable to direct mapped cache, since each cache block has a fixed location in direct mapped cache.
Replacement policies include random, least frequently used / LFU, least recently used / LRU, FIFO order, etc.
Random replacement picks a victim at random. It is a simple and fast implementation, but it is equally likely to replace a useful block as a useless block.
LRU picks victim that is accessed least recently. It takes advantages of temporal locality, but it is complexed in implementation.
LFU picks victim that is accessed least frequently. It helps with cache performance, but it is also complexed in implementation since it needs to keep access count for each block.
FIFO order picks the oldest block as victim, and it approximates LRU with simpler hardware,
In this post, we have covered different cache read policies, write policies and replacement policies, and summarized pros and cons for these design choices. Although it is straightforward, we recommend interviewees keep these basic concepts in mind.