Overview: Detailed evaluation of CRISP across five 25-million instruction traces in ChampSim, analyzing why structured pointer-chasing in Limit Order Book achieves a ~5% speedup while irregular graphs show lower gains.
| Benchmark Trace | Workload Domain | Baseline IPC | CRISP IPC | IPC Speedup | Primary Bottleneck Behavior |
|---|---|---|---|---|---|
| LimitOrderBook | Financial Trading (AVL Tree) | 1.184 | 1.243 | +4.98% | Predictable, repetitive pointer chasing through tree nodes. |
| ReverseLL | Data Structures (Linked List) | 0.6817 | 0.6912 | +1.39% | Direct linear pointer chasing (curr = curr->next). |
| BFS | Graph Algorithm (Breadth-First) | 0.1617 | 0.1636 | +1.18% | Queue-based frontier exploration with moderate locality. |
| Exchange | SPEC CPU 2017 Benchmark | 1.312 | 1.325 | +0.99% | General-purpose compute with intermittent memory stalls. |
| SSSP | GAP Benchmark (Shortest Path) | 0.2207 | 0.2211 | +0.18% | Highly irregular, random memory access based on graph edge weights. |
"We evaluated CRISP on five benchmark workloads, each running 25 million instructions on our ChampSim out-of-order processor configuration.
Our key finding was that CRISP's performance depends heavily on the structure of the memory access pattern.
The largest improvement occurred on the Limit Order Book matching engine, where Instructions Per Cycle (IPC) increased by 4.98%. A Limit Order Book uses an AVL tree to organize buy and sell orders by price. Every time an order is inserted or matched, the processor walks down the tree following left and right child pointers. These critical slices are short—about 5 to 10 instructions—and they repeat frequently. Once CRISP identifies the delinquent load PC, it proactively marks and prioritizes the address calculation on every tree step.
We saw similar positive gains on Reverse Linked List (+1.39%) and Graph BFS (+1.18%), where pointer-chasing chains also delay the next iteration.
On the other hand, the Single-Source Shortest Path (SSSP) benchmark showed only a modest 0.18% improvement. SSSP traverses irregular, weighted graphs where neighbor node connections change unpredictably on every iteration. Because the memory access pattern is quasi-random, the critical slices do not repeat consistently, making past learning less effective.
This evaluation clearly demonstrates that critical-slice scheduling is especially powerful for applications with structured, repetitive pointer-chasing—such as financial matching engines and database index traversals."
An AVL-tree order book represents the sweet spot for criticality-based scheduling:
Order Book Matching Loop:
While node != NULL:
Compare price ──► If lower, follow node->left; If higher, follow node->right
│
▼
Characteristics of this loop:
1. Short Slices: Only 5 to 10 assembly instructions per tree level.
2. High Repetition: The same loop body runs millions of times per second.
3. Stable PCs: The exact same load instruction causes the DRAM miss over and over.
Because the load PC is stable, the critical_pc_table hits on almost every order insertion, enabling proactive marking right at dispatch without waiting to measure latency again.
In graph algorithms like SSSP (Dijkstra's algorithm):
Answer: "No. All five benchmarks showed positive IPC improvements, ranging from +0.18% up to +4.98%. This proves that our three-step scheduling policy with the ROB-head liveness guarantee successfully prevents starvation and avoids delaying non-critical execution paths."
Answer: "Cycle-accurate microarchitecture simulation is compute-intensive, requiring billions of simulated CPU clock cycles. A 25-million instruction execution window provides a statistically significant, representative slice of the workload's core loops—including initial cache warmup and steady-state memory behavior—while allowing rapid experimentation and comparison across configurations."
Answer: "Any system dominated by pointer chasing: in-memory key-value databases using B-trees or Radix trees (like Redis and RocksDB), database index scanners (PostgreSQL B-tree lookups), and graph database query engines. These systems suffer from memory latency that cannot be hidden by standard stride prefetchers."