3.3 Cache Mapping (Direct)

Cache memory is a small, high-speed SRAM buffer positioned between the CPU and primary DRAM. Because cache is much smaller than main memory, the system must map memory blocks into cache lines. This chapter explores locality of reference, direct mapping modular architectures, and physical address partitioning.

Learning Objectives

Define cache concepts: Cache Line, Tag, Block Offset, Hit/Miss Ratio, and locality of reference.
Explain how direct mapping routes blocks of main memory into cache slots using modulo indexing.
Partition physical memory addresses into Tag, Line Index, and Block Offset bits based on cache specifications.
Contrast Direct Mapping with Fully Associative and Set-Associative Mapping in terms of hardware tag comparator requirements.
Calculate Average Memory Access Time ($T_{avg}$) given cache access times, hit rates, and main memory latency.

Prerequisites

Before studying this chapter, you should review Chapter 3.2: Associative Memory to understand parallel match registers and search gates.

1. Locality of Reference and Cache Architecture

Cache design relies on **Locality of Reference**:

**Temporal Locality**: Programs tend to re-access recently used data (e.g., variables in loop counters).
**Spatial Locality**: Programs tend to access memory locations situated close to previously accessed data (e.g., array traversals).

2. Direct Mapping Architecture

In **Direct Cache Mapping**, each block of main memory is mapped to exactly one specific cache line. The mapping is determined by modular arithmetic: $$i = j \pmod C$$ where $i$ is the cache line index, $j$ is the main memory block index, and $C$ is the total number of lines in the cache.

3. Address Bus Partitioning & Fields

To route memory requests, the physical address is partitioned into three fields:

**Block Offset ($W$)**: Selects the specific byte within a block. $$W = \log_2(\text{Block Size in Bytes})$$
**Line Index ($L$)**: Selects the target cache line slot. $$L = \log_2(\text{Number of Lines in Cache})$$
**Tag ($T$)**: Stored in cache tag memory to verify if the block in that line matches the requested memory block. $$T = \text{Total Address Bits} - L - W$$

4. Performance Math (Average Access Time)

The efficiency of the memory system is evaluated using the **Average Memory Access Time ($T_{avg}$)**: $$T_{avg} = H \times T_{cache} + (1-H) \times (T_{cache} + T_{memory})$$ where: - $H$ is the Hit Ratio. - $T_{cache}$ is the cache access time. - $T_{memory}$ is the main memory access latency.

5. Worked Examples & Traces

Execution Trace

Worked Example 3.3.1: Cache Read Access Flow

**Problem**: Trace a CPU memory read request to address `0x0F4C8` in a system with a 20-bit address bus, $16\text{ KB}$ cache, and $16$-byte blocks.

**System Parameters**: - Address bits $= 20$. - Block Size $= 16\text{ Bytes} \Rightarrow W = \log_2(16) = 4$ bits. - Cache Size $= 16\text{ KB} = 16384\text{ Bytes}$. - Number of Lines $= \frac{16384}{16} = 1024 \Rightarrow L = \log_2(1024) = 10$ bits. - Tag size $= 20 - 10 - 4 = 6$ bits.

**Step-by-Step Trace**:

**CPU issues memory request to Address Bus**: $$\text{Address } \text{0x0F4C8} = 0000\ 1111\ 0100\ 1100\ 1000_2$$
**Extract Fields**: - **Tag ($A_{19}-A_{14}$)**: $000011_2$ (`0x03`) - **Line Index ($A_{13}-A_4$)**: $1101001100_2$ (`0x34C`) - **Block Offset ($A_3-A_0$)**: $1000_2$ (`0x8`)
**Index Selection**: The cache controller accesses line index `0x34C` (line 844) in the cache memory.
**Cache Compare**: The tag comparator compares the stored tag bit pattern of line 844 against the extracted Tag (`0x03`) and verifies the **Valid Bit**.
**Hit / Miss Path**: - **If tag matches and valid bit is 1 (Cache Hit)**: The multiplexer selects byte offset `0x8` from the cache line buffer and routes it to the **Data Bus**. - **If tag mismatches or valid bit is 0 (Cache Miss)**: The request is sent to **Memory** using the control bus line $MEMR$ to read the entire 16-byte block. The block is written to cache line index `0x34C`, the tag is updated to `0x03`, the valid bit is set to 1, and the byte is sent to the CPU.

Average Access Math

Worked Example 3.3.2: T_avg Calculation

**Problem**: Given $T_{cache} = 1.5\text{ ns}$, $T_{memory} = 50\text{ ns}$, and a hit ratio of $95\%$, calculate $T_{avg}$.

**Solution**: $$T_{avg} = 0.95 \times 1.5 + (1 - 0.95) \times (1.5 + 50)$$ $$T_{avg} = 1.425 + 0.05 \times 51.5 = 1.425 + 2.575 = 4.0\text{ ns}$$

Common Mistakes to Avoid

Warning: Common Student Pitfalls

**Calculating Line Bits incorrectly**: Dividing cache size by block size but forgetting to convert the result into a base-2 logarithm power.
**Forgetting Cache Lookup Overhead on Misses**: Assuming that on a cache miss, the memory access time is only $T_{memory}$, forgetting that the cache tag comparison must occur first ($T_{cache} + T_{memory}$).

Revision Summary & Takeaways

Cache exploits temporal and spatial locality to reduce CPU wait cycles.
Direct Mapping maps main memory block $j$ to cache line $j \pmod C$.
Addresses are split into Tag (identification), Line Index (set selector), and Block Offset (byte selector) fields.

How this chapter connects to the next

We have examined how direct mapping routes read requests and resolves hits/misses. In Chapter 3.4: Cache Writing Policies, we transition from read paths to write synchronization, analyzing how data changes in the cache are safely updated in main memory.

Check Your Understanding

1. In a direct-mapped cache, how many tag comparators are physically required?

References

**ref-notes-syed-arsalaan**: Handwritten Lecture Notes, Page 88 (Direct Mapped Address Parsing). [Local Verified]
**ref-notes-class**: Class COA Lecture Notes, Page 37 (Locality of Reference). [Local Verified]
**ref-book-stallings**: William Stallings, *Computer Organization and Architecture*, Chapter 4. [Pending Verification]
**ref-lecture-sengupta-29**: Prof. Indranil Sengupta, NPTEL COA, Lecture 29 (Cache Mapping). [Pending Verification]