Part IIThe Core

Virtual Memory, TLBs, and Memory Ordering

July 31, 2026·85 min read·advanced

1.1 Say the separation out loud before anything else

This note covers two subjects that have nothing to do with each other. They are taught together, tested together, and filed under the same heading in every syllabus, entirely because the English word "memory" appears in both names. Conflating them is the single most common way to sound confused in an interview, so fix the boundary now, before any mechanism.

Address translation is about one core and one program. A program emits an address. Something has to turn that address into a location in physical DRAM, apply permission checks along the way, and do it fast enough that the program does not notice. There is no second core anywhere in this problem. A single-core machine with one process running still needs all of it.

Memory ordering is about several cores and what they promise each other. Core 0 performs two stores. Core 1 performs two loads. What orders of events is core 1 allowed to observe? There is no page table anywhere in this problem. A machine with no virtual memory at all, addressing physical DRAM directly, still has the entire memory ordering question in full force.

One is a lookup problem. The other is a visibility problem. They meet in exactly one place in a real design, which is the load-store unit, because that unit happens to be where both the TLB lookup and the ordering enforcement physically live. That shared address is a fact about floorplanning, not about the ideas.

1.2 The map

Parts 2 through 6 are translation. Part 2 motivates it, Part 3 builds the page table, Part 4 covers huge pages, Part 5 covers the TLB, Part 6 covers the interaction with the L1 cache that constrains L1 cache design across the entire industry. Parts 7 through 9 are ordering. Part 7 builds the consistency models from a two-line program, Part 8 covers barriers and atomics, Part 9 covers the machine organization that makes ordering a question at all.

02.Part 2, why address translation exists

2.1 Build the machine without it and watch it fail

Start with a machine that has no translation. A program says "load from address 4096" and the memory controller reads physical DRAM byte 4096. Direct, fast, and simple. Now try to actually use it.

Failure one, programs can read each other. Run a text editor and a password manager at the same time. The password manager holds a decrypted key at physical address 0x8000. Nothing whatsoever stops the text editor from executing a load from 0x8000. Not malice, not even a bug necessarily, just an ordinary pointer arithmetic slip. There is no mechanism to appeal to, because both programs are naming the same physical bytes with the same numbers and the hardware has no way to know which program is entitled to which bytes. Every program can read and write all of memory including the operating system's own data structures. That is not a security weakness to be patched, it is the absence of any security model at all.

Failure two, programs cannot be placed anywhere. A compiler produces a binary. Somewhere in that binary is an instruction LDR x0, [0x401A38], a load from a fixed address that the linker chose. That address was baked in at link time. Now run two copies of the same program at once. Both want 0x401A38. Both want the same physical byte to hold different values. You cannot run two copies. Worse, run a different program that also happened to link its data at 0x401A38 and the two collide too. The only fixes without translation are to relocate every address in the binary at load time, which means the loader must know where every address-shaped number in the file lives and patch them all, or to require every program in the system to be assigned a disjoint address range at build time, which is unworkable the moment anyone installs software.

Failure three, you cannot run more than you have. The machine has 8 GB of DRAM. Open a photo editor holding a 3 GB image, a browser with 40 tabs holding 4 GB, and a compiler wanting 2 GB of heap. Total demand is 9 GB. On a machine without translation the third program simply fails to allocate, and it fails even though at any given instant most of that 9 GB is untouched, because the browser's tab number 37 has not been looked at in an hour and the photo editor is only working on a small region of the image. The memory is committed but not in use, and there is no way to exploit that fact because a program's address 0x50000000 is physically byte 0x50000000 and nothing can move it.

2.2 The fix is one level of indirection

All three failures come from the same root. The number the program says is the number the DRAM uses. Break that identity and all three dissolve at once.

Virtual memory inserts a translation step. The program emits a virtual address, hardware translates it to a physical address, and DRAM sees only the physical one. The translation is per-process, controlled by the operating system, and enforced by hardware on every single access.

Figure 1. Without translation the number the program emits is the number DRAM reads, so two copies of a binary collide on the same byte. A per-process translation step breaks that identity and sends the same virtual address to a different physical byte in each process.

Now walk the three failures back. Isolation falls out because the text editor's map has no entry pointing at the password manager's physical page, so the text editor cannot name it. Not "is not allowed to name it," literally cannot, because there is no virtual address in its map that translates there. Access control becomes a property of what exists in a table rather than a check somebody has to remember to write. Relocation falls out because two copies of the same binary both use virtual 0x401A38 and their maps send them to different physical frames. The binary never has to be patched. Over-commitment falls out because a virtual address does not have to have a physical frame behind it at this instant. Mark the entry invalid, and when the program touches it the hardware raises a fault, the operating system finds the data on disk, loads it into some free frame, fixes the entry, and restarts the instruction. The program sees a slow load and nothing else.

That last mechanism is the page fault, and it is worth being precise about what it is. It is not an error. It is a deliberately triggered exception used as a communication channel from hardware to the operating system, meaning "the program touched something you told me was not present, go do something about it." The same mechanism implements demand paging, copy-on-write, memory-mapped files, guard pages, and lazy allocation. One hardware trap, many software policies.

2.3 The unit has to be a block, and 4 KB is the compromise

Translation cannot be per byte. A table with one entry per byte of a 48-bit address space would have $2^{48}$ entries, which is more entries than there are bytes of memory in the machine, so the map would be larger than the thing it maps. Translation must work on blocks. The block is called a page, and its size is a design decision with sharp consequences in both directions.

Consider three candidate sizes for a process using 1 MB of memory on a 48-bit machine.

Page size	Pages to cover 1 MB	Waste on a 100-byte allocation	Entries needed to map the whole 48-bit space
64 bytes	16,384	up to 63 bytes	$2^{42}$ , about 4.4 trillion
4 KB	256	up to 4,095 bytes	$2^{36}$ , about 68.7 billion
1 MB	1	up to 1,048,475 bytes	$2^{28}$ , about 268 million

Small pages give a fine-grained map with little wasted memory per allocation, and an enormous number of entries to track. Large pages give a small map, and every allocation rounds up to a whole page so a program asking for 100 bytes consumes a megabyte. That rounding waste is internal fragmentation, meaning space wasted inside an allocated unit because the unit is bigger than what was asked for.

There is a third pressure that decides the matter, and it will not appear until Part 5. The hardware caches recent translations in a small fixed-size structure. With $N$ cached translations and page size $S$ , the amount of memory reachable without a new translation is $N \times S$ , called the TLB reach. Small pages make that number small, so more accesses miss the cache of translations. That pushes toward large pages just as hard as fragmentation pushes toward small ones.

4 KB won historically and stuck. It is $2^{12}$ , so the offset within a page is exactly 12 bits, which is a tidy number. It is small enough that internal fragmentation on typical allocations is tolerable and large enough that the table is not absurd. Apple silicon uses 16 KB pages on arm64, which is $2^{14}$ , and Part 6 will show that this choice is not cosmetic. It directly buys Apple a bigger L1 data cache than a 4 KB machine can build.

2.4 The address splits, and one half is left alone

Here is the structural fact that everything downstream depends on. If pages are $2^{12}$ bytes, then the low 12 bits of an address say where inside the page the byte is, and the remaining bits say which page it is. Translation changes which page. It does not touch where inside the page, because a page is moved as a unit and the internal layout is preserved.

Figure 2. Translation rewrites the page number and leaves the page offset alone, so forming a physical address is concatenation rather than arithmetic. The untouched offset is the fact Part 6 turns into a hard limit on L1 cache size.

Put a number on it. Virtual address 0x401A38 with 4 KB pages splits into VPN = 0x401 and offset = 0xA38. Check the arithmetic by hand. $0\text{x}401\text{A}38 = 4{,}201{,}016$ . Divide by 4096 and you get 1025 with remainder 2616. In hex that is VPN 0x401 and offset 0xA38, exactly the split the bit slicing gives. Suppose the map says virtual page 0x401 lives in physical frame 0x9C22. Then the physical address is 0x9C22A38, which is the frame number shifted up by 12 bits with the offset dropped in underneath. No addition, no arithmetic, just concatenation. That is why the split is at a power of two.

The offset is not translated. Hold onto that sentence. It looks like a triviality and it is the entire basis of Part 6, where it turns out to be the reason your laptop's L1 cache is the size it is.

03.Part 3, the page table

3.1 Price out the obvious design first

The obvious map is an array. One entry per virtual page, indexed by VPN. Look up VPN 0x401, get frame 0x9C22. Constant time, trivially simple. Price it.

A 48-bit address space with 4 KB pages has $2^{36}$ virtual pages. That is $68{,}719{,}476{,}736$ pages. Each entry must hold a frame number plus permission and status bits, and 8 bytes is the natural size on a 64-bit machine. So the table is

$2^{36} \times 8 = 2^{39} = 549{,}755{,}813{,}888 \text{ bytes} = 512\ \text{GiB}$

Five hundred and twelve gigabytes of table. Per process. The map is roughly sixty-four times larger than the entire DRAM of a well-equipped laptop, and you need a separate one for every process, so ten open applications want 5 TB of page table to describe a machine with 8 GB of memory.

Now look at how much of it is used. A modest program has maybe 1 MB resident, which is 256 pages. So 256 of the 68.7 billion entries are meaningful. The occupancy is

$\frac{256}{68{,}719{,}476{,}736} \approx 3.7 \times 10^{-9} \approx 0.0000004\ \text{percent}$

The table is not merely large, it is essentially empty. Ninety-nine point nine nine nine nine nine nine six percent of it is entries saying "nothing here." That observation is the whole solution. You do not need a data structure that stores 68.7 billion "nothing here" markers. You need one where "nothing here" is represented by the absence of storage.

3.2 A radix tree, and why the levels are 9 bits

Split the VPN into chunks and use each chunk to index a small table, where each table's entries point at the next table down. That is a radix tree, also called a multi-level page table.

Why is it small? Because a pointer in a table can be null. If a whole 512 GB region of the address space is unmapped, the one entry that would have pointed at that subtree is marked invalid and the entire subtree beneath it does not exist. Not zero-filled, not compressed. Absent. A region containing nothing costs one invalid entry.

Now derive the chunk size instead of accepting it. Two constraints pin it down.

First, the operating system allocates memory in pages, so a page table should itself be exactly one page. Anything smaller wastes the rest of the page, anything larger needs a contiguous multi-page allocation, which is exactly the thing that gets hard as the machine ages.

