Topic 04: Backward Slice Construction via Bounded BFS

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.


1. High-Level Summary

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.

2. Spoken Interview Answer (Simple & Direct)

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


3. Architecture & Mechanics

3.1 What Does a Critical Slice Look Like?

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!

3.2 The Backward BFS Traversal Algorithm

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

3.3 Why Bounding Depth to 32 is Safe and Fast


4. Common Interview Questions

Q1: What happens if an ancestor instruction has already retired before the BFS runs?

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

Q2: Why use Breadth-First Search (BFS) instead of Depth-First Search (DFS)?

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

Q3: Does marking instructions as critical change program output?

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