Topic 06: Benchmark Evaluation & Workload Sensitivity Analysis

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.


1. High-Level Summary Table

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.

2. Spoken Interview Answer (Simple & Direct)

"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."


3. Architecture & Mechanics

3.1 Why Limit Order Book is the Ideal Workload for CRISP

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.

3.2 Why SSSP Shows Lower Gains

In graph algorithms like SSSP (Dijkstra's algorithm):


4. Common Interview Questions

Q1: Did CRISP cause any performance degradation on any benchmark?

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."

Q2: Why did you test on 25-million instruction traces?

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."

Q3: What other real-world systems would benefit from CRISP?

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."