Second, each entry is 8 bytes. So a one-page table holds $4096 / 8 = 512$ entries, and $512 = 2^9$ , so indexing it takes exactly 9 bits.

The VPN is 36 bits. $36 / 9 = 4$ . So a 48-bit address space with 4 KB pages needs exactly four levels of nine bits each, and the split $9+9+9+9+12 = 48$ is forced by the page size and the entry size rather than chosen. Nothing is arbitrary here.

Figure 3. The four nine-bit index fields are not a convention but a consequence of insisting that each page table fit in one 4 KB page with eight-byte entries, which leaves 512 entries and therefore nine index bits per level.

Change the page size and the whole structure rederives itself. That is the best evidence the derivation is real.

Granule	Offset bits	Entries per table	Index bits per level	VPN bits	Levels	Top level width
4 KB	12	512	9	36	4	9 bits, 512 entries
16 KB	14	2048	11	34	4	1 bit, 2 entries
64 KB	16	8192	13	32	3	6 bits, 64 entries

Look at the 16 KB row. $34 = 11 + 11 + 11 + 1$ , so the top level table of a 16 KB granule holds exactly two valid entries and wastes the rest of its page. That looks like a flaw and is a real, specified part of the AArch64 architecture. It is what falls out of insisting the tables be page-sized. The 64 KB row is tidier, $32 = 6 + 13 + 13$ , and it drops a level entirely, which shortens the walk. These are not trivia. They are the reason a designer picks a granule.

3.3 Walk one address by hand

Take virtual address 0x0000_0000_0040_1A38, a plausible code address in a Linux or Darwin binary. Slice it.

Value in decimal is $4{,}201{,}016$ . Now extract each field.

Field	Bits	Computation	Value
L0 index	[47:39]	$4{,}201{,}016 \gg 39 = 0$	0
L1 index	[38:30]	$4{,}201{,}016 \gg 30 = 0$ , since $2^{30} = 1{,}073{,}741{,}824$ is larger	0
L2 index	[29:21]	$4{,}201{,}016 \gg 21 = 2$ , since $2 \times 2{,}097{,}152 = 4{,}194{,}304 \le 4{,}201{,}016$	2
L3 index	[20:12]	$4{,}201{,}016 \gg 12 = 1025$ , and $1025 \bmod 512 = 1$	1
offset	[11:0]	$4{,}201{,}016 - 1025 \times 4096 = 2616 =$ 0xA38	0xA38

Now the walk. The hardware starts from a register holding the physical address of the root table, called TTBR0_EL1 on AArch64 for user addresses and TTBR1_EL1 for kernel addresses, or CR3 on x86-64. That register is part of the process context and is reloaded on every context switch, which is exactly how the map becomes per-process.

Figure 4. Servicing one load on a four-level page table costs five memory accesses, four of which are pure overhead the program never asked for and cannot see.

Five memory accesses to service one load. Four of them are pure overhead the program never asked for and cannot see.

Do a second address so the tree shape becomes visible. Take 0x0000_7FFF_FFFF_D678, a plausible stack address near the top of the user half of the space. Write it in binary as 48 bits.

Plain Text

  0x7FFFFFFFD678 =
  0111 1111 1111 1111 1111 1111 1111 1111 1101 0110 0111 1000

  regroup as 9 / 9 / 9 / 9 / 12:

  011111111 | 111111111 | 111111111 | 111111101 | 011001111000
    255    |    511    |    511    |    509    |    0x678
