Multi-Level Cache Hierarchies, MESI Protocol & Two-Level Paging TLB Architecture

In modern computing, the raw arithmetic capabilities of execution cores vastly outstrip the speed of physical memory. A contemporary processor can execute multiple instructions per nanosecond, yet reading a single data value from off-chip dynamic RAM (DRAM) requires 60 to 100 nanoseconds—stalling the CPU for hundreds of clock cycles. This fundamental performance divergence, known as the Memory Wall, is mitigated by a multi-tiered hierarchy of high-speed SRAM caches, hardware cache coherence protocols, and virtual memory translation units. Mastering cache indexing geometry, MESI snooping dynamics, multi-level paging structures, and Translation Lookaside Buffers (TLBs) is fundamental to designing high-performance software and scalable systems.

1. The Memory Latency Wall & Locality Principles#

Over four decades of semiconductor development, microprocessor compute throughput advanced at approximately 50% per year, while DRAM memory latency improved at an annual rate of only ~7%. This divergence created a catastrophic memory access penalty: without caching, an execution core would spend over 95% of its execution cycles idling, waiting for memory data words to arrive across physical circuit board traces.

+----------------------------------------------------------------------------------------------------+
|                                    THE MEMORY HIERARCHY PYRAMID                                    |
+----------------------------------------------------------------------------------------------------+
  Level            Typical Size     Latency (Cycles)   Latency (Time)   Technology
  --------------------------------------------------------------------------------------------------
  Registers        1 - 2 KB         1 cycle            ~0.25 - 0.3 ns   Multi-ported Flip-Flops
  L1 Cache (I/D)   32 - 64 KB       4 - 5 cycles       ~1.0 ns          Static RAM (SRAM, Private)
  L2 Cache         512 - 2048 KB    12 - 14 cycles     ~3.5 ns          Static RAM (SRAM, Private)
  L3 Cache (LLC)   16 - 96 MB       40 - 60 cycles     ~12 - 20 ns      Static RAM (SRAM, Shared)
  Main Memory      16 - 128 GB      200 - 300 cycles   ~60 - 90 ns      Dynamic RAM (DRAM DDR5)
  NVMe / SSD       1 - 4 TB         10,000+ cycles     ~10 - 50 us      NAND Flash Memory
+----------------------------------------------------------------------------------------------------+

Physical Implementation: SRAM vs. DRAM#

The memory hierarchy trades off access latency against physical silicon area and manufacturing cost:

• Static RAM (SRAM): Used for L1, L2, and L3 caches. Each SRAM cell consists of 6 transistors (6T) arranged as two cross-coupled inverters with two access transistors. SRAM holds its state stably as long as power is maintained, requiring zero refresh cycles. Access times are extremely fast (< 1 ns), but each cell requires substantial silicon area, limiting on-chip capacity.
• Dynamic RAM (DRAM): Used for main system memory. Each DRAM cell consists of only 1 transistor and 1 capacitor (1T1C). This enables immense storage density at low cost. However, the tiny electrical charge in the capacitor leaks away within milliseconds, requiring periodic electrical refresh cycles. Accessing DRAM involves charging sense amplifiers, row activation (RAS), column selection (CAS), and precharging, resulting in high latency (~60-90 ns).

The Principles of Locality#

Caches bridge the latency gap by exploiting the non-random nature of software execution, governed by two empirical locality principles:

1. Temporal Locality: If a memory location is accessed once, it is highly likely to be accessed again in the near future. Examples include loop iteration counter variables, hot function call stacks, and accumulator variables. Caches retain recently accessed blocks in high-speed SRAM.
2. Spatial Locality: If a memory location is accessed, memory locations with physically adjacent addresses are highly likely to be accessed soon. Examples include sequential execution of instruction streams, sequential iterations over contiguous array buffers, and traversal of consecutive struct fields. Caches exploit spatial locality by transferring data not as single bytes, but as fixed-size multi-byte blocks called cache lines (typically 64 bytes).

Average Memory Access Time (AMAT)#

The performance of a memory hierarchy is quantified by Average Memory Access Time:

AMAT = Hit_Time + Miss_Rate · Miss_Penalty.

In a modern 3-level cache hierarchy:

• L1 Hit Time = H1, L1 Miss Rate = M1 (local miss rate)
• L2 Hit Time = H2, L2 Miss Rate = M2 (local miss rate)
• L3 Hit Time = H3, L3 Miss Rate = M3 (local miss rate)
• Main Memory Latency = Memory_Latency.

The recursive AMAT equation is:

AMAT = H1 + M1 · [ H2 + M2 · [ H3 + M3 · Memory_Latency ] ].

Notice the compounding sensitivity: because Memory_Latency is massive (~250 cycles), even a tiny increase in the miss rate of the Last-Level Cache (L3) dramatically inflates overall AMAT, degrading instructions-per-cycle (IPC) throughput.

