CRISP: critical slice prefetching

Hardware prefetchers cannot predict pointer chases, and out-of-order schedulers pick the oldest ready instruction — so a linked-list load that will miss all the way to DRAM waits politely behind a pile of uncritical vector work it could have overlapped — CRISP fixes this with a division of labor where software does everything expensive offline (find the delinquent loads with profiling counters, extract their address-generating slices from execution traces including dependencies through memory, trim each slice to its critical path) and marks the survivors with a one-byte instruction prefix, so hardware needs only one priority bit per scheduler slot and a multiplexer to execute critical slices as early as possible — hiding miss latency for 8.4% average and up to 38% IPC gains with essentially zero new hardware state.

Why this problem is worth solving

The gap between processor and memory speed is the oldest tax in computer architecture, and

That hand-inserted prefetch is the tell. The knowledge needed to fix this —

What people did before, and where it broke

• Hardware prefetchers (deployed everywhere). Stride, stream, and best-offset designs cover regular patterns — the evaluation runs a best-offset prefetcher in every baseline precisely so CRISP’s gains are only what prefetchers cannot do. Irregular-pattern prefetchers and runahead variants exist on paper; their learning tables, redundant execution, or extra cores have kept them out of real designs.
• Load-slice architectures (IBDA), Long Term Parking, Delay and Bypass. Criticality in hardware — but aimed at in-order cores and energy (sacrificing 5–10% performance), with iterative backwards dependency analysis that only follows register dependencies. On x86, addresses routinely pass through stack memory; those slices come out broken. Reimplemented on an OOO core here, IBDA gains 4.3% where CRISP gains 8.4% — and on several benchmarks IBDA lands below baseline by promoting whole slices without critical-path trimming.
• Compiler hoisting / software prefetching. LLVM hoists loop-invariant loads, and PGO-gated hoisting exists because even that can backfire (moving work into hot blocks). But loop-carried loads — the pointer chase itself — cannot move across iterations without changing semantics. CRISP instead rides hardware speculation: early-executed slices from a mispredicted path are squashed by the machinery that already exists.
• Oldest-first scheduling itself. Instruction scheduling is NP-hard; at gigahertz frequencies, real pickers use oldest-ready-first via age matrices. Criticality never enters — not because it would not help, but because computing it in-cycle is infeasible. That is the exact gap CRISP fills from outside.

How CRISP works

The idea

Criticality is knowledge, and knowledge has a natural home. The scheduler cannot compute criticality (NP-hard, nanosecond budget); the compiler cannot act on it (no reordering across iterations); hardware slice extractors can afford neither the profiling data nor the storage. CRISP notices the analysis is offline-computable — miss ratios from counters, slices from traces, critical paths from DAGs — and that the runtime action it implies is trivially cheap: prefer this instruction. The entire hardware delta is one bit per queue slot, one AND level, one multiplexer, grafted onto the age-matrix picker that shipping processors already use. Everything hard rides the feedback-driven-optimization pipeline that datacenters (Google, Meta) already operate for code layout — CRISP just gives that pipeline a microarchitectural output channel.

“Prefetching” instructions, not data. CRISP never predicts an address and never fetches a byte early — cache miss counts are unchanged. What it prefetches is execution: the critical load of iteration N+1 issues while iteration N’s vector work fills the machine, so the DRAM miss overlaps computation instead of serializing behind it. This is why it succeeds exactly where address-predicting prefetchers give up — a pointer chase’s address is unpredictable, but the instructions that compute it are right there in the window, merely mis-scheduled. The gains show up not as MPKI reduction but as the disappearance of cycles instructions spend stalled at the head of the reorder buffer.

Trim to the critical path, or drown. The subtlest failure mode is promoting too much: a slice of thousands of instructions tagged wholesale fills the reservation station with “critical” work, and priority becomes meaningless — IBDA lands below baseline on three benchmarks for exactly this reason. CRISP’s DAG-based trimming, and its 5–40% critical ratio target, encode a scheduling truth: prioritization is a relative resource, spent only when a deprioritizable mass exists. Even the definition of a critical load is relative — bwaves’ highest-missing loads are not critical, because they miss in phases of high memory-level parallelism where the latency is already overlapped. Only profiling can see that.

The pointer chase, rescued

the pathology is the SCHEDULER, not the window size
compilers cannot make this move: it crosses a loop iteration

Why it works

• The critical load’s instructions are already in the window; only the picking order is wrong → a one-bit priority channel from software to scheduler fixes ordering without new prediction, storage, or redundant execution → overlap is recovered at the cost of a prefix byte.
• Criticality depends on offline-only knowledge (execution frequency, miss ratios, MLP phases, critical-path lengths) → software profiling computes what no in-cycle hardware heuristic can, and cross-input evaluation (profile on train, run on ref) shows the tags generalize.
• Trace-based extraction sees dependencies through memory → slices survive x86 register spills that break register-only hardware analysis → higher coverage and accuracy (namd, Xhpcg flip from missed to captured).
• Critical-path trimming keeps the critical fraction at 5–40% → the reservation station retains a deprioritizable mass, so priority stays meaningful → exactly where untrimmed IBDA falls below baseline.
• Early-resolved branch slices keep the speculative frontend filling the window → load-slice prioritization has material to reorder → the two techniques compound (lbm’s load-slice gains appear only once branches resolve early).
• Wrong-path early execution is squashed by existing speculation machinery → correctness is free, unlike compiler reordering which must be conservative.

What it costs

• A profiling pipeline. CRISP presumes the trace-profile-rewrite-redeploy loop of datacenter FDO (AutoFDO/BOLT lineage). Without that infrastructure — most desktop and mobile software — the technique has no delivery vehicle.
• An ISA change. A new instruction prefix must be decoded and carried through the pipeline; binaries using it are tied to supporting hardware (though a prefix-ignorant CPU could treat it as a NOP-class hint).
• Code footprint. One byte per critical instruction lands in the hottest loops: +5.2% dynamic footprint, up to +2.6% icache MPKI — real, if small, pressure on the frontend.
• Threshold tuning. The miss-ratio cutoff matters (1% of total misses is best overall, but Moses prefers 2%), and the authors envision iterative per-application profiling — more pipeline complexity.
• Simulation evidence. Gains are from a cycle-accurate model of a Skylake-like core; the real-hardware data point is the motivating microbenchmark, not the full suite.
• Mild SMT side channel. Priority usage could leak an application’s criticality signature to a co-resident thread — judged less severe than known SMT leaks, with the same mitigations.

The evaluation

Cycle-accurate simulation (Scarab, Skylake-parameterized) against a strong baseline — best-offset data prefetching and FDIP instruction prefetching enabled everywhere — plus a faithful IBDA reimplementation with generous variants (up to infinite slice tables). Profiling and evaluation use different inputs, so the tags must generalize.

Check yourself

Sources

• ACM DL: CRISP: Critical Slice Prefetching — ASPLOS 2022 (open access)