```text
So L0 index 255, L1 index 511, L2 index 511, L3 index 509, offset 0x678. Completely different high indices from the code address, which is the point.

### 3.4 Draw the tree and count what actually exists

Now put both addresses in the same picture, along with the whole rest of the address space that is unmapped.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig05.svg" alt="Two live addresses at opposite ends of the space need only seven tables, because every unmapped region costs one invalid entry rather than storage proportional to the addresses it covers." caption="Two live addresses at opposite ends of the space need only seven tables, because every unmapped region costs one invalid entry rather than storage proportional to the addresses it covers." id="fig:07-Virtual-Memory-and-Memory-Ordering-5" />

Count the cost. Seven tables at 4 KB each is **28 KB**. Against the flat design's 512 GiB, the ratio is

$$\frac{549{,}755{,}813{,}888}{28{,}672} \approx 19{,}174{,}400$$

Nineteen million times smaller, for the same mapping. And the saving is not a clever encoding trick. It is that a null pointer is 8 bytes regardless of how much address space hangs below it. The L0 entry at index 1 is invalid, and by being invalid it accounts for all 512 GiB of virtual addresses from 0x0000_0080_0000_0000 upward, at a cost of one entry.

Say the tradeoff cleanly. **The flat table pays for every address that could exist. The tree pays only for the addresses that do exist, and pays for that with extra levels of pointer chasing on every lookup.** Space against time, resolved in favor of space by a factor of nineteen million, and then the time cost is clawed back by Part 5.

### 3.5 What is in an entry, and where isolation is actually enforced

An entry is not just a frame number. It carries the permission and status bits, and those bits are where memory protection physically happens.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig06.svg" alt="A page descriptor carries far more than a frame number, and the permission, attribute and status bits packed around it are where memory protection is actually enforced, as a byproduct of a lookup the machine was doing anyway." caption="A page descriptor carries far more than a frame number, and the permission, attribute and status bits packed around it are where memory protection is actually enforced, as a byproduct of a lookup the machine was doing anyway." id="fig:07-Virtual-Memory-and-Memory-Ordering-6" />

Three things are worth pulling out. The **AP** and **XN** bits mean that a write to a read-only page or a fetch from a data page faults during translation, before the access reaches the cache. Protection is not a separate check bolted on afterward, it is a byproduct of a lookup the machine was doing anyway, which is why it costs nothing. The **AF** and dirty tracking give the operating system the information it needs to pick eviction victims without instrumenting the program. And the **Idx** field means cacheability is a per-page property, which is how a device register mapped into a process's address space is marked non-cacheable while ordinary heap is not.

### 3.6 The cost, and why it is not as bad as it looks

Four extra accesses per load sounds fatal. Price the worst case honestly, then fix it twice.

Worst case, every one of the four table reads misses all the way to DRAM at roughly 80 ns each. That is 320 ns before the real access even begins, which at 3 GHz is about 960 cycles. If every load cost that, a machine would run about a hundred times slower than one without translation, and virtual memory would never have been adopted.

It does not, for two reasons that both matter.

**The tables are ordinary memory, so they are cacheable.** The L0, L1, and L2 tables of a running process are touched by essentially every translation, so they sit permanently in L2 and often in L1. A walk that hits in L2 costs perhaps four times fifteen cycles, so around 60 cycles rather than 960.

**The walker caches partial results.** A **page walk cache**, also called a translation cache, stores the intermediate pointers keyed by the upper index bits. Two addresses in the same 2 MB region share their L0, L1, and L2 entries and differ only at L3, so once the first one has walked, the second only needs the final access. Work an example. A loop striding through 1 MB of data touches 256 different 4 KB pages. All 256 sit inside one 2 MB region, so all 256 share the same L0, L1, and L2 path. The first translation costs four accesses, the other 255 cost one each. Average walk cost is $(4 + 255 \times 1) / 256 = 1.01$ accesses, not four.

Both fixes are the same idea applied twice, which is caching what you just computed because you will probably need it again. Part 5 applies it a third time and much harder.

---

## Part 4, huge pages

### 4.1 Stop the walk early and see what happens

Look again at the four-level split. At each level, an entry either points at the next table down or, if the architecture allows it at that level, directly at a large physical block. The second kind is a **block descriptor**, and using one is what a huge page is.

Derive the sizes rather than memorizing them. If the walk stops at L2, then the L3 index has not been used, so bits [20:12] are no longer selecting a table entry. Those nine bits plus the twelve offset bits, twenty-one bits in total, all pass through untranslated as an offset into one big block.

$$2^{21} = 2{,}097{,}152\ \text{bytes} = 2\ \text{MB}$$

Stop one level earlier, at L1, and bits [29:12] pass through, which is thirty bits.

$$2^{30} = 1{,}073{,}741{,}824\ \text{bytes} = 1\ \text{GB}$$

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig07.svg" alt="A huge page is nothing more than a walk that stops early. Each level skipped hands its nine index bits back to the offset, which is why the block sizes are 2 MB and 1 GB rather than numbers anyone had to memorize." caption="A huge page is nothing more than a walk that stops early. Each level skipped hands its nine index bits back to the offset, which is why the block sizes are 2 MB and 1 GB rather than numbers anyone had to memorize." id="fig:07-Virtual-Memory-and-Memory-Ordering-7" />

And the derivation travels. With a 16 KB granule, each level consumes 11 bits, so stopping one level early gives $2^{11+14} = 2^{25} = 32$ MB. That is exactly the block size AArch64 specifies for the 16 KB granule, and it is not a number anyone had to look up.

### 4.2 What it buys, counted

Two distinct wins, and they are worth separating.

**The walk is shorter.** Three accesses instead of four, or two instead of four for a 1 GB page. A twenty-five to fifty percent cut in the miss cost, which is real but modest.

**TLB reach explodes.** This is the big one. A typical L1 data TLB holds around 64 entries.

| Page size | L1 DTLB reach with 64 entries | L2 TLB reach with 2048 entries |
|---|---|---|
| 4 KB | 256 KB | 8 MB |
| 16 KB | 1 MB | 32 MB |
| 2 MB | 128 MB | 4 GB |
| 1 GB | 64 GB | 2 TB |

Now make that concrete. A database walking a 40 GB in-memory index with 4 KB pages has an 8 MB reach in its L2 TLB, so it misses the TLB on the overwhelming majority of accesses and each miss costs a walk. Move that index to 1 GB pages and 40 entries cover the whole thing, so it essentially never misses again. This is not a few percent. It is the difference between a workload being translation-bound and translation being invisible.

### 4.3 What it costs, and each cost is real

**Internal fragmentation, at 512 times the scale.** A process that allocates 40 KB and gets a 2 MB page wastes 2,008 KB, or ninety-eight percent of the allocation. Do that for a hundred small allocations and you have burned 200 MB to store 4 MB.

**Physical contiguity, which gets harder over time.** A 2 MB page requires 2 MB of physically contiguous, 2 MB-aligned DRAM. A freshly booted machine has plenty. A machine that has been up for a week has its free memory scattered in 4 KB fragments, so the allocator must either compact memory, which is expensive and stalls things, or fail to grant the huge page. This is why huge pages are so often a configuration nightmare in practice and why transparent huge page support has to include a background defragmenter.

**Permissions get coarse.** The permission bits live in the descriptor, so one 2 MB block has one set of permissions. If 4 KB inside it needs to become read-only, the operating system has to **split** the block, allocating a real L3 table and 512 individual entries, then invalidate the old translation everywhere. Any mechanism that changes protections at fine grain, and copy-on-write is the obvious one, fights huge pages directly.

**Copy-on-write becomes expensive.** Fork a process, and the first write to a shared 4 KB page copies 4 KB. The first write to a shared 2 MB page copies 2 MB, which is 512 times the work and 512 times the latency spike, for a program that touched one byte.

**The TLB itself gets harder to build.** Here is the microarchitecture consequence, and it is the one an RTL interviewer cares about. A set-associative TLB indexes with some bits of the VPN. But which bits are the VPN depends on the page size, and the hardware does not know the page size until after it has found the entry. That is circular. There are three ways out, and every one costs something. Make the structure fully associative so there is no index, which caps its size at a few dozen entries. Build **separate arrays** per page size and look them all up in parallel, which multiplies area and power. Or **splinter** large pages into multiple small-page entries on fill, which throws away most of the reach benefit. Real cores do a mixture, typically a small fully associative L1 TLB that holds any size and a large set-associative L2 TLB with separate ways or separate arrays for the common sizes.

---

## Part 5, the TLB

### 5.1 The idea, and the arithmetic that justifies it

A page table walk is expensive and programs translate the same handful of pages over and over. A loop that walks a 4 KB array touches one page a thousand times. So cache the translations.

The **translation lookaside buffer**, or TLB, is a small hardware cache holding recent virtual-page-to-physical-frame mappings along with their permission bits. Hit and translation is a single cycle. Miss and you pay the walk.

Work the average cost, because the shape of the curve is the point. Let $h$ be the hit rate and let a miss cost 60 cycles, using the L2-resident walk figure from 3.6.

$$\text{average translation cost} = h \times 1 + (1-h) \times 60$$

| Hit rate | Average cost in cycles | Comment |
|---|---|---|
| 99.9 % | $0.999 + 0.06 = 1.06$ | translation is essentially free |
| 99 % | $0.99 + 0.60 = 1.59$ | still fine |
| 97 % | $0.97 + 1.80 = 2.77$ | starting to hurt |
| 95 % | $0.95 + 3.00 = 3.95$ | translation now costs more than the L1 access |
| 90 % | $0.90 + 6.00 = 6.90$ | translation dominates the memory pipeline |

Notice the asymmetry. Going from 99.9 to 99 percent costs half a cycle. Going from 99 to 90 percent costs five and a half. Because the miss penalty is large, the useful operating region is a narrow band right up against 100 percent, and this is why real TLB hit rates are quoted above 99 percent rather than above 90. A structure that is "usually right" is not good enough. It has to be almost always right.

### 5.2 A TLB is a CAM, and that is why it is tiny

An ordinary cache is indexed. You take some address bits, use them to select a set, and compare tags only within that set. A small fully associative TLB cannot do that, because with only 48 entries there is no sensible index and any VPN may live in any entry. So the lookup question becomes "does **any** entry hold this VPN," and answering it requires comparing against every entry simultaneously.

A structure that does that is a **content-addressable memory**, a CAM, covered in [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams). You present data and it tells you where, if anywhere, that data lives.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig08.svg" alt="A fully associative TLB gives every entry its own full-width comparator and drives every match line on every lookup, which is why area and power grow linearly with entry count and why an L1 TLB stops at a few dozen entries." caption="A fully associative TLB gives every entry its own full-width comparator and drives every match line on every lookup, which is why area and power grow linearly with entry count and why an L1 TLB stops at a few dozen entries." id="fig:07-Virtual-Memory-and-Memory-Ordering-8" />

Every entry carries its own comparator, so area and switching power grow **linearly with entry count** with a large constant, since each comparator is 36 bits wide. Worse, the match lines are a wide wired-OR structure that must precharge and evaluate within one cycle, and that structure gets slower as it gets taller. A CAM is one of the most power-hungry structures per bit in a processor.

That is the whole explanation for a fact that otherwise looks arbitrary. **L1 TLBs are small, typically 32 to 64 entries, because a fully associative CAM that size is at the edge of what fits in a single cycle at a gigahertz-class frequency.** It is not that designers do not want a bigger one. It is that the structure does not scale.

### 5.3 The hierarchy, for the same reason caches have one

The fix is the fix used everywhere in this business. If one structure cannot be both fast and large, build two.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig09.svg" alt="Translation uses the same escape a cache hierarchy uses. One structure cannot be both fast and large, so a tiny fully associative L1 sits in front of a set-associative L2, a page walk cache, and finally the hardware walker." caption="Translation uses the same escape a cache hierarchy uses. One structure cannot be both fast and large, so a tiny fully associative L1 sits in front of a set-associative L2, a page walk cache, and finally the hardware walker." id="fig:07-Virtual-Memory-and-Memory-Ordering-9" />

Three design choices in that picture are worth being able to defend.

**Separate instruction and data TLBs at L1.** The front end fetches from one place and the load-store unit accesses another, and both need a translation every cycle. One shared structure would need two ports, and a two-ported CAM is close to twice the area and power of a single-ported one. Splitting is cheaper and matches the access patterns, since instruction addresses are sequential and data addresses are not.

**Replicating the DTLB per load port.** A core with three load pipes needs three translations per cycle. Rather than build a three-ported CAM, build three copies of a small CAM and keep them identical. Area triples, but three single-ported CAMs are cheaper and faster than one three-ported one. This is the same reasoning that produces replicated register file read ports in [Execution Units](/learn/hardware-interview-prep/execution-units).

**Set-associative L2.** At 1024 entries a fully associative structure is impossible, so the L2 TLB indexes on VPN bits and compares a few ways. It costs a few cycles, which is fine, because it is only consulted on an L1 TLB miss and by construction that is rare.

### 5.4 Who does the walk, hardware or software

On a TLB miss something must consult the page table. There are two architectural answers and the choice is visible in the ISA.

| | Hardware walker | Software-managed TLB |
|---|---|---|
| Used by | x86-64, AArch64, most modern | MIPS, SPARC v9, Alpha, historically |
| Mechanism | a state machine in the MMU issues loads to the page table | a TLB miss raises an exception, an OS handler runs |
| Page table format | fixed by the architecture, hardware knows it | free, the OS may use any structure it likes |
| Cost of a miss | tens of cycles, and it can overlap with other work | a trap, so a pipeline flush plus the handler, 100+ cycles minimum |
| Speculation | the walker can be started speculatively on a predicted address | you cannot speculatively take an exception |
| Effect on the core | invisible, the load simply takes longer | the entire pipeline is drained and refilled |

The decisive argument is the last two rows. In an out-of-order core, a hardware walk is just another set of memory accesses that the machine issues and waits for, and the rest of the window keeps executing around it. A software walk is an **exception**, which by definition squashes everything younger and restarts the front end. That is 15 to 20 cycles of pure pipeline refill before the handler's first instruction retires, and the handler itself pollutes the instruction cache and the branch predictor. On a machine that misses the TLB even a small fraction of the time, this is not survivable. Software-managed TLBs were a reasonable trade when pipelines were five stages deep and a trap cost almost nothing. They stopped being reasonable when pipelines got long.

Hardware walkers also permit a trick that software cannot. Because the walker is a state machine and not an instruction stream, several walks can be in flight at once. A core with multiple **table walk state machines** can service two or three concurrent TLB misses in parallel, so a burst of misses costs one walk latency rather than three.

### 5.5 ASIDs, and the flush they prevent

Translations are per-process. Process A's virtual page 0x401 and process B's virtual page 0x401 map to different frames. So when the operating system switches from A to B, every TLB entry becomes wrong.

The naive fix is to flush the entire TLB on every context switch. Price that. Suppose the incoming process has a working set of 200 pages. After the flush, its first touch of each of those pages misses the TLB. If a walk costs 30 cycles with page walk caches helping, the refill cost is

$$200 \times 30 = 6{,}000\ \text{cycles} \approx 2\ \mu\text{s at 3 GHz}$$

Two microseconds of pure overhead per switch, and it is worse than that number suggests because those 6,000 cycles are spread across the first few thousand instructions of the new process, exactly the window where the branch predictor and caches are also cold. On an interactive workload with thousands of switches per second per core, and on any system doing frequent system calls that switch address spaces, the cost is real and it grows every time TLBs get bigger.

The fix is to make entries from different processes coexist by tagging each one with an identifier for the address space it belongs to. On AArch64 that tag is the **ASID**, address space identifier. On x86-64 it is the **PCID**, process context identifier.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig10.svg" alt="Adding an address space identifier to the tag turns a context switch from a full TLB flush into a change of register value, because another process's entries simply stop matching instead of having to be thrown away." caption="Adding an address space identifier to the tag turns a context switch from a full TLB flush into a change of register value, because another process's entries simply stop matching instead of having to be thrown away." id="fig:07-Virtual-Memory-and-Memory-Ordering-10" />

Now a switch from A to B writes B's ASID into the ASID register and changes TTBR0. Nothing is flushed. A's entries are still present, they simply stop matching, and if the scheduler returns to A shortly afterward, they start matching again and A resumes with a warm TLB. That last property is the one that matters most on a machine that ping-pongs between two threads.

Two details are worth volunteering unprompted, because they show you have thought past the headline.

**The global bit.** Kernel pages are mapped identically in every process, so tagging them with an ASID would waste an entry per process per kernel page. The `nG` bit in the descriptor, seen in 3.5, marks an entry as **global**, meaning it matches regardless of the current ASID. So kernel translations survive every context switch, which is why a system call is much cheaper than a process switch.

**ASIDs run out.** The field is 8 or 16 bits on AArch64, selected by a control register bit, so there are 256 or 65,536 of them. A long-running system creates more processes than that, so the operating system must recycle identifiers, and recycling one means flushing every TLB entry carrying it. The mechanism does not eliminate flushes, it makes them rare instead of universal.

### 5.6 TLB shootdown, and why hardware refuses to help

Four cores are running four threads of the same process. All four have executed code that touched page P, so all four TLBs hold a translation for it. Now the thread on core 0 calls `munmap` on P, or the operating system decides to swap P out, or a copy-on-write fault changes which frame P points to.

Core 0 edits the page table entry in DRAM and invalidates its own TLB entry. Cores 1, 2, and 3 still hold the old translation. They will happily keep reading and writing the old physical frame, which the operating system is about to hand to a different process. That is a correctness catastrophe, and it is silent.

Here is the question that gets asked, and it is a good one. **Caches are kept coherent by hardware. Why not TLBs?**

The answer has four parts and the last one is the RTL answer.

**A TLB entry is not a copy of a memory location.** The coherence protocol in [Cache Coherence Protocols](/learn/hardware-interview-prep/cache-coherence-protocols) works because a cache line is a verbatim copy of a block of DRAM, identified by its physical address, so a write to that address can be matched against every copy. A TLB entry is a **derived value**. It is manufactured from up to four separate page table entries at four different physical addresses, then transformed, with permission bits folded in and possibly a contiguous hint applied. There is no single address you can snoop on that identifies it.

**The granularity is wrong in both directions.** One TLB entry depends on four PTEs, so any of four writes should invalidate it. And one PTE at an upper level is a dependency of thousands of TLB entries, so one write should invalidate thousands. A protocol built around one-line-one-copy does not express either relationship.

**The traffic model is wrong.** Coherence is worth its cost because data sharing is frequent and fine-grained. Page table modification is rare, happening at `mmap`, `munmap`, fault, and swap, which is thousands of times per second rather than billions. Building a hardware protocol for an event that rare is poor value.

**The port cost lands in the worst possible place.** To snoop a TLB you must add a second lookup port to a fully associative CAM that is already on the critical path of every single memory access in the machine. Section 5.2 explained why that CAM is barely fast enough with one port. Doubling its ports to service an event that happens a few thousand times a second, at the cost of frequency on every load, is a trade no designer would take.

So it is left to software. The sequence is called a **TLB shootdown**.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig11.svg" alt="A shootdown is a software protocol, not a hardware one. The initiating core interrupts every other core, waits for all of them to acknowledge, and only then may the physical frame be reused, so the cost grows with core count." caption="A shootdown is a software protocol, not a hardware one. The initiating core interrupts every other core, waits for all of them to acknowledge, and only then may the physical frame be reused, so the cost grows with core count." id="fig:07-Virtual-Memory-and-Memory-Ordering-11" />

The cost is brutal and it scales badly. Each remote core takes an interrupt, which flushes its pipeline and destroys its own progress, and core 0 blocks until the slowest of them replies. Public measurements put a broadcast shootdown in the range of several microseconds on a many-core system, and because the initiator waits for **all** acknowledgements, the cost grows with core count. It is a well-known scalability wall for workloads that remap memory frequently, and it is why high-performance allocators go to some length to avoid unmapping.

AArch64 offers a genuine middle ground worth naming. The `TLBI` instruction family broadcasts an invalidation to all cores in the **inner shareable domain** in hardware, so software does not need to send interrupts at all. `TLBI VAE1IS, x0` invalidates one virtual address across the domain. This does not make TLBs coherent, because software still has to decide when to issue it, but it removes the interrupt storm and the software acknowledgement protocol. The required follow-up is a `DSB`, which is where Part 8 reconnects, because the initiating core must wait for the broadcast to complete before it may safely reuse the frame, and `DSB` is the instruction that means "wait for completion."

---

## Part 6, where translation sits relative to the cache

### 6.1 What a cache lookup needs, restated precisely

Recall from [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching) how a set-associative cache decomposes an address. Take a 32 KB cache, 8-way set-associative, with 64-byte lines.

Number of sets is $32768 / (8 \times 64) = 64$. So indexing takes $\log_2 64 = 6$ bits, and selecting a byte inside a 64-byte line takes $\log_2 64 = 6$ bits. Everything above those twelve bits is the tag.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig12.svg" alt="A cache lookup needs the index first to select a set and the tag second to compare against what came out, and that gap in timing is the opportunity every virtually indexed design exploits." caption="A cache lookup needs the index first to select a set and the tag second to compare against what came out, and that gap in timing is the opportunity every virtually indexed design exploits." id="fig:07-Virtual-Memory-and-Memory-Ordering-12" />

A lookup needs the index **first**, to select a set and start reading the tag and data arrays, and needs the tag **second**, to compare against what came out. Those two needs happen at different times, and that timing gap is the entire opportunity.

The design question is which address, virtual or physical, supplies each of them. Two independent binary choices, four combinations, three of which are used.

### 6.2 PIPT, correct and serialized

**Physically indexed, physically tagged.** Translate first, then use the physical address for everything.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig13.svg" alt="A physically indexed cache is correct with no complications at all, and pays for it by putting the whole TLB latency in series ahead of the array access that every dependent instruction is waiting on." caption="A physically indexed cache is correct with no complications at all, and pays for it by putting the whole TLB latency in series ahead of the array access that every dependent instruction is waiting on." id="fig:07-Virtual-Memory-and-Memory-Ordering-13" />

Correct with no complications of any kind. Two virtual addresses that map to the same physical page produce the same physical address, so they land in the same set and hit the same line, automatically. Coherence snoops arrive carrying physical addresses and can index the cache directly. Nothing has to be flushed on a context switch.

The cost is that the TLB latency is **added** to the cache latency. For an L2 cache that is irrelevant, since a couple of extra cycles on a twelve-cycle access is noise, and every L2 and beyond is PIPT for exactly this reason. For an L1 that must return data in three or four cycles, adding one or two is a large fraction and it lands on the load-to-use latency that every dependent instruction waits for.

### 6.3 VIVT, fast and quietly wrong

**Virtually indexed, virtually tagged.** Skip translation entirely on a hit. Index and compare with virtual bits, and only translate when you miss.

Fastest possible. The TLB is completely off the critical path. And it breaks in two distinct ways.

**Synonyms, also called aliases.** Two different virtual addresses map to the same physical page. This is not exotic, it is how shared libraries work, how `fork` works before the first write, how two processes share a memory-mapped file, and how a process that maps the same file twice behaves.

Make it concrete with a cache big enough for the bug to bite. Take a 16 KB direct-mapped VIVT cache with 64-byte lines. Sets $= 16384 / 64 = 256$, so the index is 8 bits sitting at [13:6], and the block offset is 6 bits at [5:0]. Note that the index reaches up to **bit 13**, which is above the 12-bit page offset, so two of the index bits come from the virtual page number.

Now have two processes share one physical page. Process A maps physical frame 0x40 at virtual 0x1000, process B maps the same frame at virtual 0x2000. Both are pointing at the same physical bytes.

| | Virtual address | bits [13:6] | Set |
|---|---|---|---|
| Process A | 0x1000 | $(0\text{x}1000 \gg 6)\ \&\ 0\text{xFF} = 0\text{x}40$ | **64** |
| Process B | 0x2000 | $(0\text{x}2000 \gg 6)\ \&\ 0\text{xFF} = 0\text{x}80$ | **128** |

Two different sets, for one physical line. The cache now holds two independent copies of the same physical bytes and does not know they are related. Process A stores a new value into set 64. Process B loads from set 128 and gets the stale one. Nothing detects it, because coherence operates **between** caches and both copies live inside the same cache, so no invalidation is ever generated.

State the general rule that the example illustrates. **If any index bit comes from the translated part of the address, two virtual addresses mapping to the same physical line can land in different sets, and the cache holds two copies of one line.** Everything in 6.4 is a direct consequence of forbidding exactly that.

**Homonyms.** The same virtual address in two processes means two different physical addresses. So a virtual tag match after a context switch is a false hit. The fixes are to flush the whole cache on every context switch, which is far worse than flushing a TLB because L1 caches are much larger, or to tag every cache line with an ASID, which makes the tags wider and reintroduces the ASID recycling problem into a much bigger structure.

VIVT survives in a few places, notably some small instruction caches and some GPU designs, where the sharing patterns are controlled. It is not used for a general-purpose L1 data cache.

### 6.4 VIPT, and derive the constraint rather than quoting it

**Virtually indexed, physically tagged.** Use virtual bits for the index, so the SRAM read starts immediately, and use the physical address for the tag, so aliasing cannot cause a false hit. Run the TLB **in parallel** with the array read.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig14.svg" alt="Indexing with virtual bits lets the array read start at the same instant as the translation, so the cost is the larger of the two rather than their sum. Paying for that overlap is what forces the constraint derived in this section." caption="Indexing with virtual bits lets the array read start at the same instant as the translation, so the cost is the larger of the two rather than their sum. Paying for that overlap is what forces the constraint derived in this section." id="fig:07-Virtual-Memory-and-Memory-Ordering-14" />

For this to work, the index must be available **before** translation finishes. The index comes out of the virtual address. But translation changes the upper bits of the address. So the index is only trustworthy if it uses **no bits that translation can change**, which means every index bit must come from the page offset.

Now do the algebra with symbols, then check it with numbers.

Let the page size be $2^p$ bytes, so the page offset is $p$ bits, occupying bit positions $[p-1:0]$. Let the cache have line size $2^b$ bytes and $2^s$ sets, with associativity $A$. The block offset occupies bits $[b-1:0]$ and the index occupies bits $[s+b-1:b]$. The highest index bit is therefore bit $s+b-1$, and the requirement is that it lies inside the page offset.

$$s + b - 1 \le p - 1 \quad \Longrightarrow \quad s + b \le p$$

The cache size is the number of sets times the associativity times the line size.

$$\text{size} = 2^s \times A \times 2^b = A \times 2^{s+b} \le A \times 2^p$$

$$\boxed{\ \text{cache size} \le \text{page size} \times \text{associativity}\ }$$

Derived in four lines from one physical fact, which is that the offset is not translated. That fact was stated back in 2.4 and flagged as load-bearing.

Check it against the running example. 32 KB, 8-way, 64-byte lines, 4 KB pages. Sets $= 32768/(8 \times 64) = 64$, so $s = 6$. Line is 64 bytes, so $b = 6$. Then $s + b = 12$ and $p = 12$. Equality. It **exactly** fits, with not one bit to spare. And the bound says size $\le 4096 \times 8 = 32768$ bytes, which is exactly 32 KB. The design sits precisely on the constraint, which is not a coincidence, it is designers taking every byte the rule allows.

Now break it deliberately. Keep 32 KB and 64-byte lines but make it 4-way. Sets $= 32768/(4 \times 64) = 128$, so $s = 7$ and $s + b = 13 > 12$.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig15.svg" alt="Going four-way at 32 KB pushes the index up to seven bits, and the seventh one is bit 12, which translation is free to change. That single bit is the whole failure, because two aliases of one physical line then land in different sets." caption="Going four-way at 32 KB pushes the index up to seven bits, and the seventh one is bit 12, which translation is free to change. That single bit is the whole failure, because two aliases of one physical line then land in different sets." id="fig:07-Virtual-Memory-and-Memory-Ordering-15" />

That is the aliasing of 6.3 walking straight back in through the index. The failure is concrete. Virtual 0x1000 and virtual 0x2000 both mapping to physical frame 0x40000. Bit 12 is 0 for 0x1000 and 1 for 0x2000, so they land in set 0 and set 64 respectively. A store through 0x1000 dirties the copy in set 0. A load through 0x2000 reads the clean stale copy in set 64. No hardware anywhere notices.

Tabulate the design space, since this is what an interviewer is actually probing.

| Size | Ways | Line | Sets | $s$ | $s+b$ | 4 KB page ($p=12$) | 16 KB page ($p=14$) |
|---|---|---|---|---|---|---|---|
| 32 KB | 4 | 64 B | 128 | 7 | 13 | **fails by 1 bit** | fine |
| 32 KB | 8 | 64 B | 64 | 6 | 12 | exactly fits | fine |
| 48 KB | 12 | 64 B | 64 | 6 | 12 | exactly fits | fine |
| 64 KB | 8 | 64 B | 128 | 7 | 13 | **fails by 1 bit** | fine |
| 64 KB | 16 | 64 B | 64 | 6 | 12 | exactly fits | fine |
| 128 KB | 8 | 64 B | 256 | 8 | 14 | **fails by 2 bits** | exactly fits |
| 192 KB | 12 | 64 B | 256 | 8 | 14 | fails by 2 bits | exactly fits |

Read that 48 KB row. Twelve-way associativity is a strange number, and it exists for exactly this reason. Intel's L1 data cache moved from 32 KB 8-way to 48 KB 12-way starting with Sunny Cove, and the only way to grow past 32 KB while keeping 4 KB pages and VIPT is to grow the associativity in lockstep. Associativity, not size, is the free variable.

Now say the consequence out loud, because it is the point of the whole part.

**This equation is why L1 caches are small and highly associative, and it is why they have barely grown in twenty years.** Everything else in a processor got bigger. Reorder buffers went from 40 entries to 600. Last-level caches went from 512 KB to tens of megabytes. The L1 data cache went from 32 KB to 48 KB. It is not because designers do not want more. It is because on a machine with 4 KB pages, growing the L1 requires growing associativity in proportion, and associativity costs a comparator and a way-select mux per way on the load-to-use critical path. Sixteen-way is already painful. Thirty-two-way is not buildable at speed.

And then look at the 128 KB row under the 16 KB page column. **Apple silicon uses 16 KB pages**, which raises the ceiling from $4096 \times A$ to $16384 \times A$, a factor of four. With 8-way associativity that permits a 128 KB L1 data cache, and public microarchitectural analyses of the M1's Firestorm core report a 128 KB L1D. The numbers line up exactly. The page size choice is not an operating system detail, it is a microarchitecture decision that bought Apple four times the L1 capacity at the same associativity, and therefore at the same load-to-use latency. If there is one Apple-specific fact in this entire note worth having ready, this is it.

The remaining escape hatch is a software one. **Page coloring** has the operating system deliberately assign physical frames so that the bits above the page offset that the cache uses as index bits are the same in the virtual and physical addresses. That restores correctness for a cache that violates the constraint, at the cost of constraining the physical allocator, and it is fragile because a single misallocation reintroduces the bug. Some systems have done it. Most designers prefer to obey the equation.

### 6.5 One more interaction, snooping into a virtually indexed cache

Coherence snoops carry **physical** addresses, because that is the only namespace all the caches agree on. A snoop arriving at a VIPT L1 must find the line. If the constraint of 6.4 holds, the index bits are inside the page offset and are therefore identical in the virtual and physical addresses, so the snoop can index the L1 directly using physical bits and everything works. If the constraint is violated, the snoop does not know which set to look in and must probe every set that could hold the line, which for a one-bit violation is two sets, for a two-bit violation four sets. That is extra snoop bandwidth on a structure that is already contended by the core's own accesses.

This is a second, independent reason to obey the constraint, and mentioning it unprompted signals that you have thought about the cache as a system rather than as a lookup table. The usual real-world mitigation is a **snoop filter** or an inclusive L2 with a duplicate copy of the L1 tags, so most snoops never reach the L1 at all.

---

## Part 7, the second topic, what a multiprocessor promises

### 7.1 Coherence and consistency are different questions

Everything from here on has nothing to do with page tables. Start by drawing the boundary against the neighbouring topic.

**Coherence**, the subject of [Cache Coherence Protocols](/learn/hardware-interview-prep/cache-coherence-protocols), is about **one address**. It guarantees that all cores agree on the sequence of values a single memory location takes, and that a write eventually becomes visible everywhere. Coherence is what stops core 1 from reading a stale value of `x` forever after core 0 wrote it.

**Consistency** is about **the relationship between accesses to different addresses**. It answers questions of the form "core 0 wrote `x` and then wrote `y`, can core 1 see the new `y` and the old `x`?" Coherence has nothing to say about that, because `x` and `y` are different locations and coherence reasons about each one independently.

A machine can be perfectly coherent and still allow behaviour that looks impossible. That is the next section, and it is the single most valuable thing in this note to be able to explain from a blank whiteboard.

### 7.2 The litmus test, and why the intuitive answer is wrong

Two cores. Two shared variables, `x` and `y`, both initially zero. Two registers per core.

```text
  Core 0:                        Core 1:
    STR  #1, [x]                   STR  #1, [y]
    LDR  r1, [y]                   LDR  r2, [x]
