Topic 02: Register Dependency Tracking at Dispatch

Overview: How the CPU records producer-consumer register relationships as instructions enter the pipeline, why backward tracking avoids broadcast overhead, and how proactive PC tagging speeds up critical loads.


1. High-Level Summary

Data Structure / Component Where It Lives What It Stores Systems Benefit
last_writer[] inc/ooo_cpu.h Array mapping each register to the instruction ID that last wrote it. Enables instant $O(1)$ lookup of producer instructions without scanning previous code.
pred_instr_ids[] inc/instruction.h Array inside each instruction storing up to 2 predecessor instruction IDs. Records backward dependency links for later slice construction.
recent_instrs inc/ooo_cpu.h Hash map linking instruction IDs to active ROB pointers. Allows fast BFS traversal across in-flight instructions during slice extraction.
critical_pc_table inc/ooo_cpu.h Hash set storing Program Counters of known delinquent loads. Enables proactive tagging: marks instructions critical immediately at dispatch.

2. Spoken Interview Answer (Simple & Direct)

"To prioritize the instructions that feed a slow load, the processor has to know which earlier instructions produced its input registers.

I implemented this dependency tracking in the dispatch stage (dispatch_instruction()). Dispatch is the ideal place because this is where physical registers are renamed, unique instruction IDs are assigned, and register dependencies are fully known.

Instead of building a complex forward dependency graph—which would require broadcasting updates to all future instructions—I used backward dependency tracking. I maintain a simple table called last_writer[]. Whenever an instruction writes to a destination register, we record that instruction's unique ID in the table.

When a new instruction passes through dispatch, it checks last_writer[] for its source registers. It records up to two predecessor IDs directly into its own metadata. This creates a lightweight chain of backward pointers using only $O(1)$ constant-time lookups per instruction.

At the same time, we check our critical_pc_table. If this instruction's Program Counter was identified as critical during a previous execution, we proactively mark it as critical right away. This means we don't have to wait for the load to become slow again—the processor prioritizes it immediately."


3. Architecture & Mechanics

3.1 Backward vs. Forward Dependency Tracking

There are two theoretical ways to track instruction dependencies in hardware:

Forward Tracking (Expensive):
Instruction A writes R1 ──► Must broadcast to ALL future instructions: "Listen to me!"
                            Requires complex listener queues or associative search.

Backward Tracking in CRISP (Lightweight & O(1)):
Instruction B reads R1  ──► Looks up last_writer[R1] in 1 step!
                            Finds Instruction A immediately. No broadcast needed.

3.2 How last_writer[] Builds the Chain

Consider a simple pointer-chasing sequence where a load computes an offset from an earlier base pointer:

Instruction 101: ADD R1, R2 -> R3    (last_writer[R3] = 101)
Instruction 102: MOV R4, 16 -> R5    (last_writer[R5] = 102)
Instruction 103: LOAD [R3 + R5] -> R7
                 │
                 ├── Reads source R3: last_writer[R3] == 101 -> pred_instr_ids[0] = 101
                 └── Reads source R5: last_writer[R5] == 102 -> pred_instr_ids[1] = 102

With just two array lookups, Instruction 103 now has direct backward pointers to the exact instructions that calculated its memory address.

3.3 Proactive Marking via critical_pc_table

The first time a delinquent load executes, it is discovered reactively after taking 200+ cycles to access DRAM. But once that load's Program Counter (PC) is known, repeating the same delay in the future is wasteful.

At dispatch, every incoming instruction checks:

if (critical_pc_table.count(instr.ip)) {
    instr.is_critical = true;
}

This allows the processor to prioritize recurring delinquent loads and their slices before they experience a cache miss, cutting latency proactively.


4. Common Interview Questions

Q1: Why do you track at most 2 predecessor IDs per instruction?

Answer: "On modern architectures like x86 and ARM, virtually all ALU and memory instructions use at most two source registers (for example, base + index in address calculation: [R1 + R2*4]). Capping predecessor storage at 2 covers nearly 100% of practical address-generation instructions while keeping per-instruction metadata fixed in size and avoiding dynamic memory allocation."

Q2: Why not track memory dependencies (stores forwarding to loads) as well?

Answer: "Tracking memory dependencies at runtime requires dynamic store-to-load forwarding tracking in the Load-Store Queue (LSQ). Stores often compute their addresses late, which can introduce false dependencies or ambiguity. Register dependencies, by contrast, are 100% deterministic at dispatch after register renaming. Register tracking captured the dominant address-computation chains in our workloads with minimal overhead."

Q3: When are instructions removed from recent_instrs?

Answer: "Instructions are removed from recent_instrs strictly at retirement. They must remain in the map while in-flight so that any backward BFS can reach them. Once an instruction retires from the ROB, its execution has finished and its resources are freed, so its pointer in recent_instrs is erased to prevent dangling references."