Bridging the Gap

The purpose of cache is to bridge the speed gap between memory and the CPU. CPU instructions execute in less than a nanosecond, while memory-access latency ranges from a dozen to several dozen nanoseconds. For a single memory access, the CPU must therefore wait for dozens or even hundreds of clock cycles, severely reducing the overall efficiency of the system. However, memory is slow only in terms of latency; from a bandwidth perspective, it can meet the CPU’s requirements. Introducing a fast storage medium with a somewhat smaller capacity can hide this latency. Specifically, before the CPU executes a memory-access instruction, the required data is loaded from memory into cache. By the time the CPU reaches that instruction, the data is already in cache and can therefore be accessed with latency on the same order of magnitude as CPU execution.


Three Typical Organizational Forms

When the CPU issues a memory-access instruction, how can it determine whether the data at the target address is present in cache? This is a question of cache organization. A cache can usually be understood as a table in which each entry records the data from a block of memory and the starting address of that block. Such an entry is called a cache line. Within a given system, the amount of data stored in a cache line—that is, the size of the memory block—is usually fixed, meaning that every cache line has the same length. On x86 systems, this size is 64 Bytes. This is also normally the amount of data obtained in a single DDR memory access. A cache line must record not only the data but also its corresponding address, and it usually records only part of that address. For example, in a 32-bit system with 64-Byte cache lines, only the upper 32 – 6 = 26 bits need to be recorded. The 5 here comes from 2^6=64.

How can an address be used to look up whether the cache has a hit? The simplest method is to compare the address against the tag of the first line in the cache. A match is a hit; if none matches, it is a miss. Cache lookup cannot be slow, so these one-by-one comparisons must be performed in parallel by hardware. This approach (Approach 1) results in extremely complex hardware.


Fully Associative Cache

Ideally, given an address, we would know which line in the cache might hold it. We could then examine that line: if its tag matches, it is a hit; otherwise, it is a miss. One feasible method is to take the memory address modulo the total number of cache lines. The result is the target cache line number, and data from each memory address is allowed to reside only in that target line. For now, call this Approach 2. A significant problem with Approach 2 is that data from a given memory address can reside only in a fixed cache line. If two addresses produce the same result after the modulo operation, one of them cannot be stored; even if other cache lines are empty, they cannot be used, potentially resulting in poor space utilization. Approach 1 does not have this limitation: as long as the cache still has unused space, there is no need to evict a cache line.

Direct-Mapped Cache

The cache shown has 8 lines, each 16 bytes in size. For a given memory address, its lowest 4 bits are not useful for retrieving data from the cache. The upper 28 bits are what actually matter. Taking these 28 bits modulo the number of cache lines produces a value that is precisely the lowest 3 bits among those 28 bits. The diagram therefore uses these lower 3 bits as the index to select a line from the cache. The selected line may contain the target memory data, may be empty, or may contain memory data from another similar address—one with the same lower 3 bits. After the line has been selected, the upper 25 bits must therefore be compared with the tag to determine whether the selected data belongs to the target memory block.


Meaning of a Direct-Mapped Cache Address

Approach 1 and Approach 2 are two extremes. Approach 1 is called a fully associative cache: every memory address can be associated with any cache line. Approach 2 is called a direct-mapped cache: every memory address maps directly to a particular cache line and cannot occupy another cache line.

For Approach 2, because it is not very likely that multiple memory addresses mapping to the same cache line will be accessed at the same time, an optimization can be made: several shadow lines are introduced for each cache line. For example, if one original cache line is now expanded into 4 cache lines, no eviction occurs as long as no more than 4 memory addresses mapping to that line are in use during the same period. This organization, in which one memory address corresponds to a set of several cache lines, is called an n-way set-associative cache.


Two-Way Set-Associative Cache (2-way associative 8-entry cache)