Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

The memory hierarchy

Memory hierarchy organises storage levels (registers, caches, main memory, storage) to balance speed, cost and capacity so processors see fast accesses while backing data on slower, cheaper media.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers use the memory hierarchy to design systems where the CPU often gets data very fast while large amounts of data are still stored cheaply. Proper use of caches, main memory and disks reduces average access time and improves overall program performance.

Key ideas

Start from first principles: a processor needs data and instructions. Fast storage is expensive and small; slow storage is cheap and large. The memory hierarchy organises multiple levels so the processor usually finds data in a nearby fast level.

  • Memory hierarchy — an ordered set of storage levels (for example: registers, L1 cache, L2 cache, main memory, secondary storage) arranged by decreasing speed and increasing capacity. Define each term when first used:

    • Register — the fastest storage inside the CPU; holds values used by arithmetic logic.
    • Cache — a small, fast memory holding a subset of main memory data to reduce average access time.
    • Main memory — usually DRAM; larger and slower than caches; holds the running program and data.
    • Secondary storage — disks and SSDs; non-volatile and very large but much slower.
  • Locality principle — two formal forms used in exam answers:

    1. Temporal locality — if a location is referenced, it is likely to be referenced again soon.
    2. Spatial locality — if a location is referenced, nearby locations are likely to be referenced soon.

    These justify caches and block-based transfers.

  • Block (or cache line) — smallest unit transferred between a cache level and the next lower level. Use blocks to exploit spatial locality.

  • Hit and Miss:

    • Hit — the data requested by the CPU is present in the cache level being checked.
    • Miss — the data is not present; the system must fetch it from a lower (slower) level.
    • Types of cache misses (3C model) — Compulsory (cold-start) misses: first reference to a block; Capacity misses: working set exceeds cache capacity; Conflict misses: collisions due to limited associativity.
  • Hit time — time to access the cache and deliver data on a hit. Miss penalty — extra time required to fetch the data from the next level and refill the cache.

  • Derivation (standard) of Average Memory Access Time (AMAT) for one cache level: treat access outcome as a two-outcome random variable. Let hit rate = h, miss rate = m = 1 − h, hit time = T_H, miss penalty = T_M. The expected access time is AMAT = h·T_H + m·(T_H + T_M) = T_H + m·T_M. This derivation assumes independence of accesses (or that rates are measured over the same workload) and that on a miss the cache must first check the level (incurring T_H) then wait the miss penalty.

  • Mapping functions for caches:

    • Direct-mapped — each memory block maps to exactly one cache line (index determined by address). Simple, fast, but higher conflict misses.
    • Fully associative — a block may be placed in any cache line. Eliminates conflict misses but requires expensive search (parallel tag check) and higher hardware cost.
    • Set-associative (N-way) — compromise: cache divided into sets; each set has N lines. A block maps to one set, but may occupy any line in that set.

    For address decomposition with an A-bit physical address, block size B bytes, S sets:

    • Offset bits = log2(B) — choose which byte inside a block.
    • Index bits = log2(S) — choose which set (for direct-mapped S = number of lines).
    • Tag bits = A − (index bits) − (offset bits).

    Assumptions: block size and number of sets are powers of two; addresses are byte-addressed. Each cache line stores a tag and metadata bits (valid; and dirty if write-back).

  • Cache replacement policies: LRU (least recently used — evict the line not used for the longest time), FIFO (first-in first-out — evict the oldest line in the set), Random (choose a victim uniformly at random). Explain cost and performance trade-offs.

  • Write policies: Write-through (writes update lower level immediately) vs Write-back (writes update cache only; dirty block written back on eviction). Write-allocate (on write miss bring block into cache) vs no-write-allocate (write directly to lower level). Common pairings: write-back with write-allocate; write-through with no-write-allocate (write-around). Write-through designs typically use a write buffer to hide lower-level latency.

  • Translation Lookaside Buffer (TLB) — a small cache of page table entries used for virtual-to-physical address translation. Exams may ask effective access time (EAT) with a TLB: a simple serial model is EAT ≈ T_TLB_hit + m_TLB·T_TLB_miss_service + memory_access_time; state whether translation and cache access overlap (e.g., VIPT) if relevant.

  • For multi-level caches, AMAT generalises: if L1 has hit time T1 and miss rate m1, and next level (L2) has AMAT2, then AMAT = T1 + m1·AMAT2. This is derived by replacing the miss penalty of L1 with the full expected cost of L2. In this formulation, miss rates at lower levels (m2, m3, …) are local miss rates measured conditional on an access to that level (not global miss rates). State the cache inclusion policy (inclusive/exclusive/non-inclusive non-exclusive) if it affects the question.

  • Diagram to draw in an exam: a vertical stack of boxes labelled (top to bottom) CPU registers, L1 cache (split I/D optional), L2 cache, L3 cache (optional), main memory (DRAM), and secondary storage (SSD/HDD). On the right annotate: typical sizes (bytes), access times (ns or µs), and cost per byte (₹/B or $/B). Draw arrows downward showing increasing capacity and decreasing speed.