2. Cache Addressing Geometry, Associativity & Replacement Policies#

To locate data rapidly, hardware partitions a physical memory address into three distinct bitfields: Tag, Set Index, and Byte Offset.

Physical Memory Address (m bits):
+------------------------------------------+-----------------------+---------------------+
|             Tag Bits (t bits)            |   Set Index (s bits)  | Byte Offset (b bits)|
+------------------------------------------+-----------------------+---------------------+

Address Bitfield Decomposition#

Let:

• m = Total number of physical address bits (e.g., 32 bits or 64 bits).
• C = Total cache data capacity in bytes.
• B = Cache line block size in bytes (standard B = 64 bytes).
• N = Degree of associativity (number of lines/ways per set).

1. Byte Offset (b bits):

Selects the exact byte within a B-byte cache line:

b = log2(B).

For a standard 64-byte line: b = log2(64) = 6 bits.

1. Number of Cache Sets (S):

S = Total_Lines / N = (C / B) / N = C / (N · B).

1. Set Index (s bits):

Selects which specific set holds the candidate cache line:

s = log2(S) = log2( C / (N · B) ).

1. Tag (t bits):

Uniquely identifies the memory block among all blocks that map to that specific set:

t = m - s - b.

Cache Placement Strategies#

Microarchitectures balance hardware complexity and hit latency across three placement strategies:

+----------------------------------------------------------------------------------------------------+
|                                    CACHE ASSOCIATIVITY SPECTRUM                                    |
+----------------------------------------------------------------------------------------------------+
  Direct-Mapped (1-Way):        N-Way Set-Associative:              Fully Associative:
  Set Index points to 1 line    Set Index points to N lines         No Set Index (1 Set, all lines)
  [ Set 0: [ Line 0 ] ]         [ Set 0: [ Way 0 ] [ Way 1 ] ]      [ Way 0 ] [ Way 1 ] ... [ Way M ]
  [ Set 1: [ Line 1 ] ]         [ Set 1: [ Way 0 ] [ Way 1 ] ]      Single Tag comparison against
  1 Comparator, fast,           N Comparators in parallel,          ALL cache lines simultaneously.
  prone to conflict misses.     balances speed and miss reduction.  High power/silicon area.
+----------------------------------------------------------------------------------------------------+

1. Direct-Mapped Cache (N = 1):

- Every physical address maps to exactly one set containing exactly one cache line.

- Hardware: Requires only a single tag comparator and zero multiplexing logic, resulting in the fastest possible hit time.

- Critical Flaw: Highly vulnerable to Conflict Misses. If two actively accessed data arrays happen to have addresses with identical set index bits (e.g., address 0x1000 and 0x5000), they will continuously evict each other in an infinite ping-pong loop (cache thrashing), even if 99% of the cache is completely empty!

1. N-Way Set-Associative Cache (e.g., N = 4, 8, or 16):

- The cache is partitioned into S sets, where each set contains N parallel ways.

- Hardware: When the set index selects a set, N hardware comparators evaluate the tags of all N lines simultaneously. A hit occurs if any valid line matches the address tag.

- Benefit: Drastically reduces conflict misses. A conflict occurs only if more than N active memory blocks map to the exact same set. Modern L1 and L2 caches typically implement 4-way to 8-way associativity, while L3 caches use 16-way or 24-way associativity.

1. Fully Associative Cache:

- There is no set index (s = 0, S = 1). Any memory block can reside in any line in the cache.

- Hardware: Requires M parallel comparators (where M is the total number of lines in the cache). Because massive comparator arrays consume excessive silicon area and power, full associativity is restricted to small structures like Translation Lookaside Buffers (TLBs, 64–512 entries).

Cache Miss Taxonomy (The 3 Cs + 1)#

Cache misses fall into four foundational categories:

1. Compulsory (Cold) Misses: The very first access to a memory block. The block has never been in the cache. Unavoidable unless hardware prefetchers anticipate the access.
2. Capacity Misses: Occur when the working set of the active program exceeds the total physical byte capacity C of the cache.
3. Conflict (Collision) Misses: Occur in direct-mapped or set-associative caches when multiple active memory blocks map to the same set, exceeding the N ways of that set, even though the cache has remaining capacity elsewhere.
4. Coherence Misses: Occur in multicore systems when a cache line is invalidated because another processor core wrote to the same line.

Cache Replacement Policies#

When an N-way set is full and a cache miss occurs, the cache controller must select which existing line to evict:

• Least Recently Used (LRU): Evicts the line that has not been accessed for the longest period. Optimal for programs exhibiting temporal locality. True LRU requires maintaining an N(N-1)/2 bit state per set, which becomes expensive for N >= 8.
• Pseudo-LRU (PLRU): Uses a binary decision tree of N-1 bits per set to approximate LRU behavior with minimal silicon overhead.
• Random Replacement: Selects a victim line randomly. Surprisingly effective at high associativity (N >= 16) and completely immune to worst-case pathological access loops that defeat LRU.