```text
Ask the question. **Can both `r1` and `r2` end up holding 0?**

Reason about it the way everyone reasons about it the first time. One of the two stores must physically happen before the other, since they happen at some real instant. Say core 0's store to `x` goes first. Then when core 1 later loads `x`, it must see 1, so `r2` is 1 and the answer is no. Symmetrically if core 1's store went first, `r1` is 1. Either way at least one of them sees a 1. There are only two cases and both give the same conclusion.

**That reasoning is wrong, and both loads returning 0 is a routine observation on real hardware.** Not a rare race, not a hardware bug, just what the machine does. Sit with that for a moment, because the argument above feels airtight and the flaw in it is not in the logic. It is in the premise, specifically in the phrase "the store happens." A store is not a single event. It is a sequence, and the instant a core executes the store instruction is not the instant the value becomes visible to other cores.

The reason is the **store buffer**.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig16.svg" alt="Each core sees its own store the instant it enters the store buffer and every other core sees it only when the buffer drains, which is the whole reason both loads in the litmus test can return zero on a perfectly coherent machine." caption="Each core sees its own store the instant it enters the store buffer and every other core sees it only when the buffer drains, which is the whole reason both loads in the litmus test can return zero on a perfectly coherent machine." id="fig:07-Virtual-Memory-and-Memory-Ordering-16" />

Trace it step by step.

| Step | Core 0 | Core 1 | Core 0 buffer | Core 1 buffer | Coherent x | Coherent y |
|---|---|---|---|---|---|---|
| 0 | | | empty | empty | 0 | 0 |
| 1 | `STR #1,[x]` completes into the buffer | | holds x=1 | empty | 0 | 0 |
| 2 | | `STR #1,[y]` completes into the buffer | holds x=1 | holds y=1 | 0 | 0 |
| 3 | `LDR r1,[y]` searches its own buffer, finds no `y` | | holds x=1 | holds y=1 | 0 | 0 |
| 4 | reads coherent `y`, gets **0**, `r1 = 0` | | holds x=1 | holds y=1 | 0 | 0 |
| 5 | | `LDR r2,[x]` searches its own buffer, finds no `x` | holds x=1 | holds y=1 | 0 | 0 |
| 6 | | reads coherent `x`, gets **0**, `r2 = 0` | holds x=1 | holds y=1 | 0 | 0 |
| 7 | buffer drains | | empty | holds y=1 | **1** | 0 |
| 8 | | buffer drains | empty | empty | 1 | **1** |

