Virtual memory was invented in Manchester for the Atlas, inaugurated in December 1962: a core of 16K words and a drum of 96K words were made to look like one "one-level store" of 512-word pages. A page missing from the core raised a page-fault interrupt for the supervisor, and 32 associative page address registers translated in hardware.
Virtual memory in one lesson, and VIPT: start the cache before the TLB answers
After this lesson you will translate a virtual address into a physical one by hand, tell a TLB miss from a page fault, and decide with one inequality, cache size / associativity ≤ page size, whether an L1 cache can start its lookup before the TLB answers without synonym problems.
Print the address of a variable in a running program and you get something like 0x7FFE_1234, the notes' Example 19 (p. 358). That is not where the byte sits in RAM: it is a virtual address, a name the operating system made up for your process. Yet its last three hex digits, 234, are true: they are also the last three digits of the RAM location that holds the byte.
Second fact. For about a decade Intel's L1 data cache was 32 KB with 8 ways. When it finally grew, in 2019, it became 48 KB with 12 ways. Divide: 32 / 8 = 48 / 12 = 4 KB, exactly the size of a page.
Why should a cache, a block of hardware, take its shape from a page, a notion of the operating system? Make a guess and keep it. By the end of the lesson you will derive the answer in one line, from the first fact.
Pages, frames and the page table
Every program believes it owns one large, continuous address space of \(2^{32}\) or \(2^{64}\) bytes; real RAM is finite and fragmented (p. 357). Paging reconciles the two: the operating system and the hardware cut both spaces into blocks of one fixed size and keep, for every program, a map from its blocks to real ones.
The notes picture a city of identical hotel buildings, each with rooms 0 to 4095 (p. 358). Your booking names a building and a room; reception may move you to another building, but it never changes the room number. Room 0x234 stays room 0x234.
Virtual page — a block of the virtual address space, the program's view. All pages have one size, commonly 4 KB (2 MB and 1 GB exist too); each process has its own set, which isolates it from the others (p. 357).
Physical page, or frame — a block of RAM of the same size. Several virtual pages, of different processes or of one, may map to the same frame: shared memory.
Page table — the map of one process, kept in memory. It is indexed by the virtual page number (VPN); each entry holds the physical frame number (PFN) and some flags.
An address therefore has two fields: the low bits are the page offset, the byte inside the page (12 bits for pages of 4 KB = \(2^{12}\) bytes), and the bits above it are the page number. Translation replaces the page number and copies the offset:
\[ \text{VA} = \text{VPN} \mid \text{page offset} \]
\[ \text{PA} = \text{PFN} \mid \text{page offset} \]
\[ \text{PA} = \text{PFN} \times P + \text{page offset} \]
- VPN
- virtual page number, the high bits of the virtual address: 20 bits for 32-bit addresses and 4 KB pages
- PFN
- physical frame number, read from the page table; the notes also write PPN, physical page number (pp. 360–362)
- \(P\)
- page size; the page offset has \(\log_2 P\) bits and is the same in both addresses
Example 19 (p. 358), step by step. In the 32-bit virtual address 0x7FFE_1234 (the underscore only groups the hex digits by four), the last three digits are the offset, 0x234, and the five before them the VPN, 0x7FFE1. The page table maps VPN 0x7FFE1 to PFN 0x01AB0. Put the frame number in front of the unchanged offset: PA = 0x01AB0 | 0x234 = 0x01AB_0234 = 0x01AB0 × 4096 + 0x234 (Fig. 1).
Why bother? Hennessy & Patterson (Appendix B.4; not in the notes) list four gains: capacity, since RAM becomes a cache for the disk and a program may exceed it; protection, since a process reaches only the frames its table maps, with permissions checked on every access; relocation, since a program runs wherever its frames are; and sharing: two page tables may point to one frame — keep that one for section 4.
Virtual memory is one more level of the hierarchy, so the four questions of lesson 23 apply, with pages for blocks and frames for lines. Every answer follows from one number: a miss at this level, a page fault, goes to the disk and costs millions of cycles.
| Question | Answer | Why |
|---|---|---|
| Placement | in any frame: fully associative | a page fault costs millions of cycles, so the miss rate must be as low as possible |
| Identification | the page table, indexed by the VPN; the TLB keeps recent entries | no search: the VPN is an index, so no tags are compared |
| Replacement | approximately LRU: a use (reference) bit per page, set on access and cleared now and then by the OS | a wrong victim costs a disk access; exact LRU over millions of pages is too costly |
| Write policy | always write-back, with a dirty bit per page | writing through to the disk on every store is out of the question |
Why not one flat page table?
A flat table for 32-bit addresses and 4 KB pages has \(2^{20}\) entries, 4 MB per process at 4 bytes each, mostly for pages never touched. Real systems build a tree of small tables indexed by fields of the VPN (x86-64: four levels of 9 bits, \(4 \times 9 + 12 = 48\) bits), and a TLB miss walks several dependent reads (Hennessy & Patterson; not in the notes).
Translation replaces the page number and copies the page offset: with 4 KB pages the last 12 bits, three hex digits, are the same in the virtual and in the physical address.
The TLB: a cache for translations
The page table lives in memory, so reading it first would add a memory access to every load, store and instruction fetch (p. 359). The cure is the idea of this whole chapter: keep the recent entries in a small, fast memory.
Translation lookaside buffer (TLB) — "a small, fast cache that stores the most recent virtual-to-physical address translations" (p. 359). Its tag is the VPN; its data are the PFN and the flags of the page-table entry.
On every access the CPU generates a virtual address and checks the TLB (p. 359). A TLB hit gives the physical address at once; a TLB miss walks the page table in memory, slowly, and inserts the result into the TLB. In the notes' hotel, the TLB is a post-it note with your current room key, so you need not queue at reception every time.
The textbook picture, not in the notes: a TLB has tens of entries, fully or highly associative, often split into instruction and data TLBs behind a larger second-level TLB, and answers in about a cycle; its entries carry the protection bits, checked on every access. The memory it covers, its reach, is entries × page size: 64 entries × 4 KB = 256 KB. A miss is refilled by a hardware page walker (x86, ARM) or a software handler (MIPS), in tens of cycles.
Keep two events apart. A TLB miss means only that the translation is not in the small cache: usually the page is in RAM, and the walk finds a valid entry. A page fault means the entry is invalid: the page is not in RAM at all. The hardware raises an exception; the operating system reads the page from the disk into a free frame, sets the valid bit and restarts the instruction — millions of cycles, and a restart that needs precise exceptions (lesson 17).
A TLB miss costs a page walk of tens of cycles and never touches the disk; a page fault costs a trip to the disk through the operating system, millions of cycles.
Start the cache before the TLB answers
Now put the TLB in front of the L1. A physically addressed cache (lesson 23) needs the physical index to select a set, so it waits for the TLB: cache hit alone 1 cycle, TLB lookup 1 cycle, in sequence 2 cycles — "this doubles the critical latency" (p. 360). More than 90 % of accesses are hits, and the hit time is the term of AMAT that every access pays.
Look at what the cache needs, and when: the index first, to select a set and read its tags; the tag only at the end, for the comparison. And the index of a small cache sits in the low bits, inside the page offset, which translation does not change. In the hotel city, a porter who knows only your room number can already walk to the right floor — every building has the same layout — and check the building name on the door when reception phones it through.
Virtually indexed, physically tagged (VIPT) cache — a cache where "the index (which set to look at) is taken from the virtual address" and "the tag (to confirm if it's the right block) comes from the physical address after TLB translation" (p. 360).
The notes' five steps (p. 360), drawn in Fig. 2: the CPU issues a virtual address; its index bits select a set at once; meanwhile the TLB translates the VPN into the PFN; the PFN, which is the physical tag, is compared with the tags of the selected set; a match is a hit.
The set read and the translation now overlap. With \(T_{\text{TLB}}\) for the TLB lookup, \(T_{\text{read}}\) for indexing the cache and reading the set, and \(T_{\text{cmp}}\) for comparing the tags and selecting the way:
\[ T_{\text{serial}} = T_{\text{TLB}} + T_{\text{read}} + T_{\text{cmp}} \]
\[ T_{\text{VIPT}} = \max(T_{\text{TLB}},\, T_{\text{read}}) + T_{\text{cmp}} \]
If the TLB answers before the set has been read, a VIPT hit costs what the cache alone costs. The widget puts both designs on one clock.
"A VIPT cache skips the TLB on a hit." No: the TLB is read on every access. Its PFN is the tag that decides the hit, and its permission bits are checked. VIPT takes the TLB off the critical path; it does not take it away.
Index and tag can each come from either address, which gives three designs worth knowing:
| Design | Index from | Tag from | TLB on a hit | Price |
|---|---|---|---|---|
| PIPT: physically indexed, physically tagged | physical address | physical address | in series | the TLB time on every hit; used for L2 and L3, which start after the translation is done (p. 364) |
| VIVT: virtually indexed, virtually tagged | virtual address | virtual address | not needed | synonyms (p. 360); homonyms and cache flushes (not in the notes) |
| VIPT: virtually indexed, physically tagged | page-offset bits of the virtual address | physical address | in parallel | one way may not be larger than one page |
The textbook name of VIPT is "avoiding address translation during indexing of the cache", a hit-time technique. The January 2026 quiz transcribed in the notes (pp. 503–504) offers it as a miss-penalty one, and the notes' solution accepts it (lesson 24 and lesson 26 settle that quiz). A miss still pays its full penalty; VIPT shortens every hit.
VIPT reads the set with page-offset bits while the TLB translates, then compares the physical tag: the TLB leaves the critical path of a hit, not the machine.
Two names for one byte: synonyms
Why not tag the cache with virtual addresses too? A virtually indexed, virtually tagged (VIVT) cache would need the TLB only on a miss. The obstacle is the synonym, or alias: two virtual addresses that map to the same physical address — normal with memory shared between processes, memory-mapped files, a page mapped twice (p. 361).
The notes' Example 20 (p. 362) takes two aliases, VA1 = 0x4000_1234 and VA2 = 0x8000_1234, both mapped to PA = 0x1000_1234. With 4 KB pages, 64 B blocks and a 4 KB direct-mapped cache of 64 sets, the 12-bit page offset splits into a 6-bit index and a 6-bit block offset. Do the arithmetic before reading the notes' story:
| Field (bits) | VA1 | VA2 | PA |
|---|---|---|---|
| address | 0x4000_ | 0x8000_ | 0x1000_ |
| page number [31:12] | 0x40001 | 0x80001 | 0x10001 |
| page offset [11:0] | 0x234 | 0x234 | 0x234 |
| index [11:6] | 001000 = 8 | 001000 = 8 | 001000 = 8 |
| block offset [5:0] | 110100 = 52 | 110100 = 52 | 110100 = 52 |
All three share the page offset 0x234 = 0010 0011 0100, so they share the index: set 8. The notes put VA1 in "Set 10" and VA2 in "Set 42" of a VIVT cache and tag the VIPT line "0x1000"; neither survives the arithmetic.
Duplication needs room for both names. Give the cache a second way: 8 KB, 2-way, still 4 KB per way, so still 64 sets and index [11:6]. Run four accesses, write-back with write-allocate and 0 in memory at the start: write 7 through VA1, read through VA2, write 9 through VA2, read through VA1.
| Type of memory access | Hit/ Miss Type | Value returned | Cache Tag | Cache Address | Dirty bit |
|---|---|---|---|---|---|
| Write 7 via VA1 | Cold-start Miss | — | 0x40001 | way 0 | 1 |
| Read via VA2 | Cold-start Miss | 0: stale, should be 7 | 0x80001 | way 1 | 0 |
| Write 9 via VA2 | Hit | — | 0x80001 | way 1 | 1 |
| Read via VA1 | Hit | 7: stale, should be 9 | 0x40001 | way 0 | 1 |
| Type of memory access | Hit/ Miss Type | Value returned | Cache Tag | Cache Address | Dirty bit |
|---|---|---|---|---|---|
| Write 7 via VA1 | Cold-start Miss | — | 0x10001 | way 0 | 1 |
| Read via VA2 | Hit | 7 | 0x10001 | way 0 | 1 |
| Write 9 via VA2 | Hit | — | 0x10001 | way 0 | 1 |
| Read via VA1 | Hit | 9 | 0x10001 | way 0 | 1 |
Before: virtual tags (VIVT)
After: physical tags (VIPT)
VIPT avoids this with two facts at once (p. 361). The index comes from page-offset bits, identical in every alias, so all aliases select the same set; the tag is the physical page number, identical too, so all of them match the same line. One copy, no stale data. The notes call it the page offset trick: bits that translation never changes can index the cache before translation ends.
Virtual tags have a second problem, not in the notes: homonyms, one virtual address naming different frames in different processes. A VIVT cache must be flushed at every context switch or extend its tags with an address-space identifier; physical tags never meet it.
Aliases share their page offset and their physical page: VIPT sends them to one set and matches them against one tag, so the block has a single copy.
The size law: cache size / associativity ≤ page size
"Ok, now we can sleep peacefully knowing that the Synonym Problem has been solved." "Not at all!" (p. 363): the trick needs every index bit inside the page offset, and a larger cache needs more index bits. Example 21 (p. 364): 4 KB pages give 12 offset bits, 64-byte blocks take 6, so 6 index bits are left, 64 sets at most. A 32 KB 4-way cache has 8 KB per way, 128 sets, 7 index bits; the seventh, bit 12, belongs to the VPN.
Why that hurts: bit 12 is a page-number bit, and aliases need not agree on it. If VA1 = 0x4000_1234 and a third name, VA3 = 0x8000_0234, map to the same frame, the index [12:6] puts VA1 in set 72 and VA3 in set 8 (bit 12 is 1 in VA1, 0 in VA3). Two sets, two copies: the synonym problem is back, physical tags or not (p. 363).
Count the sets: the cache holds \(C / B\) blocks, \(A\) per set.
\[ S = \frac{C}{A \times B} \]Count the bits: index \(i = \log_2 S\), block offset \(o = \log_2 B\), page offset \(p = \log_2 P\). VIPT needs index and block offset inside the page offset:
\[ i + o \le p \]A sum of logarithms is the logarithm of a product:
\[ \log_2 S + \log_2 B \le \log_2 P \] \[ S \times B \le P \]Sets times block size is the size of one way, the cache divided by its ways:
\[ S \times B = \frac{C}{A} \quad\Rightarrow\quad \frac{C}{A} \le P \]Example 21 fails by one bit; one more factor of two in \(A\) fixes it:
\[ \frac{32\ \text{KB}}{4} = 8\ \text{KB} \gt 4\ \text{KB} \] \[ k = i + o - p = 7 + 6 - 12 = 1 \]With 8 ways, 32 KB / 8 = 4 KB: equality. With 4 ways the maximum is 4 × 4 KB = 16 KB (p. 364).
Rearranged: the largest VIPT cache with \(A\) ways and the fewest ways for a cache of size \(C\). A law that fails by \(k\) bits lets an alias sit in any of \(2^k\) sets.
\[ C_{\max} = A \times P \qquad A_{\min} = \frac{C}{P} \]
\[ \frac{\text{cache size}}{\text{associativity}} \le \text{page size} \]
- cache size / associativity
- one way, \(S \times B\) bytes: what index and block offset can reach
- page size
- what the page offset can reach: the only bits known before the TLB answers
"VIPT caps the L1 at the size of a page." No: it caps one way at a page. Twelve ways of 4 KB make 48 KB, all VIPT-safe.
Back to the hook
32 KB / 8 ways = 4 KB, one page: that L1 used every index bit the page offset allows (p. 364 gives the same example), and to grow it added ways: 48 KB / 12 = 4 KB again. The first fact of the hook is the reason: only the page offset, the last three hex digits, is known before the TLB answers, so one way can cover at most one page. With 16 KB pages, as on Apple silicon, 8 ways would allow 8 × 16 KB = 128 KB.
The lower levels escape the law: "Higher-level caches (L2, L3) are usually physically indexed, physically tagged (PIPT), so they don't suffer this limitation" (p. 364). They are accessed only after an L1 miss, when the TLB has long answered, so there is nothing left to hide.
Adding ways is not free: each adds a tag comparison, widens the multiplexer and costs energy on every access. So VIPT pushes L1 associativity up while a short hit time, the theme of lesson 28, pushes it down. Way prediction (lesson 25) eases the conflict by reading the predicted way first; many processors also accept a pipelined L1 hit of two or more cycles. Other escapes (Hennessy & Patterson; not in the notes): OS page colouring, so that all aliases of a frame agree on the leaking index bits; hardware that checks the \(2^k\) candidate sets on a miss, as in the 64 KB 2-way L1 of the AMD Opteron; larger pages.
A VIPT L1 keeps every alias in one set only while cache size / associativity ≤ page size: to grow, it adds ways or uses larger pages.
Exam-style questions
The three official papers have no question on virtual memory, so these questions follow the forms the papers use for the cache (the July 2024 address quiz and cache table, the formula-sheet AMAT) and the June 2026 open question. The model answers are computed here; there are no official solutions.
Explain the main concepts and benefits of each one of the following techniques used in the memory hierarchy of modern processors: 1. Paged virtual memory; 2. Per-process page tables; 3. Translation lookaside buffer (TLB); 4. Handling of TLB misses and page faults; 5. Virtually indexed, physically tagged (VIPT) L1 caches; 6. Indexing the cache with page-offset bits only; 7. Higher associativity in a VIPT L1 cache; 8. Physically indexed, physically tagged (PIPT) L2 and L3 caches.
Show model answer
1. The virtual and the physical address spaces are divided into pages of one fixed size (for example 4 KB). Each process sees a large, private, contiguous virtual space; the OS maps its pages onto physical frames anywhere in RAM. A virtual address is VPN | page offset; translation replaces the VPN with the PFN and leaves the offset unchanged. Benefits: programs larger than RAM (main memory acts as a cache for the disk), protection and isolation between processes, relocation, sharing of frames; fixed-size pages avoid external fragmentation. Cost: a translation on every access.
2. Each process has a page table in memory, indexed by the VPN; each entry holds the PFN, a valid bit, a dirty bit, a use bit and protection bits. The same virtual address in two processes maps to different frames (isolation), two VPNs may point to one frame (sharing), and the hardware enforces the permissions. Because a page fault costs millions of cycles, placement is fully associative (any frame), replacement approximates LRU with the use bit, and the write policy is always write-back with the dirty bit. Cost: memory for the tables, hence multi-level tables.
3. A small, fast, fully or highly associative cache of recent translations: tag = VPN, data = PFN and the flags. It is looked up on every access; on a hit the physical address is available in about one cycle, with the protection check. Benefit: without it every access would need an extra memory access to read the page table. Cost: it must stay tiny (tens of entries) to answer within the cycle.
4. On a TLB miss the page table is walked in memory, by a hardware walker or a software handler, in tens of cycles; if the entry is valid it is inserted into the TLB and the access completes, with no OS involvement for a hardware walker. If the entry is invalid, the page is not in RAM: a page-fault exception transfers control to the OS, which chooses a frame (writing back a dirty victim), reads the page from the disk, updates the entry and restarts the faulting instruction; this costs millions of cycles and requires precise exceptions. A TLB miss is not a page fault.
5. The cache index is taken from the virtual address and the tag from the physical address. The set is read while the TLB translates the VPN; the PFN is then compared with the tags of the set. Benefit: the TLB latency leaves the hit time, max(TLB, set read) + compare instead of TLB + cache, for example 1 cycle instead of 2 (notes, p. 360); since most accesses are hits, the AMAT drops. The TLB is still read on every access, for the tag and the permissions. Cost: the size restriction of point 7.
6. Translation never changes the page offset, so index and block-offset bits taken from it are the same in the virtual and the physical address and can be used before the TLB answers (the page offset trick). It also solves synonyms, two virtual addresses mapped to one physical address (shared memory, mapped files): all aliases select the same set and, with physical tags, match the same line, so only one copy exists and no stale value can be read. A VIVT cache could keep two copies with different virtual tags.
7. All index bits must lie in the page offset: index bits + block-offset bits ≤ page-offset bits, that is cache size / associativity ≤ page size. With 4 KB pages and 64-byte blocks a 32 KB 4-way cache (8 KB per way, 7 index bits) takes one index bit from the VPN; 8 ways make it safe (4 KB per way), and 48 KB needs 12 ways. A larger VIPT L1 therefore needs more ways. Cost: more comparators, a wider way multiplexer, more energy and a longer hit time, which way prediction mitigates. Alternatives: page colouring, hardware alias detection, larger pages.
8. L2 and L3 use the physical address for both index and tag. They are accessed only after an L1 miss, when the TLB has already translated the address, so translation adds nothing to their access and they have no synonym problem and no page-size limit: they can be large (MBs) and highly associative. Their longer hit time is acceptable because it is paid only on L1 misses.
The form is the June 2026 question: eight sub-points, about five lines each. For each technique the examiner looks for the mechanism, what it buys and what it costs. Sub-points 4 and 7 carry the usual traps: a TLB miss is not a page fault, and the law limits one way, not the whole cache.
A processor has 32-bit virtual addresses, 4 KB pages and an L1 data cache with 32-byte blocks. 1. The L1 is 8 KB, 2-way set-associative: give the structure of the address as seen by the cache (tag | index | offset, with bit positions) and say whether the cache can be virtually indexed and physically tagged without synonym problems. 2. The designers want 64 KB, keeping 2 ways: how many index bits come from the virtual page number, and in how many sets could an alias of a block be found? 3. What is the minimum associativity of a 64 KB VIPT L1? 4. Give two other ways to make the 64 KB 2-way cache safe.
Show model answer
Page offset = log₂ 4096 = 12 bits, [11:0]. Block offset = log₂ 32 = 5 bits, [4:0].
1. Sets = 8 KB / (32 B × 2) = 128, so the index has 7 bits, [11:5], and the tag 32 − 7 − 5 = 20 bits, [31:12]: |20-bit tag | 7-bit index | 5-bit offset|. Index + offset = 7 + 5 = 12 bits = the page offset; equivalently 8 KB / 2 = 4 KB ≤ 4 KB. The cache can be VIPT, and its tag is exactly the PFN.
2. Sets = 64 KB / (32 B × 2) = 1024, so the index has 10 bits, [14:5]. Bits 14, 13 and 12 lie above the page offset: k = 10 + 5 − 12 = 3 bits come from the VPN, and an alias may be in any of 2³ = 8 sets.
3. Minimum associativity = 64 KB / 4 KB = 16 ways: 128 sets, index [11:5] again.
4. Pages of 32 KB (15 offset bits contain index [14:5]); page colouring by the OS, so that all aliases of a frame agree on virtual-address bits 14 to 12; hardware that checks the 8 candidate sets on a miss and removes a duplicate (as the AMD Opteron did).
Part 1 is the address-structure quiz of July 2024 (lesson 23) with one more question: do index and offset fit in the page offset? The examiner checks the count k = i + o − p and the \(2^k\) candidate sets, and that the fixes act on C / A or on P, never on the block size.
Pages are 4 KB. The L1 data cache is 4 KB, direct-mapped, with 64-byte blocks, write-back and write-allocate. The operating system maps the virtual addresses VA1 = 0x4000_1234 and VA2 = 0x8000_1234 to the same physical address PA = 0x1000_1234, where memory holds 0. The CPU performs: (1) write 7 via VA1; (2) read via VA2; (3) write 9 via VA2; (4) read via VA1. Give the set that all four accesses use, then complete the table Type of memory access | Hit/ Miss Type | Cache Tag | Dirty bit | Write in memory | Value returned, first for a virtually indexed, virtually tagged cache, then for a virtually indexed, physically tagged one. Does either design return a wrong value?
Show model answer
64 sets: index = bits [11:6] of the page offset 0x234 = 001000 = set 8 for all three addresses. Virtual tags: 0x40001 (VA1) and 0x80001 (VA2); physical tag: 0x10001.
VIVT:
| Type of memory access | Hit/ Miss Type | Cache Tag | Dirty bit | Write in memory | Value returned |
|---|---|---|---|---|---|
| Write 7 via VA1 | Cold-start Miss | 0x40001 | 1 | No | — |
| Read via VA2 | Cold-start Miss | 0x80001 | 0 | Yes (7) | 7 |
| Write 9 via VA2 | Hit | 0x80001 | 1 | No | — |
| Read via VA1 | Conflict Miss | 0x40001 | 0 | Yes (9) | 9 |
VIPT:
| Type of memory access | Hit/ Miss Type | Cache Tag | Dirty bit | Write in memory | Value returned |
|---|---|---|---|---|---|
| Write 7 via VA1 | Cold-start Miss | 0x10001 | 1 | No | — |
| Read via VA2 | Hit | 0x10001 | 1 | No | 7 |
| Write 9 via VA2 | Hit | 0x10001 | 1 | No | — |
| Read via VA1 | Hit | 0x10001 | 1 | No | 9 |
In the VIVT table, "Yes (7)" means that the dirty line of VA1, holding 7, is written back to PA 0x1000_1234 before VA2's block is fetched; that fetch then reads the 7.
Neither design returns a wrong value. The aliases share set 8, and a direct-mapped set holds one block: the VIVT cache never has two copies, it pays 3 misses out of 4 and 2 write-backs instead (ping-pong). The VIPT cache has 1 miss and 3 hits. With a second way (8 KB 2-way) the VIVT cache would keep both copies and both reads would return stale values.
This is the notes' own Example 20 configuration, run to the end: it is the counterexample to their "Set 10 / Set 42" story (red pen in section 4). The examiner checks the set from the page offset, the tags as page numbers (0x40001, not 0x4000), and the write-backs. A VIVT cache must also translate the victim's address to write it back to PA 0x1000_1234; the table assumes it does.
A physically indexed L1 cache waits for the TLB: TLB lookup 1 clock cycle, then the cache hit 1 clock cycle. A VIPT version overlaps the TLB lookup completely with the indexing, so its hit takes 1 clock cycle. In both designs the miss rate is 5 % and the miss penalty 20 clock cycles. How much is the speed-up of the average memory access time of the VIPT design over the serial one?
Show model answer
\[ \text{AMAT}_{\text{serial}} = 2 + 0.05 \times 20 = 3 \]
\[ \text{AMAT}_{\text{VIPT}} = 1 + 0.05 \times 20 = 2 \]
Speed-up = 3 / 2 = 1.5.
The miss term is the same 1 cycle in both designs: only the hit time changes. The widget of section 3 shows that the gap stays one cycle at any miss rate.
(SINGLE ANSWER) An L1 data cache of 64 KB with 64-byte blocks must be virtually indexed and physically tagged on a machine with 4 KB pages. What is the minimum associativity such that no index bit comes from the virtual page number?
Show model answer
Answer 3. Minimum associativity = cache size / page size = 64 KB / 4 KB = 16. The block size does not enter: it moves bits between index and block offset, not out of the page offset.
The quick route is the law, C / A ≤ P; the slow route counts sets and bits. Both give 16. Answer 2 is the near miss: 8 ways halve the overflow, but bit 12 is still a VPN bit.
(SINGLE ANSWER) In a virtually indexed, physically tagged cache, the tag stored with each block is:
Show model answer
Answer 2. The index comes from the page-offset bits of the virtual address, the tag from the physical address: the PFN delivered by the TLB is compared with the tags of the selected set.
Read the name backwards: physically tagged. The distractors are the other two designs and the index.
(True/False) A TLB miss means that the page is not in main memory, so the operating system must load it from the disk.
Show model answer
False. On a TLB miss the page table in memory is walked and the translation inserted into the TLB, in tens of cycles. Only if the page-table entry is invalid does a page fault occur, and the OS loads the page from the disk, in millions of cycles.
The distinction between the two misses is the whole point. If asked to motivate, give the cost of each.
Check yourself
Pages are 4 KB. A process accesses the virtual address 0x0040_3A2C, and its page table maps VPN 0x00403 to PFN 0x001F2. Which physical address does the access reach?
The TLB holds the translation of VPN 0x7FFE1, with 4 KB pages. Which of these accesses hit in the TLB? Select all that apply.
An access misses in the TLB, and the page walk finds a valid entry for its VPN. What happens next?
Why can a VIPT cache select its set before the TLB has answered?
Intel's L1 data cache of 2019 is 48 KB, 12-way, with 64-byte blocks, and pages are 4 KB. Can it be VIPT without synonym problems?
A 64 KB 4-way L1 on a machine with 4 KB pages is not VIPT-safe. Which changes, each on its own, would make it safe? Select all that apply.
The notes' Example 20 cache, 4 KB, direct-mapped, 64-byte blocks, 4 KB pages, with virtual tags. A program alternates reads through VA1 = 0x4000_1234 and VA2 = 0x8000_1234, aliases of one physical address. What happens?
Key take-aways
- Paging cuts virtual and physical memory into pages of one size; a virtual address is VPN | page offset, and translation replaces the VPN with the PFN read from the per-process page table, leaving the offset untouched.
- The TLB is a small cache of translations: a hit gives the PFN in about a cycle, a miss walks the page table in tens of cycles, and only an invalid entry is a page fault, handled by the OS in millions of cycles.
- A physically indexed L1 waits for the TLB on every hit. A VIPT L1 selects its set with page-offset bits while the TLB translates, then compares the physical tag: the TLB leaves the hit path but is still used on every access.
- Synonyms are two virtual addresses for one physical address. Virtual tags allow two copies and stale data; page-offset index plus physical tag give every alias the same set and the same line.
- VIPT keeps synonyms in one set only if cache size / associativity ≤ page size, which follows from S × B = C / A. A larger VIPT L1 needs more ways (32 KB 8-way, 48 KB 12-way with 4 KB pages) or larger pages, unless the OS or extra hardware handles the aliases; L2 and L3 are PIPT.
- At the exam, "avoiding address translation during indexing of the cache" is a hit-time technique, not a miss-penalty one.
What to watch and read
-
Virtual Memory (playlist)
David Black-Schaffer, Uppsala University14 short videos
Address translation, page tables, the TLB and page faults drawn by hand in small steps: the first few videos before section 1 give you the picture this lesson builds on.
-
Aliasing in Virtually Accessed Caches
Milos Prvulovic, Georgia Tech HPCA (Udacity)a few minutes
With section 4: why two virtual names for one physical block break a virtually tagged cache.
-
Real VIPT Caches
Milos Prvulovic, Georgia Tech HPCA (Udacity)a few minutes
With the bit-slicer of section 5: why index and offset bits must fit inside the page offset, and what that does to the size of real L1 caches.
-
OSTEP homework simulators
Arpaci-Dusseau, Operating Systems: Three Easy Pieces
paging-linear-translate.py generates random virtual addresses and page tables in Python: translate them by hand as in Example 19, then check yourself with -c.
-
Paging: Faster Translations (TLBs)
Arpaci-Dusseau, OSTEP chapter 1916 pages
The TLB material the notes leave out: hit and miss flow, hardware against software miss handling, and what a context switch does to the TLB.