Cache Write Policies#

Handling memory write transactions requires coordinating cache state with lower-level memory:

1. Write-Through vs. Write-Back:

- Write-Through: Every CPU write updates both the cache line and lower-level DRAM memory simultaneously. Simple, but saturates the memory bus with continuous write traffic.

- Write-Back: The CPU writes exclusively to the cache line in place. A dedicated hardware bit, the Dirty Bit, is set to 1. The modified data is written back to main memory ONLY when the dirty line is evicted to make room for a new block. This dramatically conserves bus bandwidth.

1. Write Allocation Policies:

- Write-Allocate: On a write miss, the missing 64-byte block is fetched from memory into the cache, and the write is performed in cache (typically paired with Write-Back).

- No-Write-Allocate: On a write miss, the block is written directly to lower memory without loading it into the cache (typically paired with Write-Through).

3. Multicore Cache Coherence & The MESI Protocol#

In modern symmetric multiprocessing (SMP) and multi-core processors, each CPU core possesses private L1 and L2 caches to ensure ultra-low latency. However, these private caches share a single unified physical address space in main DRAM.

The Coherence Problem#

Suppose Core 0 and Core 1 both read variable X = 5 from main memory. Both cores hold a local copy of X in their private L1 caches.

Now, Core 0 executes a store: X = 10. Under a write-back policy, Core 0 updates its local L1 cache line and marks it dirty.

If Core 1 subsequently reads X, its local L1 cache still holds X = 5! Core 1 would read stale data, violating the fundamental memory contract.

Cache Coherence guarantees that all processor cores observe a uniform, consistent view of memory: writes to any single memory location must be serialized and observed in the exact same order by all cores.

The MESI Protocol (Illinois Protocol)#

MESI is the classic 4-state invalidation-based snooping coherence protocol. Every cache line maintains a 2-bit state tag:

+-------+--------------------+----------------+----------------+-------------------------------+
| State | Name               | Line Valid?    | Line Dirty?    | Present in Other Core Caches? |
+-------+--------------------+----------------+----------------+-------------------------------+
| M     | Modified           | Yes            | Yes (Modified) | NO (Exclusive ownership)      |
| E     | Exclusive          | Yes            | No (Clean)     | NO (Exclusive ownership)      |
| S     | Shared             | Yes            | No (Clean)     | YES (May exist elsewhere)     |
| I     | Invalid            | NO             | No             | N/A (Stale / empty)           |
+-------+--------------------+----------------+----------------+-------------------------------+

State Definitions:

• Modified (M): The cache line is present exclusively in this core's cache and has been modified relative to main memory (dirty). This core is the sole owner.
• Exclusive (E): The cache line is present exclusively in this core's cache and is identical to main memory (clean).
• Shared (S): The cache line is present in this core's cache and is clean. Identical copies may simultaneously reside in the private caches of other cores.
• Invalid (I): The cache line contains invalid or stale data and cannot be read or written.

Bus Snooping & Transactions#

All private caches monitor (snoop) a shared interconnect bus. Caches broadcast transactions when state changes occur:

• BusRd (Bus Read): A core broadcasts a request to read a cache block without intent to modify.
• BusRdX (Bus Read with Invalidate / Read Invalidate): A core broadcasts a request to read a cache block with explicit intent to write, demanding that all other cores invalidate their copies.
• BusUpgr (Bus Upgrade): A core that already holds a line in state Shared (S) broadcasts intent to write, commanding all other cores holding S copies to invalidate them without re-fetching data.
• Flush: A core holding a line in state Modified (M) supplies the modified data to the requesting core and updates main DRAM memory.

State Transitions:
                             [ Invalid (I) ]
                                /         \
                  PrRd / BusRd /           \ PrWr / BusRdX
                              v             v
                       [ Shared (S) ] <---+ [ Modified (M) ]
                             ^            |      |
                    PrRd     |            | PrWr |
                  (no bus)   |            |      v
                       [ Exclusive (E) ] -+------+

Complete MESI State Transition Rules#

1. Core Initiates a Read (PrRd):

- Hit in M, E, or S: Read completes immediately with zero bus activity.

- Miss (State I): The core broadcasts BusRd.

- If no other core has the line: The line is fetched from memory and installed in state Exclusive (E).

- If another core has the line in state E or S: That core asserts a shared signal; the requesting core installs the line in state Shared (S).

- If another core has the line in state M: The owner core intervenes, broadcasts Flush to write the updated data to the bus/memory, transitions its own state from M to S, and the requesting core installs the line in state Shared (S).

1. Core Initiates a Write (PrWr):

- Hit in M: Write completes in-place immediately with zero bus activity.

- Hit in E: Silent upgrade! Because this core has exclusive ownership, it transitions from E to Modified (M) with zero bus broadcast overhead.

