CPU Memory Hierarchy: Latencies and Optimization

Memory Hierarchy in Modern Processors: From Registers to DRAM

In modern systems, cache misses cost 100–200 cycles, while hits take 1–4 cycles. This determines code performance. Consider a real case: optimizing a network interface driver on RISC-V at 1 GHz. Expected packet processing — 2 million/s at 500 instructions per packet (500 ns). Actually achieved 200 thousand/s.

Profiling revealed:

$ perf stat -e cycles,instructions,cache-misses ./driver_test
  Performance counter stats:
    5,000,000 cycles
      500,000 instructions
       45,000 cache-misses

500 thousand instructions require 500 thousand cycles at IPC=1, but 5 million were spent. The difference — 45 thousand misses × 100 cycles = 4.5 million cycles. Computations took 10%, memory waiting — 90%.

Memory Hierarchy Structure

Memory is organized as a hierarchy with decreasing speed and increasing size:

| Level | Type | Latency | Size |

|---------|-----|----------|--------|

| Registers | 32 registers | 1 cycle | ~128 B |

| L1 Cache | Instruction/Data | 3–4 cycles | 32–64 KB |

| L2 Cache | Unified | 12–15 cycles | 256–512 KB |

| L3 Cache | Shared | 40–50 cycles | 2–32 MB |

| DRAM | Main | 100–200 cycles | GB–TB |

Key properties:

• Speed drops from 1 to 200 cycles.
• Size grows from 128 B to TB.
• DRAM is 100–200 times slower than L1.

In microcontrollers (RISC-V RV32IMC, 100 MHz) the hierarchy is simplified:

| Level | Type | Latency | Size |

|---------|-----|----------|--------|

| Registers | 32 registers | 1 cycle | 128 B |

| I-cache L1 | Instructions | 1 cycle | 16 KB |

| D-cache L1/SRAM | Data | 1–2 cycles | 8–32 KB |

| Flash | Code | ~10 cycles | 128 KB–1 MB |

| DRAM | Data | 50–100 cycles | 8–64 MB |

Differences: small caches, no L2/L3, Flash instead of DRAM for code, limited size.

Cache Lines and Data Access

Caches work in 64-byte blocks. Accessing 1 byte loads the entire line.

Example access to int:

int x = array[0];  // 4 bytes at 0x1000
// Loads 64 bytes: 0x1000–0x103F (16 ints)

Sequential access is efficient:

for (int i = 0; i < 16; i++) {
    sum += array[i];  // 1 miss, 15 hits
}

Random — not:

for (int i = 0; i < 16; i++) {
    sum += array[random_index[i]];  // Many misses
}

Cache Organization: Sets and Ways

Cache is divided into sets and ways. Direct mapped:

Address bits: [Tag | Index | Offset]

For 32 KB, 64 B/line: 512 lines, 9-bit index, 6-bit offset, 17-bit tag (32-bit address).

Conflicts: arrays a[1024] (0x10000) and b[1024] (0x18000) map to the same sets.

Set-associative (N-way): a set contains N lines, reduces conflicts.

Typical parameters:

• L1: 8-way, 32–64 KB.
• L2: 8–16-way, 256–512 KB.
• L3: 16-way, 2–32 MB.

Embedded: direct or 2-way, high conflict probability.

Access Locality

Spatial: adjacent addresses.

Good:

for (int i = 0; i < n; i++) sum += array[i];

Bad:

for (int i = 0; i < n; i++) sum += array[random[i]];

Temporal: repeated access.

Good:

int temp = array[0];
for (int i = 0; i < 1000; i++) result += temp * i;

Bad:

for (int i = 0; i < 1000; i++) result += array[i % 10] * i;

Optimal code (matrix multiplication):

for (int i = 0; i < N; i++) {
    for (int k = 0; k < N; k++) {
        int r = A[i][k];
        for (int j = 0; j < N; j++) {
            C[i][j] += r * B[k][j];
        }
    }
}

Prefetcher and Its Limitations

Prefetcher preloads data based on patterns.

• Sequential: for for(i) sum += array[i];
• Stride: for sum += array[i*2];

Limitations:

• Doesn't work on random accesses.
• Limited to 10–20 lines.
• Fooled by array interleaving.

In microcontrollers — simple or absent.

Bandwidth and Multi-Core

DDR4-3200: 25.6 GB/s/channel, dual-channel — 51.2 GB/s. L1: ~1000 GB/s.

Embedded: SRAM 1–4 GB/s, DRAM 100–500 MB/s. Keep working set in SRAM.

MESI protocol (x86/ARM):

• M: Modified.
• E: Exclusive.
• S: Shared.
• I: Invalid.

False sharing:

struct { int c0, c1; } shared;  // Ping-pong

Solution:

struct { int c0; char pad[60]; int c1; } shared;

RISC-V: weak memory model, use fence:

sw a0, 0(a1)
fence w, w
sw a2, 0(a3)

Atomics: lr.w/sc.w.

What's Important

• Cache misses dominate: 90% time on waiting.
• 64 B lines: sequential access gives 15 free hits.
• Locality (spatial/temporal) — key to optimization.
• Embedded systems: simplified hierarchy, no prefetcher.
• MESI and padding prevent ping-pong in multi-core.

— Editorial Team