Formulas

AMAT = T_H + m·T_M — AMAT: average memory access time (seconds); T_H: hit time (s); m: miss rate (unitless fraction); T_M: miss penalty (s). Applies to one cache level.

AMAT_total = T1 + m1·(T2 + m2·(T3 + ...)) — multi-level AMAT expansion; Ti: hit time at level i (s), mi: miss rate at level i (fraction).

offset_bits = log2(block_size_bytes) — number of offset bits (bits); block_size_bytes in bytes; requires block size power of two.

number_of_blocks = cache_size_bytes / block_size_bytes — unitless count; both sizes in bytes. Assume cache_size_bytes refers to data store size (excluding tags/metadata), unless stated otherwise.

index_bits = log2(number_of_sets) — bits to select set; number_of_sets = number_of_blocks / associativity.

tag_bits = address_bits − index_bits − offset_bits — bits for tag in an address.

miss_rate = 1 − hit_rate — fraction.

Note: log2 denotes base-2 logarithm; when values are not powers of two, integer ceiling/floor rules apply — verify in exam whether the course assumes powers of two.

Worked examples

Example 1 — compute AMAT for one-level cache

Given: L1 cache hit time T_H = 1.0 ns, miss rate m = 5% = 0.05, miss penalty T_M = 50 ns (to fetch from DRAM). Find AMAT.

Step 1: Formula: AMAT = T_H + m·T_M.

Step 2: Substitute: AMAT = 1.0 ns + 0.05·50 ns = 1.0 ns + 2.5 ns = 3.5 ns.

Answer: AMAT = 3.5 ns.

Example 2 — address decomposition for a 32-bit machine

Given: 32-bit physical addresses. Cache size = 32 KB (1 KB = 1024 B), block size = 64 B, 4-way set-associative. Compute offset, index, and tag bits.

Step 1: Convert sizes: cache_size_bytes = 32 × 1024 = 32768 B; block_size = 64 B.

Step 2: number_of_blocks = 32768 / 64 = 512 blocks.

Step 3: associativity = 4 → number_of_sets = 512 / 4 = 128 sets.

Step 4: offset_bits = log2(64) = 6 bits.

Step 5: index_bits = log2(128) = 7 bits.

Step 6: tag_bits = 32 − 7 − 6 = 19 bits.

Answer: offset = 6 bits, index = 7 bits, tag = 19 bits.

Example 3 — direct-mapped mapping by address

Given: 16-bit byte addresses, direct-mapped cache with 16 lines, block size 4 bytes. Which cache line does memory address 0x1234 map to? (Show steps.)

Step 1: block_size = 4 → offset_bits = log2(4)=2.

Step 2: number_of_lines = 16 → index_bits = log2(16)=4.

Step 3: Binary of 0x1234 = 0001 0010 0011 0100.

Step 4: Break into [tag | index | offset] = [remaining 10 bits | next 4 bits | last 2 bits]. Index bits are bits 2..5 from LSB; extract them: the address in binary ends ...00110100. The last 2 bits (offset) = 00; the next 4 bits (index) = 1101 (binary) = 13 decimal.

Answer: Maps to cache line 13.

Common mistakes

  • Not checking that block size and number of sets are powers of two before using log2; forgetting to round to integer bits.
  • Confusing miss penalty (extra time) with total time to service a miss (which often includes T_H).
  • For set-associative caches, treating number_of_sets as number_of_lines mistakenly.
  • In direct-mapped indexing, incorrectly extracting index bits from the wrong end of the address.

For your exam

Types of questions:

  • Definitions and short notes: define locality, cache, hit/miss, replacement and write policies.
  • Derivations: derive AMAT formula; show index/tag/offset decomposition for a cache.
  • Numericals: compute AMAT, decompose addresses, calculate miss rates and effect of multi-level caches.
  • Diagrams: draw the memory hierarchy stack labelled with capacity, latency, and cost trends.

What full-marks answers include:

  • Clear definitions with bold terms (if required), units, and assumptions (e.g., power-of-two sizes).
  • Step-by-step derivations (show expectation calculation for AMAT).
  • For numericals: show conversions, formula, substitutions with units, intermediate results and a final answer with units.
  • For diagram questions: a labelled stack and short explanation of trade-offs.

Quick check

  1. Define temporal locality in one sentence.
  2. For a cache with hit time 2 ns, miss rate 4% and miss penalty 80 ns, what is AMAT? (show numeric answer only)
  3. For a 64 B block, what is offset_bits?

Answers: 1) Temporal locality: recently accessed data is likely to be accessed again soon. 2) 5.2 ns. 3) offset_bits = 6.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?