- Hit in S: The core broadcasts BusUpgr (or BusRdX). All other cores holding copies invalidate them (S -> I). The writing core transitions from S to Modified (M).

- Miss (State I): The core broadcasts BusRdX. All other cores invalidate their copies (S/E/M -> I). Any core holding M flushes its dirty data. The writing core fetches the line, modifies it, and installs it directly in state Modified (M).

4. Virtual Memory Systems, Multi-Level Paging & The TLB#

Virtual memory provides an abstraction layer that decouples an application program's view of memory from physical DRAM hardware.

Foundational Objectives of Virtual Memory#

1. Process Isolation & Hardware Protection: Each running operating system process executes within its own private Virtual Address Space. A process cannot read or corrupt memory belonging to another process or the OS kernel.
2. Efficient Memory Sharing: Read-only memory pages (such as shared C libraries, libc.so, or executable program binaries) can be mapped into multiple process virtual address spaces simultaneously while sharing a single physical DRAM frame.
3. Memory Oversubscription & Demand Paging: The sum of virtual memory allocated across processes can exceed physical DRAM. Inactive pages are transparently swapped out to backing storage (SSD/NVMe).

Virtual to Physical Address Translation#

The Memory Management Unit (MMU) translates Virtual Addresses (VA) into Physical Addresses (PA) using fixed-size blocks called pages (standard page size = 4 KB = 4096 bytes = 2^12 bytes).

A Virtual Address is partitioned into:

• Virtual Page Number (VPN): The upper address bits indexing the page table.
• Page Offset (12 bits): The lower 12 bits selecting the byte within the 4 KB page. The offset is passed through unchanged to the physical address.

Virtual Address (32 bits):
+-------------------------------------------------------+---------------------+
|              Virtual Page Number (VPN, 20 bits)       | Page Offset (12 b)  |
+-------------------------------------------------------+---------------------+
                           |
                           v  (Page Table Lookup)
+-------------------------------------------------------+---------------------+
|             Physical Frame Number (PFN, 20 bits)      | Page Offset (12 b)  |
+-------------------------------------------------------+---------------------+
Physical Address (32 bits)

The Multi-Level Page Table Architecture#

In a naive flat page table design on a 32-bit system:

• Total virtual pages = 2^32 / 4096 = 2^20 ≈ 1,048,576 pages.
• Each Page Table Entry (PTE) requires 4 bytes (storing PFN, Valid bit, Dirty bit, Read/Write permissions).
• A flat table requires 1,048,576 × 4 bytes = 4 Megabytes of contiguous physical memory for EVERY running process! In a system running 500 processes, 2 GB of DRAM would be wasted purely storing page tables, even if most processes only use 2 MB of code and data.

The Two-Level Hierarchical Paging Solution (x86 32-bit Architecture):

A 32-bit Virtual Address is partitioned into three fields:

Virtual Address:
+-------------------------------+------------------------------+---------------------+
| Page Directory Index (10 bits)| Page Table Index (10 bits)   | Page Offset (12 b)  |
+-------------------------------+------------------------------+---------------------+

1. Page Directory: The root of the hierarchy. Contains 1024 Page Directory Entries (PDEs). 1024 × 4 bytes = 4096 bytes (exactly one 4 KB page!). The physical address of the Page Directory is loaded into hardware control register CR3 during a context switch.
2. Page Tables: Each PDE points to a secondary Page Table containing 1024 Page Table Entries (PTEs).
3. Memory Savings: Secondary page tables are allocated on demand. If a process uses only 4 MB of address space at address 0x00400000 and 4 MB for its stack at 0xBFFFF000, only the Page Directory and TWO secondary page tables need to exist—consuming just 12 KB of RAM instead of 4 MB!

In 64-bit architectures (x86-64), this principle extends to 4-level paging (PML4 -> PDPT -> PD -> PT) or 5-level paging, translating 48-bit or 57-bit virtual addresses.

Translation Lookaside Buffers (TLB)#

Hierarchical paging introduces a severe performance penalty: translating a single virtual address in a 4-level page table requires four sequential memory accesses just to locate the PTE before the actual data load can occur!

The Translation Lookaside Buffer (TLB) is a high-speed, fully associative on-chip hardware cache that stores recent VPN -> PFN translation pairs.

• TLB Hit: The MMU checks the TLB concurrently with instruction decode. If the VPN hits, the physical frame number (PFN) is retrieved in under 1 clock cycle.
• TLB Miss: The hardware page-table walker accesses memory to traverse the multi-level page table, loads the PTE into the TLB, and resumes execution (incurring a 20 to 100 cycle stall).
• Effective Memory Access Time with TLB:

EMAT = TLB_Hit_Rate · (TLB_Latency + Memory_Access) + (1 - TLB_Hit_Rate) · (TLB_Miss_Penalty + Memory_Access).

