Translation Lookaside Buffer (TLB)

1. Why we need translation at all

A TLB is a small, fast cache that remembers where virtual pages live in physical memory, so the CPU doesn’t have to read the page table from memory on every access.

1. Why we need translation at all

With virtual memory, every address a program uses is a virtual address. Before the CPU can fetch the data, it must turn that into a physical address (the real location in RAM).

An address is split into two parts:

Virtual address  = [ virtual page number (VPN) | offset ]
Physical address = [ physical frame number (PFN) | offset ]

• The offset (position inside the page) stays the same.
• Only the page number changes, and the page table says what it changes to.

Example (4 KB pages): virtual address 0x3ABC → VPN = 3, offset = 0xABC. The page table says “page 3 is in frame 7”, so the physical address is 0x7ABC.

2. The problem: two memory accesses for every one

The page table itself lives in main memory. So without help, every load or store needs:

1. one memory access to read the page table entry (to find the frame), then
2. one memory access to get the actual data.

That makes every memory access twice as slow.

3. The fix: the TLB

The TLB (Translation Lookaside Buffer) is a tiny, very fast cache inside the CPU that stores recently used page table entries (VPN → frame number). It’s typically only tens to a few thousand entries, and often fully associative.

Analogy: the page table is the full address book in a drawer (main memory). The TLB is a sticky note on your monitor with the few addresses you’ve looked up recently. You check the sticky note first and only open the drawer if the address isn’t there.

4. What happens on each access

There are four possible paths, from fastest to slowest:

Path 1, TLB hit + cache hit: The TLB gives the frame number immediately, the CPU forms the physical address, and the data is found in the cache. This is the common, fast case.

Path 2, TLB hit + cache miss: The translation is fast, but the data isn’t in the cache, so it comes from main memory.

Path 3, TLB miss, page is in memory: The translation isn’t on the “sticky note”, so the CPU (or OS) reads the page table in main memory. The page table says the page is in RAM, so its entry is copied into the TLB and the access is retried, now as a TLB hit.

Path 4, TLB miss, page is NOT in memory (page fault): The page table’s valid bit says the page is on disk. The OS must:

1. load the page from disk into a free frame in memory,
2. update the page table,
3. update the TLB,
4. restart the instruction.

Disk is extremely slow compared to memory, so this costs millions of cycles.

5. Slide question: “If TLB hit, where can you find the data?”

Answer: in the cache or in main memory, never on disk.

A TLB hit only tells you where the page is in physical memory. It says nothing about whether that particular block is in the cache.

• If the block is in the cache → cache (path 1)
• If not → main memory (path 2)

It can’t be on disk because the TLB only keeps entries for pages that are currently in physical memory. When the OS moves a page out to disk, it marks the page table entry invalid and removes (invalidates) that page’s TLB entry. So if the TLB has an entry, the page must be in RAM

6. Clearing up the slide’s wording: TLB miss ≠ page fault

The slide jumps quickly from “TLB miss” to “page fault”, but they’re different events:

• Most TLB misses are not page faults. The page table usually says “the page is in memory, frame X”, and you just refill the TLB.
• A page fault happens only when the page table says the page is not in memory.
• The slide says the page table “may not be in the memory”. More precisely, it’s the page (the data) that may be on disk. The page table normally stays in memory.

7. Summary in one picture

Virtual address
   │
   ▼
 TLB ──hit──► physical address ──► cache ──miss──► main memory
   │
  miss
   ▼
 Page table (in memory)
   ├─ page in memory ──► update TLB ──► retry (now a TLB hit)
   └─ page NOT in memory ──► PAGE FAULT ──► OS loads page from disk
                                           ──► update page table + TLB ──► retry

---

Each virtual memory reference can cause two physical memory accesses

• One to fetch the page table
• One to fetch the data

To overcome this problem a high-speed cache is set up for page table entries

• Called a Translation Lookaside Buffer (TLB)
• TLB is a cache of the page table
• Contains page table entries that have been most recently used

Given a virtual address, processor examines the TLB

If page table entry is present (TLB hit), the page frame address is retrieved and the real address is formed

• Page frame address: physical memory location of that page

Question: if TLB hit, where can you find the data?
Cache? Memory? Disk?

If page table entry is not found in the TLB (TLB miss), the page number is used to index the process page table which may not in the memory

