Topic 01: The Out-of-Order Memory Bottleneck & ROB Stalls

Overview: Why long-latency memory loads cause out-of-order CPUs to freeze, how Reorder Buffer (ROB) head blocking leads to pipeline stalls, and why traditional hardware prefetchers fail on pointer-chasing workloads.


1. High-Level Summary

Subsystem Component What It Does The Bottleneck / Problem How CRISP Solves It
Out-of-Order CPU Core Executes instructions when data is ready rather than in strict code order. Limited by finite execution window (256-entry ROB in ChampSim). Prioritizes instructions that compute addresses for slow loads.
Reorder Buffer (ROB) Ensures instructions commit and retire in original program order. If a slow load is at the ROB head, no subsequent instruction can retire. Executes the load address computation earlier so the load returns sooner.
DRAM Access Penalty Main memory access when a load misses L1, L2, and Last-Level Cache (LLC). Takes 200+ CPU cycles, during which the CPU pipeline sits idle. Hides DRAM latency by overlapping address generation with independent execution.
Pointer Chasing Traversing linked lists, trees, or graph nodes (e.g. curr = curr->next). Next address is unpredictable; conventional stride prefetchers fail completely. Executes the exact chain of program instructions (the critical slice) ahead of time.

2. Spoken Interview Answer (Simple & Direct)

"Modern processors are designed to be out-of-order: whenever an instruction has its inputs ready, it can execute immediately without waiting for earlier, unrelated instructions.

However, to guarantee program correctness and handle exceptions safely, all instructions must retire in strict program order at the head of the Reorder Buffer, or ROB. In our simulated processor, the ROB holds up to 256 instructions.

The biggest performance bottleneck occurs when a memory load misses in all levels of the cache hierarchy—L1, L2, and LLC—and has to fetch data all the way from DRAM. A DRAM trip takes over 200 processor cycles. If this slow load reaches the head of the ROB, it cannot retire until its data arrives.

Meanwhile, the processor keeps fetching new instructions behind it until all 256 ROB slots are completely full. Once the ROB fills up, the dispatch stage freezes. Even though the CPU has free execution units, the entire core stalls.

This problem is especially painful in pointer-chasing workloads—like linked lists, search trees, and graphs—because the address of the next node is stored inside the current node. Conventional hardware prefetchers look for sequential or constant stride patterns, so they cannot predict these irregular addresses.

CRISP solves this bottleneck not by guessing addresses, but by identifying the instructions that compute those addresses and scheduling them with high priority. That way, the slow load is launched to memory earlier, finishes earlier, and prevents the ROB from filling up."


3. Architecture & Mechanics

3.1 The Domino Effect of a DRAM Stall

When a slow load sits at the head of the Reorder Buffer, it triggers a chain reaction that halts the entire CPU pipeline:

Cycle 0: Delinquent Load reaches ROB Head
         [ROB Head: Load (waiting for DRAM)] <-- CANNOT RETIRE!
         │
         ▼
Cycle 20: Execution continues behind the load
          [Slot 1..50: Independent ALU / math instructions finish]
          [Slot 51..100: Dependent instructions wait for data]
         │
         ▼
Cycle 60: Reorder Buffer reaches full capacity (256 / 256 slots used)
          [ROB IS COMPLETELY FULL]
         │
         ▼
Cycle 61: Pipeline Dispatch Freezes!
          Decode Stage Stalled ---> Fetch Stage Stalled ---> Core Idle
         │
         ▼
Cycle 200+: DRAM finally returns data!
            Load completes -> ROB unblocks -> Pipeline slowly restarts

3.2 Why Conventional Prefetchers Fail on Pointer Chasing

Modern CPUs include hardware prefetchers (like Stream or Best-Offset prefetchers) that monitor memory address sequences:

Because the address cannot be guessed, the only way to get the data sooner is to calculate the address faster. That is the core philosophy of CRISP.


4. Common Interview Questions

Q1: Why must instructions retire in program order if they execute out of order?

Answer: "In-order retirement is necessary to support precise exceptions and preserve program correctness. If an instruction causes an error (like a page fault or divide-by-zero), the operating system must see the architectural register state exactly as if the program executed instruction-by-instruction. The Reorder Buffer holds completed speculative instructions and only commits their results to the register file when all preceding instructions have retired without error."

Q2: How does a larger Reorder Buffer impact this problem?

Answer: "A larger ROB (e.g. 512 entries instead of 256) gives the CPU a wider execution window to find independent work while waiting for memory. However, increasing the ROB size increases hardware area, power consumption, and wire latency. Furthermore, in pointer-chasing code, instructions naturally depend on each other, so even a huge ROB quickly fills up with dependent instructions waiting on the same slow load."

Q3: How does CRISP differ from Runahead Execution?

Answer: "Runahead execution lets the processor enter a speculative 'dummy' mode during a long-latency stall, executing instructions ahead and tossing results away just to trigger data prefetches. However, runahead execution requires complex hardware checkpointing, burns substantial extra power, and can pollute caches with useless data. CRISP avoids all of that: it stays in normal execution mode and simply reorders the existing instruction stream so the critical slice executes first."