5. Production Systems, OS Engineering & Performance Optimization#

Hardware memory hierarchies dictate software performance in high-concurrency systems and database engines.

Cache-Conscious Data Layout (Data-Oriented Design)#

In multi-dimensional array traversal, iteration order must match physical memory storage:

In C and C++, 2D arrays are stored in Row-Major Order (elements of row 0 are contiguous, followed by row 1):

// ROW-MAJOR TRAVERSAL (High Spatial Locality -> Maximum Performance)
for (int i = 0; i < N; i++) {
    for (int j = 0; j < M; j++) {
        sum += matrix[i][j]; // Strides by 4 bytes (hits within 64-byte line)
    }
}

// COLUMN-MAJOR TRAVERSAL (Pathological Striding -> Severe Cache Thrashing)
for (int j = 0; j < M; j++) {
    for (int i = 0; i < N; i++) {
        sum += matrix[i][j]; // Strides by M*4 bytes (misses on every access!)
    }
}

For large matrices (e.g., N = 4096), column-major traversal generates a cache miss on virtually every access, running 10× to 30× slower than row-major traversal purely due to L1/L2 cache line evictions.

False Sharing in Multithreaded Software#

False Sharing occurs when two independent threads executing on separate CPU cores modify distinct variables that happen to reside within the same 64-byte cache line:

struct ThreadStats {
    uint64_t counter_thread_0; // 8 bytes (Offset 0)
    uint64_t counter_thread_1; // 8 bytes (Offset 8)  <-- SAME 64-BYTE CACHE LINE!
};

When Thread 0 updates counter_thread_0, Core 0 broadcasts BusRdX, transitioning the cache line to M and invalidating Core 1's cache copy (I). When Thread 1 updates counter_thread_1, Core 1 broadcasts BusRdX, invalidating Core 0's copy. The cache line continuously ping-pongs between the cores over the interconnect bus.

Solution: Cache-Line Padding.

Align independent per-thread data structures to 64-byte boundaries:

struct alignas(64) PaddedCounter {
    uint64_t counter;
    uint8_t padding[56]; // Ensures each counter occupies its own 64-byte line
};

HugePages in Linux (2 MB and 1 GB Pages)#

A standard 512-entry L1 TLB with 4 KB pages covers 512 × 4 KB = 2 Megabytes of memory.

In large-scale in-memory databases (Redis, PostgreSQL, SAP HANA) managing 128 GB of data, the entire TLB is permanently overwhelmed, resulting in catastrophic TLB thrashing where over 25% of CPU cycles are wasted walking page tables.

By enabling Linux HugePages (2 MB pages):

• A 512-entry TLB covers 512 × 2 MB = 1 Gigabyte of memory!
• TLB misses drop by over 99%, boosting database query throughput by 15% to 30%.

6. Common Architectural Pitfalls & Misconceptions#

Understanding memory architectures requires identifying critical operational misconceptions.

Pitfall 1: Confusing Cache Coherence with Memory Consistency#

Cache coherence guarantees that all cores agree on the order of writes to a single memory address.

Memory consistency defines the rules governing the allowable ordering of reads and writes across different memory addresses. Even on a perfectly coherent system, out-of-order execution and store buffers can reorder memory writes to different locations unless explicit memory barrier instructions (FENCE, MFENCE, or acquire/release semantics) are used.

Pitfall 2: Believing Write-Back Caches Eliminate All Bus Traffic#

While a write-back cache eliminates bus traffic for clean hits, when a dirty cache line is evicted to make room for a new block, the dirty line must be written back to lower-level memory. If an application continuously accesses a working set larger than the cache with heavy writes, every cache miss triggers both a memory block fetch AND a dirty block eviction write, doubling memory bus bandwidth consumption.

Pitfall 3: Assuming Increased Associativity Always Reduces Latency#

Increasing associativity from 4-way to 8-way reduces conflict misses, but increases the hit latency because wider multiplexers and more parallel comparators lengthen the combinational delay of the L1 cache. If an L1 cache hit requires 2 clock cycles instead of 1, the processor's critical path and overall IPC suffer. Modern designs strike a balance: L1 caches favor low associativity (4-way to 8-way) for 1-cycle access, while L3 caches utilize high associativity (16-way to 24-way) where hit latency is already 40+ cycles.

7. Comprehensive Checkpoint Practice Problems & Complete Step-by-Step Solutions#

Mastery of cache geometry, coherence states, and virtual memory requires solving rigorous quantitative problems.

Problem 1 (Set-Associative Cache Geometry & Bitfield Decomposition):

A 64-bit microprocessor implements a 32 Kilobyte (32 KB) 4-way set-associative data cache with 64-byte cache lines. The physical address space is 48 bits (m = 48).

