Overview: How the CPU walks backward through recorded register dependencies to extract the critical slice, why a bounded Breadth-First Search keeps overhead minimal, and how delinquent PCs are cached for proactive acceleration.
| Subsystem Component | Function / Structure | Mechanics | Systems Benefit |
|---|---|---|---|
| Slice Builder | build_slice_and_mark_critical() |
Runs backward Breadth-First Search starting from the delinquent load. | Discovers all ancestor instructions that compute the memory address. |
| Search Depth Bound | MAX_SLICE_DEPTH = 32 |
Caps BFS traversal to a maximum of 32 dependency levels. | Guarantees $O(1)$ worst-case search complexity, eliminating runtime overhead. |
| Critical Instruction Tag | is_critical = true |
Sets boolean flag on predecessor instructions in the active ROB. | Signals the execution scheduler to prioritize these instructions immediately. |
| Delinquent PC Table | critical_pc_table |
Hash set storing the Program Counter of the delinquent load. | Enables proactive tagging on future instances of the same load instruction. |
"Once a load is detected as slow at retirement, we need to find the instructions that calculated its memory address. This chain of instructions is called the critical slice.
I implemented slice construction using a backward Breadth-First Search (BFS) inside build_slice_and_mark_critical().
Starting at the delinquent load, the algorithm looks up the predecessor instruction IDs that were recorded at dispatch time. For each predecessor currently in the processor's active window, it marks the instruction as is_critical = true, and then enqueues that predecessor's own parent instructions.
To ensure the search remains lightweight and never stalls the processor, I enforced a strict depth bound of 32 instructions. In practice, typical address calculations in pointer-chasing programs are only 5 to 15 instructions deep. Capping the search at 32 captures the complete address calculation while guaranteeing the algorithm runs in constant, bounded time.
Finally, we save the delinquent load's Program Counter into critical_pc_table. The next time that same load instruction appears at dispatch, the CPU recognizes it immediately and marks it critical right away, without waiting for another cache miss."
In a pointer-chasing program (such as traversing a binary search tree: node = node->right), the address of the next node is computed through a short chain of operations:
Instruction 1: Base Pointer Load (LOAD [R_curr] -> R_base)
│
▼
Instruction 2: Offset Calculation (ADD R_base, 8 -> R_addr)
│
▼
Instruction 3: Delinquent Load (LOAD [R_addr] -> R_next) <-- HITS DRAM! (200+ cycles)
Instructions 1 and 2 form the critical slice for Instruction 3. If the processor delays Instructions 1 and 2, Instruction 3 cannot even begin its memory request. But if Instructions 1 and 2 are prioritized, Instruction 3 can issue to DRAM dozens of cycles earlier!
When build_slice_and_mark_critical() is invoked:
Queue Q = [delinquent_load_id]
Depth counter = 0
While Q is not empty and Depth < 32:
Pop current_id from Q
Look up instruction pointer in recent_instrs[current_id]
If instruction exists in active window:
Mark instr->is_critical = true
For each predecessor in instr->pred_instr_ids:
If predecessor not visited:
Enqueue predecessor into Q
Increment Depth
Answer: "If an ancestor instruction has already retired, it has already been removed from the Reorder Buffer and from recent_instrs. When the BFS looks it up, the map lookup returns null, so the search terminates naturally along that branch. This is completely safe: an instruction that has already retired has finished execution, so it no longer needs scheduling priority."
Answer: "BFS explores dependencies level by level, starting with the immediate parents that directly feed the delinquent load. This ensures that the most immediate address producers are prioritized first before exploring deeper, indirect ancestors. It also makes depth bounding simple to enforce."
Answer: "No. Slicing only changes internal instruction metadata (is_critical = true) used by the issue scheduler. It does not alter register values, memory addresses, or instruction order at retirement. Program correctness is completely preserved."