Both loads returned 0. Every step is individually reasonable, the memory system was coherent throughout, and there was never a moment when two cores disagreed about the value of a single location. The counterintuitive result came entirely from each core's store becoming visible to itself immediately and to the other core later.

Say the general fact plainly. **The order in which a core issues memory operations is not the order in which other cores observe them, and no amount of coherence changes that.** A memory consistency model is precisely a specification of how far apart those two orders are allowed to get.

### 7.3 The store buffer is not gratuitous

Before treating store buffering as a nuisance to be eliminated, understand why it exists, because that framing decides everything downstream.

A store must eventually write a cache line. If that line is not in this core's cache in a writable state, the core must first request **exclusive ownership** through the coherence protocol, which means finding the current owner, invalidating other copies, and receiving the data. That is a round trip across the fabric, and it costs anywhere from 30 cycles for a line in a neighbouring core's L1 within the same cluster to 200 cycles or more for a line held by a different cluster.

Without a store buffer, the core stalls for that entire time on every store that misses. Stores are roughly ten percent of dynamic instructions on typical code. If two percent of them miss and each miss costs 120 cycles, the added cost per instruction is

$$0.10 \times 0.02 \times 120 = 0.24\ \text{cycles per instruction}$$

On a core targeting a CPI near 0.25, that is a doubling. And the calculation understates it badly, because the stall is not just the store waiting, it is the entire in-order retirement stream behind it stopping.

With a store buffer, the store retires architecturally as soon as it is known to be non-faulting, the value goes into the buffer, the core moves on, and the ownership request proceeds in the background. The stall vanishes. This is one of the highest-value optimizations in a core, which is why every model except pure sequential consistency permits it.

### 7.4 Sequential consistency, and exactly what it forbids

