CRISP: Critical Slice Prefetching & Instruction Scheduling (ChampSim)

A comprehensive interview and technical reference hub for CRISP—a lightweight critical-slice instruction scheduler implemented inside the ChampSim cycle-accurate out-of-order processor simulator. The project identifies long-latency memory loads at runtime, records producer-consumer register dependencies, constructs backward dependency slices via breadth-first search, and prioritizes critical instructions during out-of-order execution while guaranteeing ROB-head forward progress to eliminate pipeline deadlocks.


📂 Speeches & Documentation

File Type Duration Primary Focus
intro.html Spoken Pitch 1–2 mins Crisp elevator pitch focusing on the research paper, the memory wall problem, the three core pillars, strategic interviewer hooks, and quick-fire follow-up Q&As.
detailed.html Architecture Speech 4–5 mins Full end-to-end architectural narrative covering the OoO pipeline, dependency tracking at dispatch, adaptive thresholding at retirement, backward BFS slicing, priority scheduling with liveness guarantees, and benchmark results.
topic_01_ooo_memory_bottleneck_and_rob_stalls.html Deep Dive 2–3 mins Out-of-order execution window, 200+ cycle DRAM latency penalties, in-order ROB retirement, head blocking, and why conventional stride prefetchers fail on pointer chasing.
topic_02_dependency_tracking_at_dispatch.html Deep Dive 2–3 mins Register renaming at dispatch, last_writer[] tracking table, pred_instr_ids[] backward links, and proactive marking using critical_pc_table.
topic_03_latency_detection_and_adaptive_thresholding.html Deep Dive 2–3 mins End-to-end memory latency measurement at retire_rob(), running Exponential Moving Average (EMA), and dynamic threshold zones adapting across memory phases.
topic_04_backward_slice_construction_bfs.html Deep Dive 2–3 mins Critical slice extraction using bounded backward Breadth-First Search (depth ≤ 32), setting is_critical = true, and caching delinquent load PCs.
topic_05_priority_scheduling_and_liveness.html Deep Dive 2–3 mins Two-tier priority queue (criticals vs non-criticals), three-step issue policy, and the unconditional ROB-head progress guarantee eliminating pipeline deadlocks.
topic_06_benchmark_evaluation_and_workload_analysis.html Deep Dive 2–3 mins Workload sensitivity across five 25M traces: why Limit Order Book achieved +4.98% IPC while irregular graph traversal (SSSP) achieved +0.18%.
paper_vs_project.html Comparison Guide 3–4 mins Line-by-line comparison between the original ASPLOS '22 paper (Scarab simulator, Skylake baseline, offline profiling, binary prefix) and our ChampSim runtime implementation.
fundamentals_and_design.html Technical Reference 4–5 mins Out-of-order processor fundamentals (pipeline stages, ROB, RAW/WAR/WAW, ILP, IPC metrics), core design decisions, key challenges faced & how we overcame them (dynamic critical load detection), and limitations.

🏗️ System Architecture & Subsystem Pillars

Pipeline Stage Implementation Location Mechanism Systems Benefit
Dispatch dispatch_instruction() last_writer[] tracking & proactive tagging Records producer-consumer register relationships and tags known critical PCs immediately upon entering the ROB.
Retire retire_rob() Latency calculation & adaptive thresholding Measures full memory latency (retire - dispatch) and detects delinquent loads using an exponential moving average.
Slice Building build_slice_and_mark_critical() Bounded backward BFS (depth ≤ 32) Traverses predecessor instruction IDs to mark all instructions computing the memory address as critical.
Execute execute_instruction() Two-tier priority queue with ROB-head guarantee Issues critical instructions first while ensuring the ROB head always makes forward progress to prevent starvation or deadlock.

📊 Benchmark Results (25M Instruction Traces)

Evaluated on ChampSim single-core out-of-order CPU with a 256-entry ROB, multi-level caches (L1I, L1D, L2C, LLC), and a cycle-accurate DRAM timing controller:

Benchmark Workload Description Baseline IPC CRISP IPC IPC Speedup
LimitOrderBook Financial matching engine using AVL-tree order book 1.184 1.243 +4.98%
ReverseLL Large linked-list reversal pointer-chasing 0.6817 0.6912 +1.39%
BFS Breadth-first search graph traversal 0.1617 0.1636 +1.18%
Exchange SPEC CPU 2017 benchmark suite 1.312 1.325 +0.99%
SSSP GAP benchmark Single-Source Shortest Path 0.2207 0.2211 +0.18%

💡 Key Architectural Insights