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.
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.
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)
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.
last_writer[]. Whenever an instruction writes to a destination register, we record that instruction's unique ID.last_writer[] and records up to two predecessor IDs in pred_instr_ids[0] and pred_instr_ids[1].critical_pc_table of instruction addresses known to be critical from past executions. If an instruction's Program Counter (PC) is already in this table, we proactively mark it as is_critical = true immediately at dispatch—without waiting for it to become slow again.(Hook: Deep dive into Topic 02: Register Dependency Tracking at Dispatch)
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.
latency = retire_time - dispatch_time.(Hook: Deep dive into Topic 03: Memory Latency Measurement & Adaptive Thresholding)
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.
pred_instr_ids[] links recorded at dispatch.is_critical = true.critical_pc_table so that future dynamic instances can be recognized and prioritized immediately upon dispatch.(Hook: Deep dive into Topic 04: Backward Slice Construction via BFS)
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:
(Hook: Deep dive into Topic 05: Priority Scheduling & ROB-Head Liveness)
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)
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.