**Sequential consistency**, defined by Leslie Lamport in 1979, is the strictest useful model. Two requirements.

The result of any execution must be the same as if all the operations of all cores were executed in **some single total order**. And within that total order, each core's own operations must appear in the order its program specifies.

Apply it to the litmus test. Enumerate every interleaving of the four operations that preserves each core's program order. There are six such interleavings, and in every single one of them at least one load comes after the other core's store, so at least one load reads 1. The outcome `r1 = r2 = 0` corresponds to no total order at all, so sequential consistency forbids it.

What does it cost to actually guarantee this? Not one thing but three, and they compound.

**No store buffering visible to loads.** A load may not read past a pending store to a different address, so the store buffer cannot be bypassed and the store must be globally visible before the load issues. That reinstates the stall of 7.3 in full.

**No load-load reordering.** Two independent loads must become visible in program order. In an out-of-order core, loads are issued as soon as their addresses are ready, which is routinely out of order, so a strict implementation would have to issue them in order, which serializes the entire memory pipeline and destroys memory-level parallelism.

**No store-store reordering.** Stores must drain from the buffer strictly in order, so one store missing to a far cluster blocks every younger store behind it, even stores to lines the core already owns.

There is a well-known escape, and it is worth naming because it shows the cost is not fundamental, only large. **Speculative sequential consistency**, pioneered in the MIPS R10000 and used by some later designs, lets loads execute out of order speculatively, but keeps each completed-but-not-retired load in a queue and watches the coherence traffic. If a snoop invalidates a line that a speculatively completed load read, the machine squashes that load and everything younger and replays. The result is sequentially consistent behaviour with out-of-order performance, at the cost of a snoop-triggered comparison against every entry in the load queue, which is another wide CAM in the load-store unit, plus a replay mechanism, plus the performance loss whenever the speculation fails. That machinery is exactly what a weak model lets you not build.

### 7.5 Total store order, what x86 relaxes and what it does not

**TSO** is x86-64's model, and it relaxes exactly one thing.

A **store followed by a load to a different address** may be reordered, meaning the load may become visible before the store does. That is precisely the store buffer of 7.2, and the litmus test outcome `r1 = r2 = 0` **is permitted** under TSO.

Everything else is preserved. Store-to-store order is preserved, so the store buffer drains in FIFO order. Load-to-load order is preserved. Load-to-store order is preserved. And a core always sees its own stores, since the load searches the store buffer first, which is **store forwarding** and is required by every model because otherwise single-threaded code would break.

TSO also guarantees something subtler called **multi-copy atomicity**. When a store becomes visible, it becomes visible to all other cores at once, so two observers can never disagree about the order of two stores made by two different cores. The test for this is called **IRIW**, independent reads of independent writes.

```text
  Core 0:  STR #1,[x]
  Core 1:  STR #1,[y]
  Core 2:  LDR r1,[x]   ; sees 1
            LDR r2,[y]   ; sees 0     -> core 2 thinks x was written first
  Core 3:  LDR r3,[y]   ; sees 1
            LDR r4,[x]   ; sees 0     -> core 3 thinks y was written first
```text
Under TSO this outcome is forbidden. The two stores enter a single global order and every core sees that same order. A machine that permitted it would be one where "which store happened first" has no answer, which is genuinely hard to program against.

TSO is a deliberate design point. It relaxes the one thing that buys almost all the performance, which is store buffering, and keeps everything else, which is what makes an enormous body of x86 software correct without explicit fences.

### 7.6 Weak ordering, what ARM relaxes and what it keeps

**AArch64** relaxes all four orderings between accesses to different addresses. Store then load, store then store, load then load, load then store, all four may be observed out of program order. The programmer inserts explicit barriers where order matters.

But "weak" is not "anything goes," and knowing what it still guarantees is what separates a real answer from a memorized one. Four things survive.

**Same-address ordering.** Two accesses to the same location by one core are never reordered relative to each other in a way that violates coherence. If you store 1 to `x` and then load `x`, you get 1.

**Address dependencies are respected.** If a load's address is computed from the result of a previous load, the two loads are ordered. This is why the read-copy-update pattern of loading a pointer and then dereferencing it is safe on ARM without a barrier. It is worth knowing that this was **not** true on the DEC Alpha, which permitted a dependent load to be satisfied before the load that produced its address, because of a value-predicting cache design. That single decision made Alpha notorious and is why the Linux kernel carried an explicit `read_barrier_depends` primitive for decades.

**Data and control dependencies to stores are respected.** A store cannot become visible before a load whose value determines whether the store happens.

**Other-multi-copy atomicity.** As specified today, AArch64 forbids the IRIW outcome above. Two stores by two different cores are seen in a consistent order by all other cores. ARM's architecture was revised to guarantee this, and it matters because it makes reasoning tractable.

### 7.7 The comparison, in one table

| Reordering, different addresses | SC | TSO (x86-64) | AArch64 | RISC-V RVWMO |
|---|---|---|---|---|
| store then later load | forbidden | **allowed** | **allowed** | **allowed** |
| store then later store | forbidden | forbidden | **allowed** | **allowed** |
| load then later load | forbidden | forbidden | **allowed** | **allowed** |
| load then later store | forbidden | forbidden | **allowed** | **allowed** |
| load forwards from own pending store | n/a | allowed | allowed | allowed |
| two accesses to the **same** address | forbidden | forbidden | forbidden | forbidden |
| load reordered ahead of the load producing its address | forbidden | forbidden | forbidden | forbidden |
| IRIW, observers disagree on store order | forbidden | forbidden | forbidden | forbidden |
| programmer must insert fences for lock-free code | no | rarely | **routinely** | routinely |

Read the last row alongside the rest. The columns move from left to right by moving work from hardware to software, one row at a time.

### 7.8 Why a weak model is a genuine hardware advantage

This is the part to be able to argue rather than assert, because Apple builds weakly ordered cores and will expect you to know what that buys.

**What you do not have to build.** A TSO core must preserve load-load order as observed from outside. In an out-of-order core, loads execute whenever their addresses are ready, which is out of order, so the core must be able to detect after the fact that its speculative ordering was observable and undo it. The mechanism is the one described in 7.4. Every completed load stays in the load queue until retirement, every incoming coherence invalidation is compared against every entry in that queue, and a match squashes the load and everything younger. Concretely that is a snoop port into a 100-plus entry CAM in the load-store unit, running at core frequency, plus the replay path, plus the recovery logic. On a weakly ordered machine most of that is unnecessary for accesses to different addresses.

**What you get in the store path.** A TSO store buffer must drain in order, so one store missing to a distant cluster blocks every younger store behind it, including stores to lines already owned. A weakly ordered store buffer may retire them in any order, so a miss costs only itself.

**What you get in the load path.** Loads may issue and complete freely, and there is no global ordering point that all stores must funnel through. The absence of a serialization point is worth more as core count rises, because a serialization point is exactly the thing that does not scale.

**What it pushes onto software.** All of it. Every lock, every lock-free queue, every publish-then-flag pattern needs explicit barriers or acquire-release accesses, and the compiler and language memory model have to get it right on the programmer's behalf. The failure mode is nasty, because code that is missing a barrier runs correctly on x86 for years, since TSO happened to provide the ordering for free, and then fails intermittently on ARM. That is not a hypothetical, it is a well-documented category of porting bug.

The honest counterpoint is one Apple themselves supplied. **Apple silicon includes a per-thread toggle that makes the core behave as TSO**, used by Rosetta 2 so translated x86 binaries get the ordering they were written against without inserting a barrier at every store. That fact is publicly documented and it is a superb thing to have ready, because it demonstrates two things at once. It shows the ordering behaviour is a microarchitectural knob rather than a physical law, and it shows that Apple decided the performance cost of TSO was worth paying for one specific compatibility case and not worth paying in general. That is exactly the kind of engineering judgment an interviewer is looking for.

---

## Part 8, barriers and atomics

### 8.1 The three AArch64 barriers, and what each is for

A **barrier**, also called a fence, is an instruction that constrains reordering across the point where it sits. AArch64 has three and they do genuinely different things.

| | `DMB` | `DSB` | `ISB` |
|---|---|---|---|
| Name | data memory barrier | data synchronization barrier | instruction synchronization barrier |
| Orders data accesses | yes, before vs after | yes, before vs after | no |
| Waits for prior accesses to **complete** | no, it only orders them | **yes** | no |
| Waits for cache and TLB maintenance to finish | no | **yes** | no |
| Affects instruction fetch | no | no | **yes**, flushes the pipeline |
| Typical use | ordinary lock-free code, publish-then-flag | after `TLBI`, after cache maintenance, before DMA hands off a buffer | after changing a system register, after writing code you are about to execute |

The distinction between `DMB` and `DSB` is the one that gets missed. `DMB` says "accesses after me may not be observed before accesses before me," which is a statement about **order**. It does not say the earlier accesses have finished. `DSB` says "do not execute anything at all until every earlier access and every earlier maintenance operation has actually completed," which is a statement about **completion**. That is why 5.6 needed a `DSB` after `TLBI`. Ordering the invalidation is not enough. You must know it has landed in every remote TLB before you reuse the frame.

`ISB` is about a completely different pipeline. Modern cores fetch and decode hundreds of instructions ahead. If you write a system register that changes how instructions behave, or if you write instructions into memory and then jump to them, the already-fetched instructions are stale. `ISB` discards them and refetches. It says nothing about data ordering at all.

`DMB` and `DSB` take qualifiers that narrow what they order, and using the narrowest correct one is real design and real performance work.

| Qualifier | Meaning |
|---|---|
| `SY` | full system, every observer, both loads and stores. The sledgehammer. |
| `ISH` | inner shareable domain only, which is normally all the CPU cores. The common one for multithreaded software. |
| `OSH` | outer shareable, which extends to other coherent agents such as a GPU or an accelerator. |
| `NSH` | non-shareable, this core only. |
| `LD` suffix | order only prior **loads** against later accesses. |
| `ST` suffix | order only prior **stores** against later stores. |

So `DMB ISHLD` orders prior loads against later loads and stores, within the CPU coherence domain, and nothing else. It is dramatically cheaper than `DMB SY` and is correct for the acquire side of a lock.

### 8.2 What a barrier actually costs, and why

A barrier is not an instruction that takes N cycles. It is an instruction that **stops things from proceeding** until a condition holds, so its cost is entirely determined by machine state at the moment it executes.

