Memory Hierarchy and Performance: short notes (Computer Organization & Architecture)

Introduction

No single memory technology is at once fast, large and cheap. Static RAM is fast but costly per bit, DRAM is slower but dense, and magnetic disks and flash are slower again but cheaper still. A memory hierarchy stacks these technologies so that a small, fast level sits close to the processor and holds the data in current use, while larger, slower levels hold everything else. If most accesses are served by the fast level, the whole system behaves almost as fast as the top level and almost as large and cheap as the bottom one.

The hierarchy works because programs show locality of reference. This note defines the performance measures (hit ratio, miss penalty, average memory access time), derives the two access models GATE uses (hierarchical and simultaneous), extends them to several levels, and shows how memory stalls enter CPI. How a cache is organised is the subject of Cache Memory and Cache Mapping.

Prerequisites

None within the notes. The note uses only averages and percentages; interleaving, which reduces the miss penalty, is explained in the memory interfacing note listed under Related topics.

Core concepts

Levels and locality

Level (top to bottom)	Typical technology	Managed by
Registers	Flip-flops inside the processor	Compiler
Cache (L1, L2, L3)	SRAM	Hardware
Main memory	DRAM	Operating system (with hardware for address translation)
Secondary storage	Magnetic disk or flash (SSD)	Operating system

Going down: capacity grows, access time grows, cost per bit falls. Data move between adjacent levels in fixed units: blocks (lines) between cache and main memory, pages between main memory and disk.

Temporal locality: an item referenced now is likely to be referenced again soon (loop variables, instructions of a loop body). It justifies keeping recently used data in the fast level.
Spatial locality: items near a referenced item are likely to be referenced soon (sequential instructions, array elements). It justifies moving a whole block, not one word.

Inclusion. In many designs every block held in a level is also held in the level below it. This is a design choice, not a law; exclusive caches exist. Unless a question says otherwise, assume the lowest level named always holds the data.

Performance measures

Term	Meaning
Hit	The requested word is found in the level searched
Hit ratio $h$	Fraction of accesses that hit
Miss ratio $m$	$1 - h$
Hit time $t_c$	Time to access the level on a hit
Miss penalty	Extra time to get the word from the level below (often to fetch the whole block)
Average memory access time (AMAT, effective access time)	Expected time per access over hits and misses
Local miss rate of level $i$	Misses at level $i$ divided by accesses that reach level $i$
Global miss rate of level $i$	Misses at level $i$ divided by all accesses made by the processor

Different count: local versus global miss rate. With L1 local miss rate $m_1$ and L2 local miss rate $m_2$ , the global L2 miss rate is $m_1 m_2$ . Given one, compute the other.

How it works

On every access the processor looks in the top level first. Two organisations decide what happens on a miss.

Hierarchical (look-through, serial) access. The next level is started only after the miss is detected. A miss costs the cache's time plus the memory's time.
Simultaneous (look-aside, parallel) access. Both levels start together; on a hit the slower access is abandoned. A miss costs only the memory's time.

Hierarchical and simultaneous access timelines for a hit and a miss — Figure 1. With a 10 ns cache and a 100 ns memory, a miss costs 110 ns under hierarchical access and 100 ns under simultaneous access; a hit costs 10 ns in both, so with $h = 0.9$ the averages are 20 ns and 19 ns.

Figure 2 summarises the trade-off along the levels.

Memory hierarchy pyramid from registers to secondary storage — Figure 2. The memory hierarchy: registers, cache, main memory and secondary storage from top to bottom; capacity and access time grow downwards while cost per bit falls.

Algorithms and pseudocode

Text

ACCESS(address)                       // two-level, hierarchical
  if address is in cache then
    return data after t_c             // hit
  else
    fetch the block from memory       // detected after t_c
    place it in the cache (may evict a block)
    return data after t_c + t_m       // miss

For simultaneous access the miss returns after $t_m$ , because the memory access began at time 0. Many questions model the miss penalty as "one memory access time"; others charge the time to transfer the whole block. Read which one is meant.

Mathematical explanation

Let $t_c$ be the cache access time, $t_m$ the main-memory access time (or the miss penalty when the question gives a block transfer time), and $h$ the hit ratio.

Hierarchical access.

