CRISP: Original ASPLOS Paper vs. Our Implementation

Overview: A direct, side-by-side comparison between the original research paper ("CRISP: Critical Slice Prefetching", ASPLOS '22 by Litz, Ayers, and Ranganathan from UC Santa Cruz & Google) and our ChampSim simulator implementation.


1. Executive Summary: What is the Same vs. What is Different?

💡 The Core Shared Insight (What is Identical):
Both the original paper and our project target the same fundamental memory wall problem: irregular, delinquent memory loads that miss the cache hierarchy stall out-of-order processors. Instead of trying to guess future memory addresses speculatively (which fails on pointer-chasing code), both approaches extract the critical slice—the backward dependency chain of instructions that computes the load's address—and execute those instructions earlier in the CPU scheduler.

The primary architectural difference lies in how criticality is discovered and communicated to the processor:


2. Comprehensive Comparison Table

Component / Dimension CRISP Research Paper (ASPLOS '22) Our Implementation (ChampSim)
Main Goal Hide latency of irregular / delinquent loads Same — Hide memory latency by calculating addresses earlier
Basic Idea Execute critical load / slice early Same — Prioritize critical slice instructions during OoO issue
Conventional Address Prediction No — does not guess speculative addresses No — executes real program slice instructions earlier
Critical Load Detection Offline profiling using PMU hardware performance counters on training inputs Runtime latency detection measuring actual cycle latency at retirement
Criticality Metrics LLC miss rate, memory-level parallelism (MLP), execution ratio, instruction stall cycles Simulated memory latency (retire - dispatch) evaluated against an adaptive exponential moving average threshold
Load Slice Identification Yes — extracts backward slice Yes — extracts backward dependency slice
Dependency Tracking Register dependencies + memory dependencies (load-store forwarding) Primarily register dependencies tracked via last_writer[] table at dispatch
Trace-Based Analysis Yes — utilizes offline execution traces to analyze critical paths No — operates purely online on in-flight instructions
Critical-Path Analysis Yes — trims slice to only instructions on the longest critical path No — marks all backward-reachable predecessor instructions up to max depth
Slice Marking Scope Only the critical path within the slice is prioritized Entire backward slice (all reachable ancestor instructions in active window)
Persistent Knowledge Binary annotation via modified machine code critical_pc_table runtime hash table caching delinquent load PCs
Binary Instruction Prefix Yes — introduces a new x86 instruction prefix byte decoded in hardware No — instructions tagged dynamically inside simulator structures
Branch Slices Yes — extends slicing to prioritize branches that cause frequent mispredictions No — focuses strictly on delinquent memory load slices
Scheduler Design Age-matrix or RAND picker extended with PRIO bit logic ChampSim ROB scan with two-tier issue queue: ready_criticals before ready_non_criticals
Hardware Scheduler Modeling Detailed gate-level circuit evaluation (critical path latency, multiplexer overhead) Simplified software model in ChampSim core execution loop
Hardware Instruction Prefix Yes — adds prefix byte to decode stage No — tags instruction object directly in memory
Simulator Used Scarab (execution-driven cycle-accurate simulator) + Ramulator ChampSim (trace-driven cycle-accurate microarchitecture simulator)
Simulated Baseline Architecture Intel Xeon Skylake-like core:
• 6-way fetch/decode/retire
• 224-entry ROB, 96-entry Reservation Station
• TAGE branch predictor
• BOP (Best-Offset) & Stream prefetchers
• Multi-level cache + Ramulator DRAM
Single-core OoO CPU:
• 4-way dispatch / 6-way execution
• 256-entry ROB, private LSQ
• Multi-level caches (L1I, L1D, L2C, LLC)
• Cycle-accurate DRAM timing controller
Evaluated Workloads SPEC CPU 2017, XHPCG, Tailbench (Moses, Memcached, Img-dnn) 5 diverse traces (25M instructions each):
• LimitOrderBook (AVL Tree, +4.98%)
• ReverseLL (Linked List, +1.39%)
• BFS (Graph Traversal, +1.18%)
• Exchange (SPEC 2017, +0.99%)
• SSSP (GAP Benchmark, +0.18%)
Cache Modifications Not part of CRISP (standard cache hierarchy retained) Exploratory: Experimented with an exclusive cache hierarchy alongside scheduling
Runtime Adaptation Not central (static offline annotations guide execution) Yes — dynamic EMA threshold continuously adapts to workload memory phases
Dynamic Learning No (requires offline profiling pass on training inputs) Yes — learns delinquent loads and critical PCs on the fly during single-pass execution

3. Deep-Dive: Key Architectural Differences Explained

3.1 Offline Profiling + Binary Prefix vs. Online Dynamic Learning

In the CRISP paper, the authors aimed for zero hardware overhead for learning. They ran the program once under a hardware performance monitor (PMU) to find instructions with high LLC miss rates and stall cycles. Then, a compiler tool re-encoded the executable binary, adding a special 1-byte prefix to critical instructions. When the CPU decodes these instructions, it sets a PRIO flag in the reservation station.

In our project, we wanted to see if the core could learn critical instructions completely on the fly without needing offline profiling or re-compiling binaries. We implemented dynamic latency measurement at retirement, an adaptive moving-average threshold, and an in-memory critical_pc_table. When a load misses in cache and takes a long time, the CPU automatically discovers the slice and prioritizes future instances of that PC.

3.2 Full Slice BFS vs. Critical-Path Trimming

When an address is calculated, multiple instructions may contribute (for example, computing an array offset and loading a base pointer). The paper performs an offline dataflow analysis to find which dependency sub-path has the longest latency, marking only those specific instructions to avoid overcrowding the scheduler.

In our runtime implementation, performing full critical-path graph analysis at microsecond timescales inside a CPU would be too expensive. Instead, we run a bounded Breadth-First Search (BFS) capped at depth 32. This captures all reachable predecessor instructions that produce source registers for the load, ensuring the entire address calculation is accelerated.

3.3 The Liveness & Deadlock Challenge

Both systems recognized that simply prioritizing critical instructions can cause starvation: if non-critical instructions at the head of the ROB never get issued, the ROB can never retire, and the entire CPU hangs in a deadlock.


4. Top Interview Questions on Paper vs. Project

🎯 Q1: “Why did the paper use offline binary rewriting, while you built online dynamic detection?”
“The paper's philosophy was to keep hardware modifications strictly minimal—they didn't want extra hardware tables or BFS circuits on the chip, so they offloaded slice detection to an offline compiler pass and inserted an x86 instruction prefix. In my project, I wanted to explore whether an out-of-order processor could achieve similar benefits autonomously at runtime without requiring developers to profile and recompile their binaries. I built an adaptive moving-average threshold and an in-flight BFS slice builder that learns critical loads on the fly.”
🎯 Q2: “How does the paper's simulated processor compare to your ChampSim setup?”
“The paper evaluated their system using the Scarab simulator modeled after an Intel Xeon Skylake server processor (6-way fetch/retire, 224-entry ROB, 96-entry unified reservation station, TAGE branch predictor, and BOP prefetcher). In my implementation, I used ChampSim with a modern out-of-order core configuration featuring a 256-entry ROB, private LSQ, multi-level caches, and cycle-accurate DRAM timing.”
🎯 Q3: “What were the key workload differences and results?”
“The paper evaluated memory-intensive benchmarks from SPEC2017, XHPCG, and data-center workloads from Tailbench (Moses, Memcached, Img-dnn), observing average IPC improvements of 8.4% and up to 38% on pointer-chasing microbenchmarks. In our project, we focused on five 25M-instruction traces including a real-world Limit Order Book matching engine. We observed the strongest gain on the Limit Order Book (+4.98%), demonstrating that AVL-tree pointer chasing in financial applications provides predictable critical slices ideal for this technique.”