Walk the mechanism. When a `DMB ISH` reaches the load-store unit, later memory operations are prevented from becoming globally observable until the earlier ones have. In most implementations that means later memory operations are blocked from issuing, which means the load-store queues stop draining, which means the reorder buffer stops retiring, which means it fills, which means rename stalls, which means the front end stalls. A barrier in a wide out-of-order core does not stall one instruction, it back-pressures the entire machine.

Now the cost depends on what was pending.

| Machine state when the barrier executes | Rough cost |
|---|---|
| store buffer empty, no outstanding loads | a handful of cycles, essentially the issue bubble |
| store buffer holds a few stores whose lines are already owned in L1 | tens of cycles to push them out |
| store buffer holds one store whose line must be fetched exclusive from another core in the same cluster | 40 to 80 cycles, dominated by the coherence round trip |
| store buffer holds a store whose line lives in another cluster or in DRAM | 150 to 400+ cycles |
| `DSB` following a broadcast `TLBI` | hundreds to thousands, since every remote TLB must acknowledge |

Work one case. Suppose the store buffer holds six entries, four of which hit in L1 and two of which miss and need exclusive ownership from a remote cluster at 150 cycles each. If the core has enough miss handling registers to have both ownership requests outstanding simultaneously, the drain takes about 150 cycles, since they overlap. If it does not, or if TSO-style in-order drain forces them to serialize, it takes 300. A barrier that costs 150 cycles on a core executing 6 instructions per cycle has thrown away roughly 900 instruction slots.

Two design consequences follow, and both are real microarchitecture work rather than trivia.

**Barriers should order, not drain, wherever the architecture permits.** A naive implementation waits for the store buffer to empty. A better one only enforces that later accesses are not **observed** before earlier ones, which can sometimes be achieved by tagging entries and enforcing an ordering constraint on their release, rather than by stopping the machine until the buffer is empty. That is harder to get right and worth a great deal.

**Use the narrowest barrier.** `DMB ISHLD` on the acquire side does not need to wait for the store buffer at all, since it only orders prior loads. Implementing the qualifier distinctions properly rather than mapping everything to a full system barrier is a meaningful performance difference on real lock-heavy code.

### 8.3 Acquire and release, a one-way wall

The best way to make barriers cheap is to not use them. AArch64 attaches ordering to individual accesses through `LDAR`, load-acquire, and `STLR`, store-release. These are **one-way** barriers, and the picture explains the whole idea.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig17.svg" alt="A full barrier blocks motion in both directions, while load-acquire and store-release each block one direction only. A lock needs exactly one direction at each end, so paying for the other is pure waste." caption="A full barrier blocks motion in both directions, while load-acquire and store-release each block one direction only. A lock needs exactly one direction at each end, so paying for the other is pure waste." id="fig:07-Virtual-Memory-and-Memory-Ordering-17" />

Now see why that is exactly what a lock needs. Acquiring a lock is a load, and the critical section that follows must not be hoisted above it, so a one-way wall that blocks upward motion is precisely correct. Releasing a lock is a store, and the critical section that precedes it must not sink below it, so the mirror-image wall is precisely correct. Neither case needs the other direction, and paying for the other direction is pure waste.

The hardware saving is concrete. A `DMB SY` before and after a critical section forces two full drains. A `LDAR`/`STLR` pair attaches the constraint to two specific accesses, so the machine only has to track ordering relative to those, and the rest of the load-store queues keep flowing. This is one of the clearest examples in the ISA of a construct designed with the microarchitecture in mind, and it is a good thing to be able to explain.

### 8.4 Atomics, the exclusive monitor, and why the loop can fail

Consider the simplest shared-memory operation there is, incrementing a counter. In three steps it is load, add one, store. On two cores running it simultaneously, both can load 5, both add one, both store 6, and one increment vanishes. The three steps must be **atomic**, meaning no other core may observe or modify the location partway through.

The RISC answer, used by ARM, PowerPC, RISC-V, and MIPS, is a pair of instructions rather than a single fused one. On AArch64 they are `LDXR`, load exclusive, and `STXR`, store exclusive.

`LDXR` loads a value and sets a hardware flag called the **exclusive monitor**, recording that this core is watching that address. `STXR` stores a value **only if** the monitor is still set, and returns a status of 0 for success or 1 for failure. If anything happened to the address in between, the monitor is cleared and the store fails without writing anything, so software retries.

```text
  retry:
    LDXR   w0, [x1]          ; load, arm the monitor on the address in x1
    ADD    w0, w0, #1        ; modify in a register, no memory involved
    STXR   w2, w0, [x1]      ; try to store.  w2 = 0 success, 1 failure
    CBNZ   w2, retry         ; if it failed, go around again
```text
Trace two threads racing.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig18.svg" alt="The losing store-exclusive writes nothing and reports failure, because the coherence invalidation that carried the winner's write also cleared the loser's monitor. Detection rides for free on traffic the protocol was going to generate anyway." caption="The losing store-exclusive writes nothing and reports failure, because the coherence invalidation that carried the winner's write also cleared the loser's monitor. Detection rides for free on traffic the protocol was going to generate anyway." id="fig:07-Virtual-Memory-and-Memory-Ordering-18" />

No increment is lost. The failure is detected and retried, and the detection rides for free on the coherence invalidation that was going to happen anyway. That is elegant, and the elegance is why this design is so widespread.

Four practical facts about the monitor are worth having ready, because they are what the follow-up questions are about.

**There are two monitors, local and global.** The local monitor lives in the core and tracks the core's own reservation. The global monitor lives out in the memory system and handles addresses that are non-cacheable or shared with agents that are not coherence participants. In ordinary cacheable memory the coherence protocol does the work and the local monitor is what matters.

**The granularity is a whole reservation granule, typically a cache line.** The monitor does not track a 4-byte word, it tracks the line. So two threads doing atomic updates to two **different** variables that happen to share one 64-byte line will clear each other's monitors constantly. Both spin, both fail, forward progress is terrible. That is false sharing in its most vicious form, and the fix is padding shared counters to a cache line each.

**The loop can fail forever, so the architecture constrains it.** If arbitrary code sits between `LDXR` and `STXR`, an interrupt or a cache eviction can clear the monitor every time and the loop never terminates. The architecture places restrictions on what may appear between the pair, and implementations include forward-progress mechanisms so that a thread that has failed repeatedly gets to win. Knowing that the loop is not guaranteed to terminate in general, and that both the architecture and the implementation work to make it terminate in practice, is a good answer.

**Contention scales badly.** With $N$ threads hammering one counter, the line ping-pongs between caches, and each round trip is 100-plus cycles. The successful thread invalidates the other $N-1$ reservations, so on average a lot of work is thrown away. Throughput does not merely fail to scale, it can go **down** as threads are added.

### 8.5 LSE atomics, and why moving the operation is better than moving the data

ARMv8.1 added the **Large System Extensions**, a set of single-instruction atomic read-modify-write operations including `LDADD` for atomic add, `SWP` for atomic exchange, and `CAS` for compare and swap. They replace the `LDXR`/`STXR` loop with one instruction, which removes the retry loop and its failure modes.

The deeper win is not the instruction count. It is **where the operation executes**. A far-atomic can be sent to the point of coherence, typically the shared cache, and performed there, so the cache line never has to travel to the requesting core at all.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig19.svg" alt="An exclusive pair drags the contended line back and forth between cores and throws most attempts away, while a far atomic sends the operation to the line instead, so the shared cache serializes the requests and nothing bounces." caption="An exclusive pair drags the contended line back and forth between cores and throws most attempts away, while a far atomic sends the operation to the line instead, so the shared cache serializes the requests and nothing bounces." id="fig:07-Virtual-Memory-and-Memory-Ordering-19" />

The difference in behaviour under contention is dramatic. Bouncing a line among $N$ cores costs a round trip per attempt plus wasted attempts, and the wasted fraction grows with $N$. Serializing at the shared cache costs one round trip per operation regardless of $N$, and nothing is wasted. A contended counter goes from a structure that gets worse as you add cores to one that saturates at the shared cache's throughput.

This is a genuinely good thing to be able to explain, because it is a clean instance of a principle that shows up everywhere in this business. **When an operation on data is small and the data is large or contended, move the operation to the data rather than the data to the operation.** The same reasoning motivates compute-near-memory, in-cache operations, and DMA descriptors.

---

## Part 9, multiprocessor organization and multithreading

### 9.1 Clusters, shared caches, and shareability domains

Consistency questions only exist because there is more than one core, so the organization matters.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig20.svg" alt="The shareability qualifiers on a barrier name boxes in this picture rather than abstract scopes, so choosing ISH over SY is a statement about which caches and cores must agree before the barrier is satisfied." caption="The shareability qualifiers on a barrier name boxes in this picture rather than abstract scopes, so choosing ISH over SY is a statement about which caches and cores must agree before the barrier is satisfied." id="fig:07-Virtual-Memory-and-Memory-Ordering-20" />

Three observations connect this picture back to earlier parts. The **shareability domains** in the barrier qualifiers of 8.1 are literally this diagram, which is why choosing `ISH` over `SY` is not a guess, it is a statement about which boxes must agree. The **coherence round trip cost** in 8.2 depends on whether the line is in a sibling core's L1 within the cluster, in the cluster L2, in the other cluster, or in the SLC, which is a spread of roughly an order of magnitude. And the **TLB shootdown** of 5.6 has to reach every core in the inner shareable domain, so its cost grows with the width of this diagram.

Apple's public design splits performance cores and efficiency cores into separate clusters with separate shared L2 caches, which matters here for a reason beyond scheduling. Two threads that communicate frequently are much cheaper to run in the same cluster, because their shared lines stay in the cluster L2 rather than crossing to the SLC. Cluster topology is a memory latency question as much as a power question, and it ties into [DVFS Droop and Thermal](/learn/hardware-interview-prep/dvfs-droop-and-thermal) because the two clusters run at different voltages and frequencies.

### 9.2 Three ways to run more than one thread on a core

A wide superscalar core has issue slots it cannot fill. Two kinds of waste.

**Horizontal waste** is issue slots left empty in a cycle where the core did issue something, because one thread simply did not have four ready independent instructions available.

**Vertical waste** is entire cycles where nothing issues at all, because the thread is stalled on a cache miss or a mispredict recovery.