T_{\text{avg}} = h\,t_c + (1 - h)(t_c + t_m) = t_c + (1 - h)\,t_m

Simultaneous access.

T_{\text{avg}} = h\,t_c + (1 - h)\,t_m

The two differ by $(1 - h)\,t_c$ , which is small when $h$ is high.

Three levels, hierarchical. With L1 time $t_1$ and local miss rate $m_1$ , L2 time $t_2$ and local miss rate $m_2$ , and memory time $t_3$ :

T_{\text{avg}} = t_1 + m_1\,(t_2 + m_2\,t_3).

Three levels, simultaneous. Each access is served by the first level that holds the word, at that level's time:

T_{\text{avg}} = (1 - m_1)\,t_1 + m_1(1 - m_2)\,t_2 + m_1 m_2\,t_3.

Memory stalls in CPI. For a processor with base CPI $C_0$ (all hits), $a_I$ instruction fetches and $a_D$ data accesses per instruction, miss rates $m_I$ and $m_D$ , and a miss penalty of $P$ cycles:

\text{CPI} = C_0 + a_I\,m_I\,P + a_D\,m_D\,P.

Usually $a_I = 1$ . The speedup of a perfect cache over this one is $\text{CPI} / C_0$ .

Block miss penalty. If a block of $w$ words is fetched from a memory that needs $c_a$ cycles to send the address, $c_m$ cycles per access and $c_t$ cycles to transfer a word:

Memory organisation	Miss penalty (cycles)
One word wide	$c_a + w\,(c_m + c_t)$
$w$ words wide	$c_a + c_m + c_t$
$w$ interleaved one-word banks	$c_a + c_m + w\,c_t$

Average cost per bit. Two levels of sizes $S_1, S_2$ and costs per bit $c_1, c_2$ cost on average $(c_1 S_1 + c_2 S_2)/(S_1 + S_2)$ per bit, close to $c_2$ when $S_2 \gg S_1$ .

Disk access time (secondary storage level). Access time $=$ seek time $+$ rotational latency $+$ transfer time $(+$ controller overhead $)$ . The average rotational latency is half a revolution: at $r$ revolutions per minute it is $\frac{1}{2} \cdot \frac{60}{r}$ seconds. Transfer time is bytes divided by transfer rate.

Worked examples

Example 1: hierarchical versus simultaneous

Cache access 10 ns, main memory 100 ns, hit ratio 0.9.

Hierarchical: $10 + 0.1 \times 100 = 20$ ns.
Simultaneous: $0.9 \times 10 + 0.1 \times 100 = 19$ ns.
Without a cache every access takes 100 ns, so the cache gives a speedup of $100/20 = 5$ (hierarchical).

Example 2: the hit ratio needed for a target

With the same times, what hit ratio gives an average of 15 ns under hierarchical access? $10 + (1 - h) \times 100 = 15$ gives $1 - h = 0.05$ , so $h = 0.95$ . Under simultaneous access, $10h + 100(1 - h) = 15$ gives $h = 85/90 \approx 0.944$ .

Example 3: two cache levels

L1: 1 ns, local miss rate 10%. L2: 10 ns, local miss rate 20%. Main memory: 100 ns.

Hierarchical: $1 + 0.1 \times (10 + 0.2 \times 100) = 1 + 0.1 \times 30 = 4$ ns.
Global L2 miss rate: $0.1 \times 0.2 = 0.02$ , that is 2% of all accesses go to memory.
Simultaneous: $0.9 \times 1 + 0.08 \times 10 + 0.02 \times 100 = 0.9 + 0.8 + 2.0 = 3.7$ ns.
Without L2 (L1 then memory, hierarchical): $1 + 0.1 \times 100 = 11$ ns, so L2 cuts the average from 11 ns to 4 ns.

Example 4: CPI with cache misses

Base CPI 1.0, one instruction fetch and 0.3 data accesses per instruction, instruction-cache miss rate 2%, data-cache miss rate 5%, miss penalty 100 cycles.

Instruction-miss stalls: $1 \times 0.02 \times 100 = 2.0$ cycles per instruction.
Data-miss stalls: $0.3 \times 0.05 \times 100 = 1.5$ cycles per instruction.
CPI $= 1.0 + 2.0 + 1.5 = 4.5$ . A perfect cache would make the processor $4.5$ times faster.
Halving the miss penalty to 50 cycles gives CPI $= 1 + 1 + 0.75 = 2.75$ .