1. Calculate the number of byte offset bits (b), the total number of sets (S), the number of set index bits (s), and the number of tag bits (t).
2. Given the physical memory address 0x00007FFF8A4C2180, determine the exact hexadecimal tag, the decimal set index, and the byte offset.
3. Calculate the total hardware storage overhead in bits required to implement the cache tags and valid/dirty status bits across the entire cache (assume 1 valid bit and 1 dirty bit per line).

Solution:

Step 1: Calculate Bitfield Widths

Given parameters:

• Physical address width: m = 48 bits.
• Cache data capacity: C = 32 KB = 32 × 1024 bytes = 32,768 bytes = 2^15 bytes.
• Cache line size: B = 64 bytes = 2^6 bytes.
• Associativity: N = 4 ways per set.

1. Byte Offset bits (b):

b = log2(B) = log2(64) = 6 bits.

1. Total Cache Lines:

Total_Lines = C / B = 32,768 / 64 = 512 lines.

1. Total Cache Sets (S):

S = Total_Lines / N = 512 / 4 = 128 sets = 2^7 sets.

1. Set Index bits (s):

s = log2(S) = log2(128) = 7 bits.

1. Tag bits (t):

t = m - s - b = 48 - 7 - 6 = 35 bits.

Verify address partition: 35 (Tag) + 7 (Index) + 6 (Offset) = 48 bits.

Step 2: Decompose Physical Address 0x00007FFF8A4C2180

Convert the 48-bit address into binary:

Hex: 7 F F F 8 A 4 C 2 1 8 0 (12 hex digits = 48 bits)

• 7: 0111
• F: 1111
• F: 1111
• F: 1111
• 8: 1000
• A: 1010
• 4: 0100
• C: 1100
• 2: 0010
• 1: 0001
• 8: 1000
• 0: 0000

Extract bitfields from right to left:

1. Byte Offset (lowest 6 bits):

Bits [5:0] = 00 0000 (binary) = 0 (decimal) = 0x00.

1. Set Index (next 7 bits, bits [12:6]):

Examine bits from hex digits 1, 8, 0:

- Hex 1: 0001

- Hex 8: 1000

- Hex 0: 0000

Bits [12:0] = 1 1000 0000

Bits [5:0] = 000000 (Offset)

Bits [12:6] = 110 0110 (binary)

Let's verify carefully:

Address: ... 2 1 8 0

Binary: ... 0010 0001 1000 0000

Bit indices:

Bits 3..0 = 0000 (digit 0)

Bits 7..4 = 1000 (digit 8)

Bits 11..8 = 0001 (digit 1)

Bits 15..12 = 0010 (digit 2)

Offset = Bits [5:0] = Bits [5:4] of digit 8 + Bits [3:0] of digit 0 = 00 + 0000 = 000000 = 0.

Index = Bits [12:6] = Bit 12 (from digit 2) + Bits [11:8] (digit 1) + Bits [7:6] (digit 8):

Bit 12 = 0 (lowest bit of 0010)

Bits [11:8] = 0001

Bits [7:6] = 10 (top two bits of 1000)

Concatenated Index = 0 + 0001 + 10 = 0000110 = 6 (decimal).

1. Tag (remaining upper 35 bits, bits [47:13]):

Address shifted right by 13 bits:

0x7FFF8A4C2180 >> 13 = 0x3FFF_C526_10...

Dividing 0x7FFF8A4C2180 by 8192 (2^13):

Tag = 0x00003FFF8A4C2180 >> 13 = 0x3FFF_C526_1 (hexadecimal).

Summary:

• Byte Offset = 0 (decimal 0x00)
• Set Index = 6 (decimal)
• Tag = 35-bit value

Step 3: Calculate Cache Metadata Storage Overhead

Total lines = 512 lines.

Each line requires:

• Tag storage: 35 bits.
• Valid bit: 1 bit.
• Dirty bit: 1 bit.

Metadata per line = 35 + 1 + 1 = 37 bits.

Total metadata bits for the entire cache:

Total_Metadata = 512 lines × 37 bits/line = 18,944 bits = 2,368 bytes ≈ 2.31 KB.

Problem 2 (Average Memory Access Time in a 3-Level Cache Hierarchy):

A high-performance server core features a 3-level cache hierarchy with the following measured access times and local miss rates:

• L1 Data Cache: Hit Time H1 = 1.2 ns, Local Miss Rate M1 = 6.0% (0.060).
• L2 Unified Cache: Hit Time H2 = 4.0 ns, Local Miss Rate M2 = 15.0% (0.150).
• L3 Shared Cache: Hit Time H3 = 18.0 ns, Local Miss Rate M3 = 25.0% (0.250).
• Main Memory (DRAM): Latency = 75.0 ns.

1. Calculate the global miss rate for the L2 cache and the L3 cache.
2. Compute the exact Average Memory Access Time (AMAT) in nanoseconds.
3. If an architectural prefetcher reduces the L3 local miss rate from 25.0% down to 10.0%, calculate the new AMAT and the overall memory latency reduction percentage.