Multithreading attacks the waste with another thread's work. Three styles, and the difference between them is exactly which kind of waste they can fill.

<Figure src="/figures/hardware-interview-prep/iv-07-Virtual-Memory-and-Memory-Ordering-fig21.svg" alt="Only SMT puts two threads in the same issue cycle, which is why it is the only style that can fill the empty slots left beside an instruction that did issue rather than only the cycles where nothing issued at all." caption="Only SMT puts two threads in the same issue cycle, which is why it is the only style that can fill the empty slots left beside an instruction that did issue rather than only the cycles where nothing issued at all." id="fig:07-Virtual-Memory-and-Memory-Ordering-21" />

| Style | Switch trigger | Fills vertical waste | Fills horizontal waste | Main cost |
|---|---|---|---|---|
| coarse-grained | a long stall, tens of cycles | only long stalls, and only after a switch penalty | no | needs a pipeline drain and refill on switch, so short stalls are not worth switching for |
| fine-grained, also called barrel | every cycle, round-robin | yes, all of it | no | single-thread latency is terrible, since one thread gets at most one cycle in $N$ |
| SMT | never, threads issue in the **same** cycle | yes | **yes** | every shared structure needs thread tags, arbitration, and fairness logic |

The key line in that table is that only SMT fills horizontal waste, and it does so because it is the only one where two threads occupy the same issue cycle. Coarse and fine-grained multithreading still issue from one thread per cycle, so a thread with only two ready instructions still wastes two slots.

### 9.3 What SMT costs in RTL

This is the part that matters for a design role, because SMT is not a scheduling feature, it is a change to nearly every structure in the core.

| Structure | SMT treatment | Why |
|---|---|---|
| architectural registers, PC, PSTATE, exception state | **replicated** | each thread has its own architectural state by definition |
| rename map table | **replicated** | the architectural-to-physical mapping is per-thread |
| physical register file | shared | dynamic sharing is the entire point, but it must be sized for two threads or each gets half a core's worth |
| reorder buffer | partitioned, statically or dynamically | one thread must not be able to fill it and deadlock the other |
| issue queue | shared with per-thread caps | without a cap, a thread stalled on a long-latency miss fills the queue with unready instructions and starves the other |
| store buffer and load queue | partitioned | entries must be attributable to a thread for ordering and for flush on a per-thread pipeline squash |
| L1 caches, TLBs | shared, entries tagged by thread | tagging avoids flushing on every thread interleave, at the cost of wider tags |
| branch predictor | shared, sometimes tagged | a major source of destructive interference, since two threads' histories pollute each other |

Three problems recur in every SMT design. **Fairness**, since a thread taking a long miss can occupy shared resources it cannot use, which is why per-thread occupancy caps exist. **Partitioning policy**, since a static split wastes half the structure when only one thread is running, and a dynamic split needs logic to enforce minimums and prevent deadlock. And **verification cost**, since every structure now has a thread dimension and every flush, every exception, and every replay must be per-thread rather than global, which multiplies the state space the verification plan in [Verification Methodology](/learn/hardware-interview-prep/verification-methodology) has to cover.

There is also a security dimension. Threads sharing a core share caches, TLBs, branch predictors, and execution port occupancy, and a shared resource whose occupancy one thread can measure is a channel the other thread can be observed through. This is a well-documented class of problem across the industry, and the general defence, which is to not share microarchitectural state between mutually distrusting threads, is in direct tension with what SMT is for.

### 9.4 Why Apple does not use SMT, and why that is defensible

Apple's CPU cores do not implement SMT. That is publicly known and it is a legitimate interview topic, so have a real argument rather than an opinion.

**SMT's value is proportional to the holes it fills, and a very wide core with good speculation has fewer holes than it looks.** SMT pays off when one thread cannot keep the issue width busy. But the things that leave holes are long stalls and dependency chains, and a core with a very large reorder buffer, an aggressive prefetcher, and an excellent branch predictor already finds independent work far ahead in its own instruction stream. Every one of those structures is an alternative way of spending area to fill the same holes, and unlike SMT they improve **single-thread** performance rather than throughput.

**SMT costs single-thread performance in two ways.** Shared structures must be sized for the multi-thread case or each thread gets less than a full core, and the tagging, arbitration, and fairness logic sits in the middle of frequency-critical structures like the issue queue and the load queue. Even a core running one thread pays that timing cost. If your product's defining characteristic is single-thread responsiveness, and Apple's is, that is the wrong trade.

**Given area, more cores may beat more threads.** SMT typically adds a few percent of core area for maybe twenty to thirty percent throughput on threaded workloads. Spending the same area on additional efficiency cores, which are much smaller than a performance core, can buy more throughput per watt. Apple's heterogeneous design is the alternative answer to the same problem SMT solves, and it answers it with real cores that have their own full resources rather than half-shares of somebody else's.

**Predictability and security.** No SMT means no cross-thread interference in shared microarchitectural structures, so performance is more repeatable and one large class of side channels does not exist.

Be honest about the counterargument, because pretending SMT is bad is a worse answer than explaining the trade. SMT is very good value on **throughput-oriented server workloads** with many independent threads and poor per-thread instruction-level parallelism, which is why it persists in x86 server parts. Apple's products are not that workload. The right framing is not "SMT is bad," it is "SMT optimizes throughput per unit area on workloads with abundant thread parallelism and poor per-thread parallelism, and Apple's products are dominated by latency-sensitive workloads where the same area is better spent on a wider window and more real cores." That sentence is a defensible engineering position rather than brand loyalty.

---

## Part 11, check yourself

Answer out loud, in full sentences, as if an interviewer asked. If you cannot, reread the section named.

1. Name the two independent problems this note covers and give one sentence each on why they have nothing to do with each other. Where in a real core do they physically meet? (1.1)
2. Give a concrete failure for each of isolation, relocation, and over-commitment on a machine without translation. (2.1)
3. Compute the size of a flat page table for a 48-bit space with 4 KB pages and 8-byte entries, compute how many entries a 1 MB process actually uses, then count how many tables the radix tree needs for the same process. (3.1, 3.4)
4. Why is each level of an AArch64 4 KB-granule page table exactly 9 bits? Derive it, redo the derivation for a 16 KB granule, then walk virtual address 0x401A38 and count the memory accesses. (3.2, 3.3)
5. Derive the 2 MB and 1 GB huge page sizes from the level structure rather than quoting them. Then give three distinct costs of using them. (4.1, 4.3)
6. Why is a TLB hit rate of 95 percent bad when a 95 percent cache hit rate would be acceptable? Work the average cost, then say why an L1 TLB is fully associative and why that caps it at a few dozen entries. (5.1, 5.2)
7. What do ASIDs prevent, what does the global bit add on top of them, and why do ASIDs not eliminate flushes entirely? (5.5)
8. Name the three multithreading styles, say which kind of issue-slot waste each one can and cannot fill, and give the defensible argument for why Apple does not use SMT. (9.2, 9.4)
9. An interviewer asks why hardware keeps caches coherent but not TLBs. Give four reasons, and make the last one the RTL reason about ports. (5.6)
10. Derive the VIPT constraint from the fact that the page offset is not translated. Show what specifically breaks in a 32 KB 4-way cache with 4 KB pages, naming the bit, then say why Apple's 16 KB pages let it build a larger L1 at the same associativity and latency. (6.4)
11. Draw the two-core litmus test, state the intuitive answer, say why it is wrong, and trace the store buffer step by step to produce both loads returning 0. (7.2)
12. State exactly what TSO relaxes and exactly what it preserves. Then state what AArch64 additionally relaxes and what it still guarantees. (7.5, 7.6)
13. What hardware does a weakly ordered machine avoid building that a TSO machine must build? Be specific about the structure. (7.8)
14. Distinguish `DMB`, `DSB`, and `ISB`, and say why a `TLBI` needs a `DSB` rather than a `DMB`. Then say what a barrier costs in cycles and why "it depends" is the correct start of that answer. (8.1, 8.2, 5.6)
15. Explain the exclusive monitor with a two-thread trace where one `STXR` fails, explain why two unrelated counters in one cache line livelock each other, then say why an LSE far-atomic is better under contention. (8.4, 8.5)

---

## Part 12, related notes

- [Cache Coherence Protocols](/learn/hardware-interview-prep/cache-coherence-protocols) for coherence, which Part 7 spends its first section carefully distinguishing from consistency, and for the invalidation traffic that clears the exclusive monitor in 8.4
- [Load Store and Memory Ordering](/learn/hardware-interview-prep/load-store-and-memory-ordering) for where the ordering rules of Parts 7 and 8 are actually enforced in RTL, meaning the load queue, the store buffer, and the replay machinery
- [Cache Organization and Prefetching](/learn/hardware-interview-prep/cache-organization-and-prefetching) for index, tag, set, and way, which Part 6 assumes, and for the cache whose maximum size the VIPT constraint dictates
- [Arbiters FIFOs and CAMs](/learn/hardware-interview-prep/arbiters-fifos-and-cams) for the content-addressable memory that a fully associative TLB is built from, and for why its cost scales the way 5.2 describes
- [Out of Order Execution](/learn/hardware-interview-prep/out-of-order-execution) for the reorder buffer and issue queue that a barrier back-pressures and that SMT has to partition
- [SRAM Arrays and ECC](/learn/hardware-interview-prep/sram-arrays-and-ecc) for the arrays the TLB and the tag and data stores are built from
- [SoC Integration and Interfaces](/learn/hardware-interview-prep/soc-integration-and-interfaces) for shareability domains at fabric scale and for IOMMU translation on DMA-capable agents
- [Verification Methodology](/learn/hardware-interview-prep/verification-methodology) for why memory ordering is a formal-methods problem rather than a directed-simulation problem
- [Virtual Memory](/learn/computer-architecture/virtual-memory) for the vault's treatment of paging, faults, and the operating system side
- [TLBs and Address Translation](/learn/computer-architecture/tlbs) for the vault's deeper treatment of the walk, ASIDs, and shootdown
- [Anatomy of an Instruction Set](/learn/computer-architecture/anatomy-isa) for consistency models from the ISA architect's point of view
- [Load-Store Queue Design](/learn/computer-architecture/load-store-queue) for the vault's treatment of the queues that implement ordering
- [Simultaneous Multithreading (SMT)](/learn/computer-architecture/smt) for the vault's full treatment of SMT

Book mode