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 #

Block Offset

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.

Tag

Block Offset

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.

Tag

Cache Set #

Block Offset

Several factors should be kept in mind when choosing the read policy:

Block conflict rate
Cache utilization
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
Cache utilization Low Medium High
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:

  1. Write-through + write-around
  2. 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,

Conclusion

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.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.