Solution:

Step 1: Calculate Global Miss Rates

• Global L1 Miss Rate = M1 = 0.060 (6.0%).
• Global L2 Miss Rate = M1 · M2 = 0.060 · 0.150 = 0.0090 (0.90% of all memory accesses miss both L1 and L2).
• Global L3 Miss Rate = M1 · M2 · M3 = 0.060 · 0.150 · 0.250 = 0.00225 (0.225% of all accesses reach main DRAM).

Step 2: Compute Exact Baseline AMAT

The recursive AMAT equation is:

AMAT = H1 + M1 · [ H2 + M2 · [ H3 + M3 · DRAM_Latency ] ].

Work from the innermost memory layer outward:

1. L3 Penalty to DRAM:

Penalty_L3 = H3 + M3 · DRAM_Latency

Penalty_L3 = 18.0 ns + 0.250 · 75.0 ns

Penalty_L3 = 18.0 + 18.75 = 36.75 ns.

1. L2 Penalty to L3:

Penalty_L2 = H2 + M2 · Penalty_L3

Penalty_L2 = 4.0 ns + 0.150 · 36.75 ns

Penalty_L2 = 4.0 + 5.5125 = 9.5125 ns.

1. Total AMAT at L1:

AMAT = H1 + M1 · Penalty_L2

AMAT = 1.2 ns + 0.060 · 9.5125 ns

AMAT = 1.2 + 0.57075 = 1.77075 ns.

Baseline AMAT is approximately 1.771 ns.

Step 3: Impact of Prefetcher Reducing L3 Miss Rate to 10.0%

With new M3_new = 0.100:

1. New Penalty_L3:

Penalty_L3_new = 18.0 ns + 0.100 · 75.0 ns = 18.0 + 7.50 = 25.50 ns.

1. New Penalty_L2:

Penalty_L2_new = 4.0 ns + 0.150 · 25.50 ns = 4.0 + 3.825 = 7.825 ns.

1. New AMAT:

AMAT_new = 1.2 ns + 0.060 · 7.825 ns = 1.2 + 0.4695 = 1.6695 ns.

Calculate percentage reduction:

Reduction = [ (1.77075 - 1.6695) / 1.77075 ] · 100% = (0.10125 / 1.77075) · 100% ≈ 5.7179% ≈ 5.72%.

Average memory access latency drops by 5.72%, delivering a direct IPC boost across memory-bound workloads.

Problem 3 (MESI Cache Coherence Protocol Trace):

A dual-core symmetric multiprocessor (SMP) features private L1 caches implementing the MESI snooping protocol over a shared bus. Main memory holds initial variable X = 100. Initially, neither Core 0 nor Core 1 holds X in cache (both in state Invalid I).

Trace the execution of the following sequential operations:

• Event 1: Core 0 reads variable X.
• Event 2: Core 1 reads variable X.
• Event 3: Core 0 writes X = 200.
• Event 4: Core 1 reads variable X.
• Event 5: Core 0 evicts cache line X to make room for another address.

For each event:

1. State of Core 0's cache line.
2. State of Core 1's cache line.
3. Bus transaction broadcast on the snooping bus.
4. Value of X in main memory.

Solution:

Trace Evaluation Table:

