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.
The primary architectural difference lies in how criticality is discovered and communicated to the processor:
critical_pc_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 |
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.
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.
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.