4–5 Minute Detailed Architecture: CRISP (Critical Slice Prefetching & Scheduling)

Target Duration: ~3.5 to 5 minutes (~650–850 spoken words)
Goal: Deliver an end-to-end architectural explanation covering the memory wall bottleneck, dependency tracking at dispatch, latency detection at retirement, backward slice construction, priority scheduling with liveness guarantees, and benchmark results.


🎙️ Spoken Script & Architectural Walkthrough

To explain the complete architecture of CRISP, I divide the system into five main stages: the out-of-order memory bottleneck, dependency tracking at dispatch, latency detection and adaptive thresholding at retirement, backward slice construction, and priority scheduling with liveness guarantees.


Stage 1: The Out-of-Order Memory Bottleneck

Modern processors execute instructions out of order: when an instruction's inputs are ready, it executes immediately, even if earlier instructions are still waiting.

However, all instructions must retire and commit in strict program order at the head of the Reorder Buffer (ROB) to preserve program correctness. The ROB has a finite size—typically 256 instructions in our simulated core.

The problem arises with long-latency memory loads. When a load instruction misses in L1, L2, and the Last-Level Cache (LLC), it must fetch data from DRAM, which takes 200 or more processor cycles. If this slow load sits at the head of the Reorder Buffer, it cannot retire. Within a few dozen cycles, instructions behind it fill up the remaining ROB slots. Once the ROB is full, instruction dispatch stalls completely.

In pointer-chasing workloads—like linked lists, search trees, and graphs—consecutive loads depend directly on previous loads. The CPU spends most of its time stalled, waiting for memory addresses to be calculated. The core idea of CRISP is simple: if we can identify the instructions that compute the address of a slow load and schedule them earlier, the memory request is sent to DRAM sooner, finishes sooner, and prevents the pipeline from freezing.

(Hook: Deep dive into Topic 01: OoO Memory Bottleneck & ROB Stalls)


Stage 2: Register Dependency Tracking at Dispatch

To prioritize the instructions that feed a slow load, the processor must know which instruction produced each operand. We track this in the dispatch stage (dispatch_instruction()).

Dispatch is the ideal stage for dependency tracking because it is the earliest point where registers are renamed, instruction IDs are assigned, and register dependencies are fully known.

(Hook: Deep dive into Topic 02: Register Dependency Tracking at Dispatch)


Stage 3: Latency Measurement & Adaptive Thresholding at Retirement

The next question is: how does the processor know which loads are actually slow?

We detect slow loads in the retirement stage (retire_rob()). This is because retirement is the only point in the entire pipeline where the actual total memory latency is known—after the load has traveled through the full cache hierarchy and DRAM.

(Hook: Deep dive into Topic 03: Memory Latency Measurement & Adaptive Thresholding)


Stage 4: Backward Slice Construction via BFS

When a delinquent load is identified, we call build_slice_and_mark_critical() to discover its critical slice—the chain of instructions that calculated its memory address.

(Hook: Deep dive into Topic 04: Backward Slice Construction via BFS)


Stage 5: Priority Scheduling with ROB-Head Liveness Guarantee

The actual performance improvement happens in the execution stage (execute_instruction()), where the out-of-order core decides which ready instructions to issue.

In stock ChampSim, the scheduler simply selects ready instructions in program order. In CRISP, we separate ready instructions into two groups: ready_criticals and ready_non_criticals.

However, purely prioritizing critical instructions could cause a serious correctness bug: pipeline deadlock. Because the ROB must retire in program order, if the instruction at the head of the ROB is starved of execution slots, it can never retire, and the entire CPU hangs.

To eliminate this risk, we enforce a strict three-step scheduling rule:

  1. Liveness Guarantee: If the instruction at the head of the ROB is ready, it is unconditionally issued first. This guarantees forward progress under all conditions.
  2. Critical Priority: Next, all ready critical instructions are issued up to the remaining execution width.
  3. Non-Critical Issue: Any remaining execution slots in that cycle are filled by non-critical instructions in program order.

(Hook: Deep dive into Topic 05: Priority Scheduling & ROB-Head Liveness)


Evaluation & Benchmark Results

We evaluated CRISP on ChampSim across five 25-million instruction traces:

Benchmark Trace Workload Type Baseline IPC CRISP IPC IPC Speedup
LimitOrderBook Financial Matching Engine (AVL Tree) 1.184 1.243 +4.98%
ReverseLL Large Linked-List Reversal 0.6817 0.6912 +1.39%
BFS Graph Breadth-First Search 0.1617 0.1636 +1.18%
Exchange SPEC CPU 2017 Benchmark 1.312 1.325 +0.99%
SSSP Single-Source Shortest Path (GAP) 0.2207 0.2211 +0.18%

The results confirmed our hypothesis: Limit Order Book achieved the largest speedup (+4.98%) because AVL tree operations follow short, repetitive, and predictable pointer-chasing patterns. CRISP quickly learned the critical slice and consistently scheduled it first. Workloads with irregular, random memory access patterns (like SSSP) showed smaller gains, as their dependency chains vary with each access.

Overall, CRISP showed that intelligent instruction scheduling inside the CPU execution core can meaningfully reduce memory stall penalties without requiring complex hardware modifications to the cache hierarchy.

(Hook: Deep dive into Topic 06: Benchmark Evaluation & Workload Analysis)


Key Challenge Faced & How We Overcame It

The main challenge was identifying critical loads dynamically.

In the original CRISP paper by Litz et al., published at ASPLOS 2022, critical instructions are identified through an offline profiling and analysis process, and that information is used to guide execution. In my implementation, I wanted to explore a runtime approach in ChampSim rather than rely on pre-annotated instruction traces.

The challenge was deciding when a load should be considered critical. Memory latency varies across instructions and workloads, so a fixed threshold could be too rigid. I implemented runtime latency measurement at retirement, maintained a moving average of observed latency, and used an adaptive threshold to identify potentially critical loads.

Once a slow load was detected, I traced its recorded register dependencies backward using BFS, marked the resulting instructions as critical, and prioritized ready critical instructions during execution.

This was challenging because I had to connect runtime latency detection, dependency tracking, slice construction, and scheduling into one working mechanism. It also helped me understand the trade-offs involved in approximating a research technique in a simulator.