# Memory Hierarchy and Cache — Locality, Hit Ratio, AMAT and Direct, Associative and Set-Associative Mapping

Source: https://skills101.in/learn/coa/memory-hierarchy-cache-mapping — Skills101 free tutorial (Computer Organisation & Architecture (COA)). Updated 2026-11-09.

A modern CPU can do an addition in well under a nanosecond, but fetching data from main memory takes around a hundred times longer. If the CPU waited for RAM every time, it would sit idle most of the time. The **memory hierarchy** — especially **caches** — is how computers hide that gap. Cache questions are the single most common COA numerical in GATE.

## 1. The hierarchy

![Memory hierarchy pyramid: registers at the top (fastest, smallest, most expensive per byte), then L1, L2, L3 caches, main memory (DRAM), SSD and hard disk at the bottom (slowest, largest, cheapest)](https://skills101.in/learn-img/coa/memory-hierarchy.svg)

| Level | Typical size | Typical access time (order of magnitude) |
|---|---|---|
| Registers | bytes–KB | < 1 ns |
| L1 cache | tens of KB per core | ~1 ns |
| L2 cache | hundreds of KB–few MB | a few ns |
| L3 cache | several–tens of MB (shared) | ~10 ns |
| Main memory (DRAM) | GBs | ~50–100 ns |
| SSD | hundreds of GB–TBs | tens–hundreds of µs |
| Hard disk | TBs | milliseconds |

Faster memory is smaller and costlier per byte. The goal: make the whole system **feel** as fast as the top level and as big as the bottom one.

## 2. Why caches work: locality

- **Temporal locality** — data used now will probably be used again soon (loop variables, counters).
- **Spatial locality** — data near what's used now will probably be used soon (array elements, sequential instructions).

So caches keep **recently used** data and fetch memory in **blocks** (cache lines, e.g. 64 bytes) rather than single bytes. That's why iterating an array row by row is much faster than column by column in C/Java.

## 3. Hit ratio and AMAT

- **Hit** — data found in the cache. **Miss** — must go to the next level.
- **Hit ratio h** = hits / accesses; miss ratio = 1 − h.
- **Average memory access time:** `AMAT = hit time + miss rate × miss penalty`.

Two-level cache: `AMAT = T_L1 + m_L1 × (T_L2 + m_L2 × T_mem)`.

(Some textbooks use `h·Tc + (1−h)·(Tc + Tm)` — the same thing when a miss first checks the cache. Read which model the question uses.)

```python
def amat(hit_time, miss_rate, miss_penalty):
    return hit_time + miss_rate * miss_penalty

print("L1 only: ", amat(1, 0.05, 100), "ns")
print("L1 + L2: ", 1 + 0.05 * (10 + 0.20 * 100), "ns")
print("no cache:", 100, "ns")
```

```text
L1 only:  6.0 ns
L1 + L2:  2.5 ns
no cache: 100 ns
```

A 95% hit rate turns 100 ns memory into a 6 ns *average*; adding an L2 brings it to 2.5 ns.

## 4. Cache mapping: where can a block go?

Main memory is divided into **blocks**; the cache into **lines** of the same size. Mapping decides which line(s) a block may occupy.

| Mapping | A block can go in | Lookup | Conflicts |
|---|---|---|---|
| **Direct-mapped** | exactly one line: `block mod lines` | 1 comparison, fast, cheap | high — two hot blocks with the same index keep evicting each other |
| **Fully associative** | any line | compare with every tag (expensive) | none from mapping |
| **k-way set-associative** | any of the k lines in set `block mod sets` | k comparisons | low — the common real-world choice (e.g. 8-way L1) |

## 5. Splitting an address: tag | index | offset

![A memory address split into tag, index and offset: offset bits choose the byte inside the block, index bits choose the cache line or set, and the tag is compared to check that the stored block is the right one](https://skills101.in/learn-img/coa/cache-address.svg)

- **Offset bits** = log₂(block size)
- **Index bits** = log₂(number of lines) for direct-mapped, log₂(number of sets) for set-associative, **0** for fully associative
- **Tag bits** = address bits − index − offset

**Worked example.** 32-bit addresses, 64 KB cache, 64-byte blocks.

```python
import math

def split(address_bits, cache_bytes, block_bytes, ways):
    lines = cache_bytes // block_bytes
    sets = lines // ways
    offset = int(math.log2(block_bytes))
    index = int(math.log2(sets))
    tag = address_bits - index - offset
    return lines, sets, tag, index, offset

for name, ways in [("direct-mapped", 1), ("4-way set-assoc", 4), ("fully associative", 64 * 1024 // 64)]:
    lines, sets, tag, index, offset = split(32, 64 * 1024, 64, ways)
    print(f"{name:18} lines={lines} sets={sets:5}  tag={tag:2} index={index:2} offset={offset}")
```

```text
direct-mapped      lines=1024 sets= 1024  tag=16 index=10 offset=6
4-way set-assoc    lines=1024 sets=  256  tag=18 index= 8 offset=6
fully associative  lines=1024 sets=    1  tag=26 index= 0 offset=6
```

Notice: more associativity → fewer sets → fewer index bits → **more tag bits** (and more comparators).

**Tag memory size** (a common follow-up): tag bits × number of lines. For the direct-mapped case: 16 × 1024 = 16,384 bits = 2 KB of tags (plus valid/dirty bits if the question includes them).

## 6. A working direct-mapped cache simulator

```python
def simulate(addresses, lines=4, block=16):
    cache = [None] * lines            # stores the tag in each line
    hits = 0
    for a in addresses:
        blk = a // block
        idx, tag = blk % lines, blk // lines
        if cache[idx] == tag:
            hits += 1
            result = "hit"
        else:
            result = "miss" + ("" if cache[idx] is None else " (evict)")
            cache[idx] = tag
        print(f"addr {a:3} -> block {blk:2} line {idx} tag {tag}: {result}")
    print(f"hit ratio = {hits}/{len(addresses)} = {hits / len(addresses):.2f}")

simulate([0, 4, 8, 64, 0, 16, 64, 4])
```

```text
addr   0 -> block  0 line 0 tag 0: miss
addr   4 -> block  0 line 0 tag 0: hit
addr   8 -> block  0 line 0 tag 0: hit
addr  64 -> block  4 line 0 tag 1: miss (evict)
addr   0 -> block  0 line 0 tag 0: miss (evict)
addr  16 -> block  1 line 1 tag 0: miss
addr  64 -> block  4 line 0 tag 1: miss (evict)
addr   4 -> block  0 line 0 tag 0: miss (evict)
hit ratio = 2/8 = 0.25
```

Addresses 0 and 64 are in blocks 0 and 4, which both map to **line 0** in a 4-line direct-mapped cache — they keep evicting each other (**conflict misses**). A 2-way set-associative cache would hold both.

## 7. Types of misses (the 3 Cs)

| Miss type | Cause | Reduce by |
|---|---|---|
| **Compulsory (cold)** | first access to a block | larger blocks, prefetching |
| **Capacity** | the working set is bigger than the cache | bigger cache |
| **Conflict** | blocks fighting over the same line/set | more associativity |

## 8. Writes and replacement

- **Write-through** — write to cache and memory every time (simple, more memory traffic); usually with a write buffer.
- **Write-back** — write only to cache, mark the line **dirty**, write to memory when evicted (less traffic).
- **Replacement** (set-associative/fully associative): **LRU** (least recently used), FIFO, random.

## Common mistakes

- Using the number of **lines** instead of **sets** for index bits in set-associative caches.
- Forgetting that fully associative has **no index bits**.
- Mixing up the two AMAT formulas — check whether the miss time already includes the cache check.
- Computing offset from the cache size instead of the **block** size.

## Quick recap

- Hierarchy: registers → L1 → L2 → L3 → RAM → SSD/disk; caches work because of **temporal and spatial locality**.
- **AMAT = hit time + miss rate × miss penalty** (apply recursively for multi-level).
- Direct (1 place), fully associative (anywhere), k-way set-associative (k places in one set).
- Address = **tag | index | offset**; offset = log₂(block), index = log₂(lines or sets), tag = rest.
- Misses: compulsory, capacity, conflict. Write-through vs write-back; LRU replacement.


Practice quiz and free certificate: https://skills101.in/learn/coa/memory-hierarchy-cache-mapping