Modern processors execute instructions far faster than main memory can supply data. This disparity, often called the memory wall, means that without an intermediate buffer, the CPU would spend most of its time idle waiting for bytes to arrive. A cache solves this problem by holding frequently used data close to the processor core.
In this article, you will gain an understanding of how a cache is modeled and designed from the ground up. The discussion begins with the fundamental unit of storage, the cache line, then moves to the address breakdown that determines where data lives. By the end, you will be able to calculate the bits needed for tags, indices, and offsets, and evaluate trade-offs between direct-mapped, set-associative, and fully associative designs.
(toc) #title=(Table of Content)
What Is a Cache Line?
A cache is not an undifferentiated pool of bytes. It is organized into fixed-size units called cache lines or cache blocks. When the processor requests a single byte from memory, the cache does not fetch just that byte; it retrieves an entire block. This exploits spatial locality, the tendency of programs to access nearby addresses in sequence.
Each cache line contains several fields:
- Valid bit: Indicates whether the line holds meaningful data.
- Tag: Identifies which memory block occupies the line.
- Data: The actual cached bytes.
- Dirty bit (optional): Tracks whether the line has been modified.
- Replacement information (optional): Used by policies such as Least Recently Used (LRU).
A line without a valid bit and tag would be useless; the cache could never confirm whether the data matches the requested address.
Three Parameters That Define a Cache
Every cache design begins with three decisions:
- Cache capacity: The total amount of data the cache can hold, such as 64 KB.
- Block size: The number of bytes in one cache line, such as 32 bytes.
- Associativity: The number of locations in which a memory block may reside.
These three parameters determine the number of lines, the number of sets, and the width of each address field.
Breaking Down a CPU Address
For a direct-mapped cache, the CPU address is partitioned into three fields:
\[ \text{Address} = \text{Tag} + \text{Index} + \text{Block Offset} \]
Each field serves a distinct purpose.
Block Offset
The block offset selects the desired byte within a cache line. If the block size is 32 bytes, then:
\[ 32 = 2^5 \]
Therefore, 5 bits are required for the offset. These bits allow the processor to address any of the 32 bytes inside the block.
Index
The index identifies which cache line or set should be examined. If the cache contains 256 lines, then:
\[ 256 = 2^8 \]
Thus, 8 bits are needed for the index.
Tag
The tag distinguishes between different memory blocks that map to the same cache location. For a 32-bit address:
\[ \text{Tag} = 32 - 8 - 5 = 19 \text{ bits} \]
The tag is stored alongside the data and compared on every access.
Worked Example: Direct-Mapped Cache
Consider a processor with the following specifications:
- Address width: 32 bits
- Cache capacity: 16 KB
- Block size: 32 bytes
- Direct-mapped organization
Step 1: Number of cache lines
\[ \text{Lines} = \frac{16 \times 1024}{32} = 512 \]
Step 2: Offset bits
\[ 32 = 2^5 \Rightarrow 5 \text{ bits} \]
Step 3: Index bits
\[ 512 = 2^9 \Rightarrow 9 \text{ bits} \]
Step 4: Tag bits
\[ \text{Tag} = 32 - 9 - 5 = 18 \text{ bits} \]
The resulting address breakdown is:
| Field | Width |
|---|---|
| Tag | 18 bits |
| Index | 9 bits |
| Offset | 5 bits |
How a Cache Access Works
When the CPU issues an address, the hardware performs the following sequence:
- The index selects a cache line.
- The tag stored in that line is compared with the tag field of the address.
- If the tags match and the valid bit is set, a cache hit occurs.
- If not, a cache miss occurs, and the block must be fetched from lower memory.
The offset then selects the required byte or word from within the line.
Direct-Mapped, Set-Associative, and Fully Associative
The three cache organizations differ in where a memory block may be placed.
| Feature | Direct Mapped | Set Associative | Fully Associative |
|---|---|---|---|
| Placement | Exactly one line | One set, any way | Anywhere |
| Hardware complexity | Low | Medium | High |
| Conflict misses | Higher | Lower | Lowest |
| Lookup cost | Simple | Multiple comparisons | Many comparisons |
Direct-Mapped Cache
In a direct-mapped cache, each memory block maps to exactly one line:
\[ \text{Cache Line} = \text{Block Number} \bmod \text{Number of Lines} \]
If the cache has 8 lines, block 0 and block 8 both map to line 0. This simplicity enables fast access but causes conflict misses when two frequently used blocks compete for the same line.
Set-Associative Cache
A set-associative cache groups lines into sets. A 4-way set-associative cache allows a block to occupy any of four ways within its assigned set:
\[ \text{Set} = \text{Block Number} \bmod \text{Number of Sets} \]
The tags of all ways in the set are compared in parallel. This reduces conflict misses at the cost of additional comparators.
Fully Associative Cache
In a fully associative cache, a block may be placed anywhere. There is no index field:
\[ \text{Address} = \text{Tag} + \text{Offset} \]
The tag must be compared against every entry, which makes the hardware expensive but virtually eliminates conflict misses.
Effect of Associativity on Address Bits
Associativity changes the number of sets and therefore the index width. Consider a 16 KB cache with 32-byte blocks.
For a 4-way set-associative design:
\[ \text{Lines} = 512 \]
\[ \text{Sets} = \frac{512}{4} = 128 \]
\[ 128 = 2^7 \Rightarrow 7 \text{ index bits} \]
The offset remains 5 bits. For a 32-bit address:
\[ \text{Tag} = 32 - 7 - 5 = 20 \text{ bits} \]
Notice that the block offset never changes when associativity changes; only the index and tag widths are affected.
Cache Design Trade-Offs
Cache design is an exercise in balancing competing constraints:
- Larger capacity reduces capacity misses but increases cost and access latency.
- Larger block size exploits spatial locality but can waste bandwidth and reduce the number of lines.
- Higher associativity reduces conflict misses but increases hardware complexity and power consumption.
These trade-offs can be summarized as:
\[ \text{Performance} \leftrightarrow \text{Capacity} \leftrightarrow \text{Area} \leftrightarrow \text{Power} \leftrightarrow \text{Complexity} \]
Modeling Cache Performance
The average memory access time (AMAT) provides a single metric for comparing designs:
\[ \text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty} \]
Suppose a cache has a hit time of 2 ns, a miss rate of 4%, and a miss penalty of 40 ns:
\[ \text{AMAT} = 2 + (0.04)(40) = 3.6 \text{ ns} \]
This equation allows architects to quantify the benefit of reducing miss rate or miss penalty.
Essential Formulas
| Quantity | Formula |
|---|---|
| Number of lines | \(\frac{\text{Cache Capacity}}{\text{Block Size}}\) |
| Number of sets | \(\frac{\text{Lines}}{\text{Associativity}}\) |
| Offset bits | \(\log_2(\text{Block Size})\) |
| Index bits | \(\log_2(\text{Number of Sets})\) |
| Tag bits | \(\text{Address Bits} - \text{Index} - \text{Offset}\) |
| AMAT | \(\text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}\) |
Conclusion
Cache design rests on a small set of parameters: capacity, block size, and associativity. From these, the number of lines, sets, and address field widths follow directly. Direct-mapped caches offer simplicity and speed; set-associative caches balance conflict misses against hardware cost; fully associative caches minimize conflicts at the expense of complexity.
As processor clock speeds continue to outpace memory latency improvements, cache design remains a critical area of computer architecture. The ability to calculate address breakdowns and reason about trade-offs provides a foundation for understanding more advanced topics such as replacement policies, write policies, and multilevel cache hierarchies.
%20(1)%20wepb.webp)