Example 5: block miss penalty

A block has 4 words. Sending the address takes 1 cycle, each DRAM access 15 cycles, each word transfer 1 cycle.

One-word-wide memory: $1 + 4 \times (15 + 1) = 65$ cycles.
Four-word-wide memory and bus: $1 + 15 + 1 = 17$ cycles.
Four interleaved banks, one-word bus: $1 + 15 + 4 \times 1 = 20$ cycles.

Interleaving gets most of the benefit of a wide memory with a narrow bus (see Memory Interfacing and Organization).

Example 6: disk access

A disk spins at 7200 rpm, the average seek time is 4 ms and the transfer rate is $50 \times 10^6$ bytes per second. Read one 4096-byte block.

One revolution: $60/7200$ s $= 8.333$ ms, so the average rotational latency is $4.1667$ ms.
Transfer: $4096 / (50 \times 10^6)$ s $= 0.08192$ ms.
Average access time: $4 + 4.1667 + 0.0819 \approx 8.25$ ms, millions of times slower than a cache hit. This gap is why a page fault is so expensive.

Important properties and observations

Hierarchical access always costs the cache time. On a miss the total is $t_c + t_m$ , not $t_m$ .
Simultaneous access cannot be slower than hierarchical access with the same parts; the difference is $(1 - h)\,t_c$ .
Small miss rates matter. With a 100 ns memory and a 10 ns cache, going from 90% to 95% hits cuts the hierarchical average from 20 ns to 15 ns.
Miss penalty, miss rate and hit time trade off. Larger blocks can lower compulsory misses through spatial locality but raise the miss penalty and, at fixed cache capacity, can increase capacity or conflict misses; a larger cache lowers the miss rate but may raise the hit time.
Multi-level formulas use local miss rates inside the nested expression; the global rate of the last level is the product of the local rates.
Memory stalls dominate CPI when the miss penalty is large: in Example 4 the stalls are 3.5 of the 4.5 cycles.
Common misconceptions.
- "AMAT $= h\,t_c + (1 - h)\,t_m$ always." That is the simultaneous model; hierarchical access adds $(1 - h)\,t_c$ .
- "The L2 miss rate given is out of all accesses." Usually it is the local rate; check the wording.
- "Rotational latency is one full revolution." The average is half a revolution.

GATE examination perspective

ACCESS MODEL. Identify hierarchical (the default when the question says the lower level is accessed after a miss) or simultaneous (when it says the levels are accessed in parallel).
WHAT A MISS COSTS. One memory word, or a whole block transfer, or a block transfer plus the cache read: use the question's definition.
LOCAL OR GLOBAL. Convert miss rates before substituting into the nested formula.
READS AND WRITES. Write policies change the time of a write (see Cache Memory); combine read and write times with their fractions.
CPI WITH MISSES. There is normally one instruction fetch per instruction; weight its penalty by the instruction-cache miss rate. Weight data accesses by the load/store frequency and data-cache miss rate.
INVERSE QUESTIONS. Solve for the hit ratio or the memory time that achieves a target average.
DISK TIME. Seek plus half a rotation plus transfer, with consistent units.

Summary

Cache Memory: dependent. What a cache stores, write policies and replacement.
Cache Mapping: dependent. Where a block may go and the address split.
Memory Interfacing and Organization: related. Interleaving and building memories from chips.
Paging, Page Tables and TLB: related. The main-memory to disk level and the TLB, with the same effective-access-time arithmetic.

Memory Hierarchy and Performance

Introduction

Prerequisites

Core concepts

Levels and locality

Performance measures

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: hierarchical versus simultaneous

Example 2: the hit ratio needed for a target

Example 3: two cache levels

Example 4: CPI with cache misses

Example 5: block miss penalty

Example 6: disk access

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Levels and locality

Performance measures

How it works

Algorithms and pseudocode

Mathematical explanation

Worked examples

Example 1: hierarchical versus simultaneous

Example 2: the hit ratio needed for a target

Example 3: two cache levels

Example 4: CPI with cache misses

Example 5: block miss penalty

Example 6: disk access

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps