Memory Hierarchy

A useful memory system must appear large, fast, and inexpensive, but no single technology maximizes all three. A hierarchy keeps the current working set in small fast levels and the rest in progressively larger, slower levels.

Why the Hierarchy Works

Programs show temporal locality—recently used items tend to be reused—and spatial locality—nearby addresses tend to be used soon. Loops, stacks, arrays, instructions in a basic block, subroutines, and symbol tables all exhibit locality. Moving an entire block on a miss anticipates nearby references.

The terms hit and miss are relative to a level. Hit ratio $h$ is the fraction found there; miss rate is $1-h$. Miss penalty includes the time to fetch from the next level and make the requested word available.

Main Memory Technologies

RAM

Random-access memory takes approximately the same time to access any addressed word.

DRAM reads are destructive and must restore the cell. Its address may be multiplexed into row and column portions to reduce package pins. SRAM is faster and simpler to interface but consumes more area per bit.

ROM family

ROM stores firmware and fixed lookup data. Modern flash is nonvolatile and rewritable, but writes are slower and organized in erase blocks.

Building and Addressing a Memory Module

An $m\times n$ chip stores $m$ words of $n$ bits. It needs $\log_2m$ address inputs and $n$ data connections. Capacity expansion has two independent directions:

• Put chips in parallel to widen each word.
• Decode additional high-order address bits to select one bank and increase the number of words.

For example, build $2\,\text{KiB}\times8$ from $512\times8$ chips. Each chip uses nine address bits because $512=2^9$. Four chips provide depth; $A_8\dots A_0$ go to every chip and a 2-to-4 decoder driven by $A_{10}A_9$ selects one chip.

If four 512-byte regions start at address 0x000, their inclusive ranges are:

The same decoder can select a mixture of RAM and ROM, creating a memory map. Read/write control must be disabled for ROM.

Cache Organization

A cache line contains a valid bit, a tag, a data block, and often dirty/replacement metadata. The CPU address separates into:

Direct mapping

Main-memory block $j$ maps to cache line $i=j\bmod L$, where $L$ is the number of cache lines. The index selects one line and its stored tag confirms whether that line contains the requested block. Hardware is small and fast, but two active blocks with the same index repeatedly evict each other.

Source example: a $32\text{K}\times12$ main memory has $2^{15}$ words and a $512\times12$ one-word-line cache has $2^9$ lines. Its 15-bit address splits into a 6-bit tag and a 9-bit line index. If each line instead contains eight words and the cache still holds 512 words, it has $64=2^6$ lines, so the split is 6 tag bits, 6 line bits, and 3 word bits.

Fully associative mapping

Any memory block may occupy any line. Every stored tag is compared in parallel, eliminating conflict based solely on index. The parallel comparison and replacement search cost more hardware.

Set-associative mapping

The cache is divided into $S$ sets with $W$ ways per set. Block $j$ maps to set $j\bmod S$ and may occupy any of its $W$ ways. It balances direct mapping’s fast indexing with associative placement inside a small set.

For a 32 KiB, 4-way cache with 64-byte lines and 32-bit byte addresses:

$\text{lines}=32768/64=512,\qquad \text{sets}=512/4=128.$

Offset bits $=\log_2 64=6$, set bits $=\log_2 128=7$, and tag bits $=32-7-6=19$.

Cache Lookup, Replacement, and Writes

Common victim policies are:

• FIFO: replace the line resident longest; simple, but not sensitive to actual use.
• LRU: replace the least recently referenced line; good locality behavior, but exact tracking becomes costly at high associativity.
• Random/pseudo-LRU: inexpensive approximations often used in hardware.
• Optimal: replace the item whose next use is farthest in the future; unattainable online, but a useful lower bound.

On a write, write-through updates cache and main memory immediately; a write buffer can hide some delay. Write-back updates only the cache, marks the line dirty, and writes it to memory when evicted. A write miss also needs an allocation choice: write-allocate fetches the line, whereas no-write-allocate writes around the cache.

Average Access Time

If a hit costs $t_c$ and a miss first checks cache and then accesses main memory in $t_m$, the source model is

$T=h\,t_c+(1-h)(t_m+t_c).$

With $t_c=160$ ns, $t_m=960$ ns, and $h=0.90$:

$T=0.9(160)+0.1(960+160)=256\text{ ns}.$

The main-memory/cache speed ratio is $\gamma=t_m/t_c=6$. Efficiency relative to ideal cache time is

Always state the timing convention. Some systems overlap cache lookup with the lower-level access and use $T=t_c+(1-h)t_m$; the numerical result happens to be the same algebraically here.

For multiple levels, let $F_i$ be the fraction of all requests that reach level $i$, and $t_i$ its access time:

$T=\sum_i F_it_i.$

Using the lecture example’s stated reach fractions and latencies—$F=(1,0.4,0.2,0.1)$ and $t=(100\text{ ns},1\,\mu\text{s},50\text{ ms},1\text{ s})$—

$T=0.0001+0.0004+10+100=110.0005\text{ ms}.$

This calculation treats $F_i$ as unconditional fractions of all references. If hit probabilities are conditional on reaching a level, multiply the preceding miss probabilities to derive $F_i$ instead.

Virtual Memory

Virtual memory gives each process a private address space larger and more regular than available physical RAM. It divides virtual space into fixed-size pages and physical memory into equal-size frames.

For virtual address width $v$, physical address width $p$, and page size $2^d$ bytes:

A page-table entry records the frame plus valid/present, protection, referenced, and dirty information. A translation lookaside buffer (TLB) caches recent page-table entries.

For a 32-bit byte address and a 4 KiB page, the offset has $\log_2 4096=12$ bits and the virtual page number has $32-12=20$ bits. If physical memory is 1 GiB, physical addresses have 30 bits, so a frame number needs $30-12=18$ bits. Translation changes the 20-bit virtual page number into an 18-bit frame number; it copies the 12-bit offset unchanged.

On a TLB miss, hardware or software consults the page table. If the page is present, translation is inserted into the TLB. If absent, a page fault transfers control to the operating system, which selects a frame, writes a dirty victim if needed, reads the required page from storage, updates the page table/TLB, and restarts the instruction.

Page Replacement

FIFO, LRU, and Optimal also illustrate virtual-memory replacement:

For reference string 7 0 1 2 0 3 0 4 and three empty frames, FIFO evolves:

7--  70-  701  201  201  231  230  430
 F    F    F    F    H    F    F    F

There are seven faults and one hit. LRU differs at the request for 3: because 1 is least recently used, it evicts 1 rather than FIFO’s 0. Optimal is useful for comparing algorithms, not implementing a real system.

Check Your Understanding

1. Why is a complete block fetched on a cache miss rather than only one word?
2. Split a 24-bit byte address for a direct-mapped 4 KiB cache with 16-byte lines.
3. What is the average time for $t_c=5$ ns, $t_m=80$ ns, and $h=0.95$ under the sequential-lookup model?
4. Which virtual-address field passes through translation unchanged?