+-------+---------------+---------------+---------------+-------------------+---------------+
| Event | Action        | Core 0 State  | Core 1 State  | Bus Transaction   | Memory Value  |
+-------+---------------+---------------+---------------+-------------------+---------------+
| Init  | Startup       | I (Invalid)   | I (Invalid)   | None              | X = 100       |
| 1     | Core 0 reads X| E (Exclusive) | I (Invalid)   | BusRd             | X = 100       |
| 2     | Core 1 reads X| S (Shared)    | S (Shared)    | BusRd             | X = 100       |
| 3     | Core 0 writes | M (Modified)  | I (Invalid)   | BusUpgr (or BusRdX| X = 100       |
| 4     | Core 1 reads X| S (Shared)    | S (Shared)    | BusRd + Flush     | X = 200       |
| 5     | Core 0 evicts | I (Invalid)   | S (Shared)    | None (Clean line) | X = 200       |
+-------+---------------+---------------+---------------+-------------------+---------------+

Detailed Walkthrough:

• Event 1 (Core 0 reads X): Core 0 broadcasts BusRd. Core 1 does not have the block. The line is read from DRAM. Because no other core has a copy, Core 0 installs the line in state Exclusive (E). Memory holds X = 100.
• Event 2 (Core 1 reads X): Core 1 broadcasts BusRd. Core 0 snoops this request. Because Core 0 holds X in state E, it asserts the shared signal and transitions its own state from E to Shared (S). Core 1 installs X in state Shared (S).
• Event 3 (Core 0 writes X = 200): Core 0 has X in state S. To write, it must acquire exclusive ownership. Core 0 broadcasts BusUpgr (or BusRdX). Core 1 snoops BusUpgr and invalidates its copy (I). Core 0 updates X = 200 in-place and transitions to Modified (M). Main memory still holds stale X = 100 (write-back).
• Event 4 (Core 1 reads X): Core 1 misses (state I) and broadcasts BusRd. Core 0 snoops BusRd while holding X in state M. Core 0 intervenes, supplies the dirty data (X = 200) via a Flush transaction, writing X = 200 back to main DRAM memory. Both Core 0 and Core 1 transition to state Shared (S).
• Event 5 (Core 0 evicts X): In Event 4, Core 0 transitioned to S (clean relative to memory). When a clean S line is evicted, it requires zero bus activity and simply transitions to Invalid (I). Core 1 remains in state S. Memory holds X = 200.

Problem 4 (Two-Level Page Table Translation & Effective Memory Access Time):

A 32-bit virtual memory system implements two-level hierarchical paging with 4 KB pages:

• Virtual Address is partitioned as: 10-bit Page Directory Index (PDI), 10-bit Page Table Index (PTI), 12-bit Page Offset.
• A fully associative Translation Lookaside Buffer (TLB) has a hit latency of 1.0 ns and achieves a 98.0% hit rate (0.980).
• Physical DRAM memory access latency is 60.0 ns.

1. Decompose the Virtual Address 0x7A3B5C10 into its exact numerical PDI, PTI, and Page Offset (in both hexadecimal and decimal).
2. Calculate the Effective Memory Access Time (EMAT) for virtual memory address translations assuming a 98% TLB hit rate.
3. Explain why the multi-level page table structure saves physical memory for sparse processes compared to a single flat page table.

Solution:

Step 1: Decompose Virtual Address 0x7A3B5C10

Convert 0x7A3B5C10 to 32-bit binary:

Hex: 7 A 3 B 5 C 1 0

• 7: 0111
• A: 1010
• 3: 0011
• B: 1011
• 5: 0101
• C: 1100
• 1: 0001
• 0: 0000

Binary: 0111 1010 0011 1011 0101 1100 0001 0000

Partition into bitfields:

1. Page Offset (lowest 12 bits, bits [11:0]):

Bits [11:0] = 1100 0001 0000

Hex = 0xC10.

Decimal = 12 · 256 + 1 · 16 + 0 = 3072 + 16 = 3088.

1. Page Table Index (middle 10 bits, bits [21:12]):

Bits [21:12] = 11 1011 0101

Hex = 0x3B5.

Decimal = 3 · 256 + 11 · 16 + 5 = 768 + 176 + 5 = 949.

1. Page Directory Index (highest 10 bits, bits [31:22]):

Bits [31:22] = 0111 1010 00

Hex = 0x1E8.

Decimal = 1 · 256 + 14 · 16 + 8 = 256 + 224 + 8 = 488.

Summary:

• Page Directory Index (PDI) = 488 (0x1E8)
• Page Table Index (PTI) = 949 (0x3B5)
• Page Offset = 3088 (0xC10)

Step 2: Calculate Effective Memory Access Time (EMAT)

• Case 1 (TLB Hit): Access TLB (1.0 ns), retrieve physical address, access physical DRAM for the requested data word (60.0 ns).

Time_Hit = 1.0 ns + 60.0 ns = 61.0 ns.

• Case 2 (TLB Miss): Access TLB (1.0 ns), miss. The hardware page walker must:

1. Access Page Directory in DRAM: +60.0 ns

2. Access Page Table in DRAM: +60.0 ns

3. Access actual target data word in DRAM: +60.0 ns

Time_Miss = 1.0 ns + 60.0 ns + 60.0 ns + 60.0 ns = 181.0 ns.

Calculate EMAT:

EMAT = (TLB_Hit_Rate · Time_Hit) + ((1 - TLB_Hit_Rate) · Time_Miss)

EMAT = (0.980 · 61.0 ns) + (0.020 · 181.0 ns)

EMAT = 59.78 ns + 3.62 ns = 63.40 ns.

With a 98% TLB hit rate, effective access time is 63.40 ns—only 5.6% slower than direct physical memory access (60 ns), demonstrating how TLBs eliminate the page table walking bottleneck.

Step 3: Memory Savings of Hierarchical Paging

A single flat page table requires allocating all 2^20 Page Table Entries upfront, consuming 4 MB of contiguous DRAM per process regardless of whether the process uses 1 page or 1 million pages.

In a two-level page table, only the root Page Directory (4 KB) must be resident. Secondary page tables are allocated dynamically only when memory in that 4 MB virtual region is actively mapped. If a process uses only 2 MB of memory, it requires only the Page Directory (4 KB) and a single secondary Page Table (4 KB)—consuming a mere 8 KB of RAM (a 99.8% reduction in memory overhead!).