• Causes a page fault: page is not in the memory
• Penalty: millions of cycles

First checks if page is already in main memory

• If not in main memory a page fault is issued

The TLB is updated to include the new page entry

A Hirerachy of Misses

1. TLB miss
2. Cache miss
3. Page fault
4. Multiple instances of any of these misses can occur for any single instruction

TLB (Direct mapped vs fully associative)

Both sides translate the same virtual address, page 5, offset 502, to the same real address, frame 37, offset 502. They differ in how they find “page 5 → frame 37”.

(a) Direct mapping: the page table

The page table has one entry for every virtual page, in order. So the page number is used directly as an index:

page 5  →  go straight to entry #5  →  frame 37

No searching is needed, because entry #5 always belongs to page 5. The entry doesn’t even need to store the page number.

(b) Associative mapping: the TLB

The TLB is tiny and holds only a few recently used pages, in any order (19, 511, 37, 27, 14, 1, 211, 5, 90, …). Page 5 could be in any slot, so:

• each TLB entry stores the page number (its tag) next to the page table entry, and
• the incoming page number (5) is compared against all entries at the same time.

The entry tagged 5 matches, and it gives frame 37. This is exactly a fully associative cache, where the page number is the tag.

Then: real address = frame number + same offset

Virtual:  [ page 5  | offset 502 ]
Real:     [ frame 37 | offset 502 ]    ← offset is copied unchanged

Why the TLB is usually (fully) associative

TLB misses are expensive (a page table walk), and the TLB is small, so having one comparator per entry is affordable. That’s why TLBs are typically fully associative or highly set associative. It’s the same reasoning as the victim cache.

Any problem with this design w.r.t performance ?

TLB Access Timing

Don’t want TLB in critical path to cache

• But, TLBs are early select -- have to match page name before accessing memory address
• Slow approach is:
  TLB page name -> TLB Page Frame Address -> Cache Access

The problem: the slow, serial path

The cache in this figure is physically addressed: its tags are physical addresses. So the obvious way to access it is:

TLB (translate page #) → get frame # → THEN access the cache
hit time = TLB time + cache time

The TLB lookup sits in the critical path of every load and store, which makes every cache hit slower.

The key observation: the offset bits never change

Translation only changes the page number. The page offset (low 12 bits for a 4 KB page) is identical in the virtual and physical address. So the CPU can start using those bits before translation finishes.

The solution: access the TLB and the cache at the same time

Here is how the figure’s numbers fit together:

Step by step, for one access:

1. At the same time:
   • the 20 high bits (virtual page number) go to the TLB, and
   • the 12 low bits (page offset) go straight to the 4 KB cache to select the block (“block select”). The cache reads out that block’s data and its stored 18-bit tag.
2. The TLB outputs the 18-bit page frame address (the physical page number).
3. Compare the TLB’s frame number with the cache’s tag: hit if they match.

The numbers in the figure:

• 4 KB pages → page offset = log₂(4096) = 12 bits, so VPN = 32 − 12 = 20 bits
• 4 KB direct-mapped cache → index + block offset = log₂(4096) = 12 bits, exactly the page offset
• Physical address = 18-bit frame + 12-bit offset = 30 bits (1 GB of physical memory), so the cache tag = 30 − 12 = 18 bits

This design is called virtually indexed, physically tagged (VIPT): the cache is indexed with bits taken from the virtual address, but compared against physical tags.

“Any requirements to use this method?” — Yes

The cache’s index bits and block offset bits must all come from the page offset, the bits that don’t change during translation:

index bits + block offset bits ≤ page offset bits
⇔  cache size ÷ associativity ≤ page size

In other words, one way of the cache must be no bigger than one page.

Why: if even one index bit came from the virtual page number, that bit could be different in the physical address. You’d then read the wrong set before knowing the translation. A related problem: two virtual addresses that map to the same physical address (aliases) could land in different sets, giving two copies of the same data.

How to get a bigger L1 and keep the trick

• Raise associativity: a bigger cache with more ways keeps each way at 4 KB. That’s why many L1 caches are 32 KB 8-way with 4 KB pages.
• Use bigger pages: the page offset gets more bits.
• Add hardware or OS support for aliases (for example, page coloring, where the OS makes sure the extra index bits are the same in the virtual and physical address).

Solution: Access TLB & cache concurrently
Any requirements to use this method?

An Memory Hierarchy Example

• Page size 8KB
• TLB direct mapped with 256 entries
• L1 cache direct-mapped, 8KB
• L2 cache direct-mapped, 4MB
• Both use 64-byte blocks
• Virtual address 64 bits, physical address 41 bits
• Draw the figure of the memory hierarchy from virtual address to L2 cache access.

you should know how to draw below structure

검산: 합이 주소 길이와 맞는지

가상 주소: TLB tag 43 + TLB index 8 + page offset 13 = 64 ✓
물리 주소 (L1 기준): L1 tag 28 + index 7 + offset 6 = 41 ✓
물리 주소 (L2 기준): L2 tag 19 + index 16 + offset 6 = 41 ✓

2단계: 그림의 흐름

① 가상 주소를 둘로 나눔

64비트 = 가상 페이지 번호 51 | page offset 13

② TLB와 L1을 동시에 찾음 (지난번에 배운 parallel access, VIPT)

TLB 쪽: 페이지 번호 51비트 = TLB tag 43 | TLB index 8. index 8비트로 TLB 칸 하나를 고르고, 저장된 TLB tag(43)와 비교합니다 (왼쪽 =?). 같으면 TLB hit이고, 그 칸의 TLB data 28비트 = 물리 페이지 번호가 나옵니다.
L1 쪽 (동시에): page offset 13비트 = L1 index 7 | block offset 6. 번역이 필요 없는 비트라 바로 L1 칸을 골라 L1 tag(28)와 data(512)를 읽습니다.

③ L1 hit 판단

TLB가 준 물리 페이지 번호 28비트(“L1 tag compare address”)와 L1에서 읽은 tag 28비트를 비교합니다 (가운데 =?). 같으면 L1 hit → block offset으로 원하는 워드를 골라 CPU로 보냅니다.

④ L1 miss면 물리 주소를 만들어 L2로

물리 주소 41비트 = 물리 페이지 번호 28 (TLB에서) | page offset 13 (원래 주소에서). 이걸 L2 기준으로 다시 나눕니다: L2 tag 19 | L2 index 16 | block offset 6

⑤ L2 접근

index 16비트로 L2 칸을 고르고, 저장된 tag(19)와 비교합니다 (아래 =?). 같으면 L2 hit → 데이터를 L1이나 CPU로 보냅니다.

왜 L1 tag를 43에서 28로 고쳤나

교과서 원래 그림에는 L1 cache tag <43>로 나와 있는데, 28이 맞습니다 (그래서 고쳐 쓰신 거예요).

L1 tag는 TLB가 준 물리 페이지 번호(28비트)와 비교됩니다. 비교하는 두 값의 길이가 같아야 하니 28비트입니다.
계산으로도 물리 주소 41 − index 7 − offset 6 = 28입니다.

43은 TLB tag 길이와 헷갈린 오타입니다.

왜 L1은 TLB와 동시에, L2는 번역 후에 접근하나

지난번 규칙을 적용하면:

동시 접근 조건: index 비트 + block offset 비트 ≤ page offset 비트

그래서 L1은 VIPT(가상 주소로 index, 물리 주소로 tag 비교)이고, L2는 번역이 끝난 물리 주소로만 접근합니다 (PIPT). L2는 L1 미스 뒤에야 접근하니, 그때는 이미 번역이 끝나 있어서 기다릴 일이 없습니다.

시험에서 그리는 순서

1. 가상 주소 → VPN | page offset (offset = log₂ 페이지 크기)
2. VPN → TLB tag | TLB index (index = log₂ TLB 칸 수, direct-mapped 기준)
3. TLB data = 물리 주소 − page offset
4. page offset → L1 index | block offset, L1 tag = 물리 주소 − index − offset
5. 물리 주소 = TLB data | page offset
6. 물리 주소 → L2 tag | L2 index | block offset
7. 비교기 3개: TLB tag, L1 tag, L2 tag
8. 마지막으로 합이 64 / 41인지 검산

시험에서 숫자가 바뀌어도 이 순서대로 log₂만 하면 됩니다. 예를 들어 TLB가 4-way 256칸이면 TLB index = log₂(256 ÷ 4) = 6, TLB tag = 51 − 6 = 45가 됩니다.