Module III: Instruction-Level Parallelism (ILP)

Instruction-Level Parallelism (ILP) refers to the potential for simultaneous execution of multiple instructions within a single processor. It measures how many operations in a program's instruction stream are truly independent and can, in theory, be executed at the same time.

Key Concepts:

• Independence: Two instructions can execute in parallel only if neither depends on the result of the other. The degree of ILP is determined by the density of independent instructions in the code.
• Exploitation Methods: ILP can be exploited through hardware techniques (Superscalar processors, Out-of-Order execution) or software techniques (compiler reordering, loop unrolling, VLIW scheduling).
• Ideal vs. Practical ILP: Studies have shown that typical programs contain an average ILP of 3-7 independent instructions at any point (with perfect branch prediction and infinite resources). Practical processors extract ILP of 1.5-4 due to hardware limitations and imperfect predictions.

Why ILP Matters:

Increasing clock frequency has hit a power wall (~2005). ILP is one of the key architectural approaches to improve performance without increasing frequency — by doing more useful work per clock cycle. This is quantified as IPC (Instructions Per Cycle). A superscalar processor achieving IPC > 1 is exploiting ILP.

Static and Dynamic ILP refer to who is responsible for discovering and scheduling independent instructions — the compiler (software) or the processor hardware.

These are the three types of data dependencies between instructions. They define the limits of ILP because dependent instructions cannot execute simultaneously.

1. RAW — Read After Write (True Dependency):

• Scenario: Instruction J tries to read a register that Instruction I has not yet written to.
• Example:
  I: ADD R1, R2, R3 (writes to R1)
  J: SUB R4, R1, R5 (reads R1)
• Nature: This is a true data dependency. J genuinely needs the result produced by I. It CANNOT be eliminated by any renaming trick.
• Impact on ILP: J must wait until I produces R1's value. This serializes the instructions.

2. WAR — Write After Read (Anti-Dependency):

• Scenario: Instruction J tries to write to a register that Instruction I has not yet finished reading.
• Example:
  I: SUB R4, R1, R5 (reads R1)
  J: ADD R1, R2, R3 (writes to R1)
• Nature: This is a false dependency (name dependency). There is no actual data flow from I to J. The conflict arises only because both happen to use the same register name R1.
• Resolution: Register Renaming can eliminate WAR. Rename J's destination to a different physical register (e.g., R1' = R2 + R3), allowing J to execute freely alongside I.

3. WAW — Write After Write (Output Dependency):

• Scenario: Instruction J tries to write to the same register that Instruction I also writes to.
• Example:
  I: ADD R1, R2, R3 (writes to R1)
  J: MUL R1, R4, R5 (also writes to R1)
• Nature: Another false dependency. The final value of R1 must be J's result. If J completes before I (in out-of-order execution), I's stale result would incorrectly overwrite J's.
• Resolution: Register Renaming eliminates WAW. Map each write to a unique physical register. The commit logic ensures the correct final value is visible.

The compiler plays a critical role in exposing and organizing ILP for the hardware to exploit. Even in superscalar processors with dynamic scheduling, compiler optimizations significantly boost performance.

Key Compiler Techniques:

1. Instruction Scheduling (Code Reordering): The compiler analyzes data dependencies and reorders independent instructions to fill pipeline slots that would otherwise be wasted as stalls. For example, it moves an independent LOAD instruction before a dependent ADD to hide the memory access latency.
2. Loop Unrolling: The compiler duplicates the loop body multiple times and adjusts the loop counter. This removes branch overhead and, more importantly, exposes independent instructions from different original iterations that the hardware can execute in parallel.
3. Software Pipelining: An advanced technique where the compiler interleaves instructions from different loop iterations into a single iteration body. This creates a "pipeline" of iterations at the instruction level, maximizing functional unit utilization.
4. Register Allocation: Efficient register allocation reduces spills to memory. More values held in registers means fewer slow Load/Store operations and more opportunities for the hardware to find ILP.
5. Trace Scheduling: The compiler identifies the most frequently executed paths through the program (traces) and optimizes those paths aggressively by reordering instructions across basic block boundaries and branch points.

Significance: Without compiler optimization, even the most advanced superscalar hardware would find far fewer independent instructions to execute in parallel. The compiler's global view of the program enables optimizations that localized hardware logic cannot achieve.

Despite decades of architectural innovation, extracting more ILP from programs faces several fundamental limits:

1. True Data Dependencies (RAW): These cannot be eliminated by any hardware or software technique. If instruction B needs the result of instruction A, B must wait. The critical path of data dependencies defines the theoretical maximum ILP of any program.
2. Control Dependencies (Branches): Programs contain 15-25% branch instructions. Each branch creates uncertainty about which instructions to execute next. Even with 97% prediction accuracy, a 3% misprediction rate causes significant pipeline flushes in deep pipelines, wasting many cycles of speculative work.
3. Memory Latency (Cache Misses): An L1 cache miss stalls the dependent instruction chain for 10-15 cycles (L2 hit) or 100+ cycles (DRAM access). This latency is nearly impossible to hide if subsequent instructions depend on the loaded data.
4. Finite Hardware Resources: The processor has a limited number of ALUs, load/store units, and physical registers. Even if 10 independent instructions exist, if the processor only has 4 ALUs, only 4 can execute per cycle.
5. Power and Complexity Wall: Out-of-order logic (Reorder Buffers, Reservation Stations, Register Rename tables) consumes enormous chip area and power. The energy cost of the ILP extraction logic can exceed the energy cost of the actual computation. Diminishing returns set in rapidly beyond 4-6 wide issue.
6. Window Size Limitation: The hardware can only "see" a limited number of instructions ahead (the instruction window, typically 128-300 instructions). ILP opportunities beyond this window are invisible to the hardware.

Loop unrolling is a compiler optimization technique that replicates the body of a loop multiple times within a single iteration and adjusts the loop control accordingly. Its primary purpose is to expose more ILP and reduce loop overhead.

Before Unrolling (Original Loop):

for (i = 0; i < 100; i++) {
    A[i] = A[i] + B[i];
}
    

Each iteration has: 1 load A[i], 1 load B[i], 1 add, 1 store A[i], 1 branch (loop test). That's 5 instructions, with the branch consuming 20% of the work.

After Unrolling by Factor 4:

for (i = 0; i < 100; i += 4) {
    A[i]   = A[i]   + B[i];
    A[i+1] = A[i+1] + B[i+1];
    A[i+2] = A[i+2] + B[i+2];
    A[i+3] = A[i+3] + B[i+3];
}
    

Now each iteration has: 4 loads A, 4 loads B, 4 adds, 4 stores, 1 branch = 17 instructions. The branch now consumes only ~6% of the work.

Benefits:

1. Reduced Branch Overhead: The loop executes 25 iterations (instead of 100), reducing the number of branch instructions and associated prediction penalties by 75%.
2. Exposed ILP: The 4 add operations in the unrolled body are completely independent of each other (they access different array elements). A superscalar processor can issue all 4 adds simultaneously if it has enough ALUs.
3. Better Register Utilization: The compiler can now schedule loads early and keep values in registers longer, hiding memory latency.

Drawback: Increased code size (instruction cache pressure). If unrolled too aggressively, the larger loop body may not fit in the I-Cache, causing instruction cache misses.

A Superscalar processor is a CPU that can issue and execute more than one instruction per clock cycle by having multiple parallel execution pipelines (functional units).

Architecture:

• A superscalar processor with an issue width of N can fetch, decode, and dispatch up to N instructions per clock cycle.
• It contains multiple functional units: e.g., 2 integer ALUs, 2 FP units, 2 Load/Store units, 1 Branch unit.

How ILP is Achieved (Step-by-Step):

1. Fetch Multiple Instructions: The front-end fetches N instructions from the I-Cache per cycle (e.g., 4-6 instructions on modern CPUs).
2. Decode & Rename: The decoder checks for dependencies. The Register Renaming unit maps architectural registers to a larger pool of physical registers, eliminating WAR and WAW false dependencies.
3. Dynamic Scheduling (Dispatch to Reservation Stations): Decoded instructions are placed into Reservation Stations in front of each functional unit. Instructions wait here until all their operands are available.
4. Out-of-Order Issue: As soon as an instruction in any Reservation Station has all its operands ready, it is issued to the corresponding functional unit for execution, regardless of program order.
5. Execute in Parallel: Multiple functional units operate simultaneously, executing independent instructions in the same clock cycle.
6. In-Order Commit (via ROB): Completed results are held in the Reorder Buffer. Instructions are committed (results written to architectural state) strictly in original program order to maintain correctness and support precise exceptions.

Example: A 4-wide superscalar processor with ideal conditions can retire up to 4 instructions per cycle, achieving an IPC (Instructions Per Cycle) of up to 4.

Out-of-Order (OoO) Execution is a hardware technique where the processor executes instructions in an order determined by the availability of their input data, rather than strictly following the original program order.

Why OoO is Needed:

Consider instructions: I1 (slow cache miss), I2 (depends on I1), I3 (independent of I1 and I2). In an in-order processor, I3 is blocked behind I2, which is blocked behind I1. In an OoO processor, I3 can execute immediately while I1 is still waiting for memory.

How OoO Works:

1. In-Order Front-End: Instructions are fetched and decoded in program order.
2. Register Renaming: Architectural registers are mapped to physical registers to eliminate WAR/WAW false dependencies.
3. Dispatch to Reservation Stations: Instructions are dispatched to waiting areas (Reservation Stations) associated with specific functional units.
4. Out-of-Order Issue & Execute: Each clock cycle, the hardware scans the Reservation Stations. Any instruction whose operands are ALL available is issued to its functional unit for execution, bypassing older instructions that are still waiting.
5. In-Order Commit (Retirement): Completed results are buffered in the Reorder Buffer (ROB). The ROB retires instructions strictly in program order, writing their results to the architectural register file. This ensures precise exceptions and correct program behavior.

Relation to ILP: OoO execution is the primary hardware mechanism for exploiting dynamic ILP. By looking ahead through the instruction window and executing independent instructions whenever possible, OoO processors extract significantly more ILP than in-order processors. Modern OoO cores can look at windows of 200-300 instructions to find parallelism.

Tomasulo's Algorithm (developed by Robert Tomasulo at IBM in 1967) is a pioneering hardware scheme for dynamic instruction scheduling that enables out-of-order execution. It was first implemented in the IBM System/360 Model 91 floating-point unit.

Key Hardware Components:

1. Reservation Stations (RS): Buffers in front of each functional unit. Each RS entry holds an instruction, its operands (or tags pointing to the sources that will produce them), and the operation code. Instructions wait here until their data is ready.
2. Common Data Bus (CDB): A broadcast bus. When a functional unit produces a result, it broadcasts the result along with the RS tag on the CDB. All Reservation Stations and the Register File simultaneously listen and capture the value if they were waiting for that tag.
3. Register File with Tags: Instead of just storing values, each register entry can also store a tag indicating which Reservation Station will produce the value. This is Tomasulo's form of register renaming.

Algorithm Steps:

1. Issue: Decode the instruction. If a Reservation Station is free for the required functional unit, issue the instruction into it. Read available operands from the Register File. If an operand is not ready, store the tag of the RS that will produce it.
2. Execute: The RS monitors the CDB. When both operands become available (either from the register file or via CDB broadcast), the instruction is sent to the functional unit for execution.
3. Write Result: When execution completes, the result is broadcast on the CDB. All waiting RSs and register file entries that are expecting this tag capture the value.

How It Achieves ILP:

• Eliminates WAR/WAW: Because operands are copied into Reservation Stations (or captured via CDB), the original register can be overwritten safely. This is an implicit form of register renaming.
• Enables OoO Execution: Instructions execute as soon as their data is available, not necessarily in program order.
• Distributed Scheduling: Each RS independently decides when its instruction is ready, creating a highly parallel scheduling mechanism.

Register Renaming is a hardware technique that maps the limited set of architectural registers (the registers defined by the ISA, e.g., R0-R31) to a much larger pool of hidden physical registers. This eliminates WAR and WAW false dependencies.

The Problem (False Dependencies):

I1: ADD R1, R2, R3   (Writes R1)
I2: SUB R4, R1, R5   (Reads R1 — True RAW dependency on I1)
I3: MUL R1, R6, R7   (Writes R1 — WAW with I1, WAR with I2)
    

I3 cannot execute before I2 reads R1 (WAR). I3 cannot execute before I1 writes R1 (WAW). But I3 doesn't actually need I1's result — it just happens to reuse the name "R1".

The Solution (Register Renaming):

The hardware maintains a Rename Table that maps each architectural register to a physical register. Every instruction that writes to a register gets a new, unique physical register.

I1: ADD P31, P2, P3   (R1 → P31)
I2: SUB P4, P31, P5   (Still reads P31 — RAW preserved)
I3: MUL P32, P6, P7   (R1 → P32, a NEW physical register)
    

Now:

• The WAW between I1 and I3 is gone: they write to P31 and P32 respectively.
• The WAR between I2 and I3 is gone: I2 reads P31 (a fixed snapshot), I3 writes to P32. They can execute in any order or simultaneously.
• The true RAW between I1 and I2 is preserved: I2 still waits for I1 to produce P31.

ILP Impact: By eliminating false dependencies, register renaming dramatically increases the number of instructions that can execute in parallel, unlocking ILP that was hidden by the limited number of architectural register names.

How Pipeline Hazards Restrict ILP:

• Data Hazards (RAW): Create serial chains of dependent instructions that cannot be parallelized. The critical path of RAW dependencies is the fundamental limit on ILP.
• Control Hazards (Branches): At every branch, the processor doesn't know which instructions to execute next. If it guesses wrong, all speculatively executed instructions must be flushed, wasting cycles and energy.
• Structural Hazards: Limited functional units restrict how many independent instructions can execute simultaneously. If there are 6 independent ADD instructions but only 2 ALUs, only 2 can execute per cycle.

Speculative Execution:

Definition: Speculative execution is a technique where the processor predicts the outcome of a branch (using a branch predictor) and begins executing instructions from the predicted path before the branch condition is actually resolved.

How It Contributes to ILP:

1. Eliminates Control Hazard Stalls: Instead of stalling the pipeline waiting for the branch to resolve, the processor keeps the pipeline full by executing predicted instructions.
2. Correct Prediction: If the prediction is correct (~95%+ of the time), the speculative instructions are committed normally. Zero performance loss.
3. Incorrect Prediction: If wrong, the Reorder Buffer discards all speculatively computed results, the pipeline is flushed, and execution restarts from the correct path. This incurs a penalty, but the average benefit across all branches far outweighs the occasional cost.
4. Enabling OoO Past Branches: Without speculation, the OoO window stops at every branch. With speculation, the window extends past multiple branches, finding far more ILP.

The Problem:

Consider a loop where the 4 instructions within a single iteration form a chain of RAW dependencies:

Loop:  LOAD  R1, 0(R2)      ; I1: Load from memory
       ADD   R1, R1, R3     ; I2: Depends on I1 (RAW)
       MUL   R1, R1, R4     ; I3: Depends on I2 (RAW)
       STORE R1, 0(R2)      ; I4: Depends on I3 (RAW)
       ADDI  R2, R2, 4      ; Increment pointer
       BNE   R2, R5, Loop   ; Branch
    

Within a single iteration, I1→I2→I3→I4 is a strict serial chain. The ILP within one iteration is effectively 1 (no parallelism).

The Solution — Unrolling by 4:

Loop:  LOAD  R1,  0(R2)     ; Iteration 1
       LOAD  R6,  4(R2)     ; Iteration 2 (INDEPENDENT of R1)
       LOAD  R7,  8(R2)     ; Iteration 3 (INDEPENDENT)
       LOAD  R8, 12(R2)     ; Iteration 4 (INDEPENDENT)
       ADD   R1, R1, R3     ; Depends on Load 1
       ADD   R6, R6, R3     ; Depends on Load 2 (INDEPENDENT of ADD R1)
       ADD   R7, R7, R3     ; Depends on Load 3 (INDEPENDENT)
       ADD   R8, R8, R3     ; Depends on Load 4 (INDEPENDENT)
       MUL   R1, R1, R4     ; ...and so on
       ...
    

Why This Improves ILP:

• The 4 LOAD instructions are independent (different addresses). A superscalar processor can issue all 4 simultaneously if it has 2 load units.
• The 4 ADD instructions are independent (different registers). They can be issued in parallel.
• While waiting for Load 1's result (memory latency), the processor is doing useful work: executing Loads 2, 3, and 4. Memory latency is hidden.
• Inter-iteration parallelism is now visible within a single iteration body.

General Exam Approach:

1. List all instructions and identify their source and destination registers.
2. Build a dependency graph: For each instruction pair (I, J) where J comes after I, check:
   • RAW: J reads a register that I writes? → True dependency (J must wait for I).
   • WAR: J writes a register that I reads? → Anti-dependency (can be renamed).
   • WAW: J writes a register that I writes? → Output dependency (can be renamed).
3. Determine issue groups: With issue width = 2, pair up instructions that have NO RAW dependency between them.

Example:

I1: ADD  R1, R2, R3    (Writes R1)
I2: SUB  R4, R1, R5    (Reads R1 — RAW on I1)
I3: MUL  R6, R7, R8    (Independent of I1 and I2)
I4: AND  R9, R6, R1    (Reads R6 — RAW on I3, Reads R1 — RAW on I1)
    

Dependency Analysis:

• I2 depends on I1 (RAW via R1) → Cannot issue together.
• I3 is independent of I1 and I2 → Can issue with either.
• I4 depends on I1 (R1) and I3 (R6) → Must wait for both.

Issue Schedule (Width = 2):

Total: 3 cycles for 4 instructions. IPC = 4/3 = 1.33.

Given:

• Issue Width = 4 instructions per clock cycle
• Measured CPI (Cycles Per Instruction) = 1.2

Step 1: Calculate IPC (Instructions Per Cycle)

Step 2: Determine Potential ILP

• The potential ILP of this machine (its maximum theoretical throughput) is equal to its issue width = 4 instructions per cycle.
• This would correspond to a best-case CPI of 1/4 = 0.25.

Step 3: Analyze the Gap

• The machine is achieving only 0.833 IPC out of a possible 4 IPC.
• Utilization = Actual IPC / Maximum IPC = 0.833 / 4 = 20.8%.
• This means approximately 79% of the processor's execution slots are wasted every cycle due to data dependencies, branch mispredictions, cache misses, and structural hazards.

Conclusion: IPC = 0.833. The potential ILP of the architecture is 4, but the actual program only exploits about 21% of it. This illustrates the ILP wall — real programs simply do not have enough independent instructions to fully utilize wide-issue processors.

Interpretation: The question likely means the compiler reorders instructions to eliminate 3 stall cycles per instruction on average from the original pipeline.

Given:

• Original CPI = 2.5 (which means: Ideal CPI of 1.0 + 1.5 stall cycles per instruction)
• The compiler optimization eliminates 3 stall cycles. However, since the total stall component is only 1.5, the compiler can at most eliminate all 1.5 stall cycles.

Interpretation A (3 stalls eliminated from total program, not per instruction):

If 3 stall cycles are eliminated from an N-instruction sequence:

For large N, this approaches 2.5 (negligible improvement).

Interpretation B (Stall penalty per hazard reduced by eliminating 3 types of stalls):

If the compiler reduces the stall component from 1.5 to a lower value (e.g., by scheduling away 3 categories of stall):

If all stalls are eliminated: New CPI = 1.0 (the ideal).

Most Likely Intended Answer: If the original CPI includes 1.5 stall cycles and the compiler manages to eliminate all of them → New CPI = 1.0. If the "3 stalls" means the penalty is reduced by 3 stall cycles (not possible since only 1.5 exist), the minimum is still CPI = 1.0.

Under ideal conditions (perfect branch prediction, no cache misses, infinite resources), the achievable ILP is limited solely by True Data Dependencies (RAW dependencies).

Method to Determine ILP:

1. Build a Data Flow Graph (DFG): Represent each instruction as a node. Draw directed edges from instruction I to instruction J if J has a RAW dependency on I.
2. Find the Critical Path: The longest chain of dependent instructions through the graph. This is the minimum number of cycles required, even with infinite parallelism.
3. Calculate ILP:
   ILP = Total Number of Instructions / Length of Critical Path (in cycles)

Example:

I1: LOAD R1, mem     ; 1 cycle (assume)
I2: LOAD R2, mem     ; 1 cycle (independent of I1)
I3: ADD R3, R1, R2   ; 1 cycle (depends on I1 AND I2)
I4: MUL R4, R3, R5   ; 1 cycle (depends on I3)
I5: LOAD R6, mem     ; 1 cycle (independent)
I6: ADD R7, R6, R4   ; 1 cycle (depends on I4 AND I5)
    

Critical Path: I1 → I3 → I4 → I6 = 4 cycles. Total instructions = 6.

Even with infinite resources, this code can only achieve an IPC of 1.5 due to the chain of true dependencies.

VLIW is a processor architecture where the compiler explicitly packages multiple independent operations into a single, very wide instruction word. The hardware executes all operations within the word simultaneously without performing any runtime dependency checking.

Architecture Details:

• A VLIW instruction word is typically 128-1024 bits wide, containing multiple "slots" (e.g., 2 integer ops + 2 FP ops + 2 memory ops + 1 branch op).
• The compiler is entirely responsible for filling these slots with independent operations. If no independent operation is available for a slot, the compiler inserts a NOP.
• The hardware has multiple functional units (one per slot) that execute in lockstep based on the instruction word.

Key Characteristics:

1. No Dynamic Scheduling Hardware: No Reservation Stations, no Reorder Buffer, no Register Renaming. All scheduling is done statically by the compiler.
2. Simple, Power-Efficient Hardware: The chip area saved from removing OoO logic can be used for more functional units, larger caches, or lower power consumption.
3. Compiler Dependency: The quality of the generated code depends heavily on the compiler's ability to find ILP. A poor compiler produces many NOPs and underutilizes the hardware.

Examples: Intel Itanium (IA-64/EPIC), Texas Instruments C6000 DSPs, some embedded and signal processing architectures.

VLIW exploits ILP entirely through static, compile-time analysis and scheduling. The compiler does all the heavy lifting that would otherwise be done by expensive runtime hardware in a superscalar processor.

The Process:

1. Dependency Analysis: The compiler builds a complete dependency graph of the entire program (or large regions of it), identifying all RAW, WAR, and WAW dependencies.
2. Register Allocation & Renaming: The compiler eliminates WAR and WAW by using different registers (it has full visibility of the register file at compile time).
3. Instruction Scheduling: The compiler groups independent operations together and assigns them to specific functional unit slots in the VLIW instruction word.
4. Loop Unrolling & Software Pipelining: The compiler aggressively unrolls loops and applies software pipelining (interleaving iterations) to fill as many VLIW slots as possible.
5. Speculative Code Motion: The compiler may move instructions above branches speculatively. If the branch is mispredicted, the results are simply ignored (using predicated execution or speculative loads).

Example VLIW Word (4 slots):

| ADD R1, R2, R3 | MUL R4, R5, R6 | LOAD R7, 0(R8) | BNE R9, Loop |
    

All four operations execute simultaneously in a single clock cycle.

Key Insight: Superscalar won the general-purpose market because it can handle unpredictable runtime behavior (cache misses, data-dependent branches) gracefully. VLIW thrives in domains with predictable, regular computation (signal processing, media encoding) where the compiler can schedule effectively.

Reservation Stations (RS) are specialized hardware buffers placed in front of each functional unit in a dynamically scheduled (out-of-order) processor. They are central to Tomasulo's algorithm and modern superscalar designs.

Structure of a Reservation Station Entry:

Role in OoO Execution:

1. Buffering Instructions: After decode, instructions are dispatched to a free RS. The RS holds the instruction until all its operands are ready, decoupling the decode stage from the execute stage.
2. Operand Monitoring: Each RS continuously monitors the Common Data Bus (CDB). When a result is broadcast with a matching tag (Qj or Qk), the RS captures the value into Vj or Vk.
3. Implicit Register Renaming: Because operand values are copied into the RS (or referenced by tag), the original register can be freely overwritten by later instructions. This eliminates WAR and WAW hazards without a separate rename table.
4. Distributed, Parallel Scheduling: Each RS independently determines when its instruction is ready. Multiple RSs can simultaneously detect readiness and issue their instructions to different functional units in the same clock cycle, maximizing parallelism.
5. Enabling OoO Issue: A younger instruction in one RS can issue before an older instruction in another RS if the younger instruction's operands are ready first.

The Reorder Buffer (ROB) is a circular hardware queue that allows instructions to execute out of order but commit (retire) in strict program order. It is essential for supporting precise exceptions and correct speculative execution.

Structure of an ROB Entry:

How It Works:

1. Issue (Allocate): When an instruction is decoded, it is assigned an entry in the ROB in program order. The ROB entry number becomes the instruction's unique identifier (tag).
2. Execute (Out of Order): The instruction is dispatched to a Reservation Station and executes whenever its operands are ready. The result is written to the ROB entry (not the architectural register file).
3. Commit (In Order): The ROB has a head pointer pointing to the oldest instruction. Every cycle, the hardware checks if the instruction at the head is marked "Ready" (execution complete). If so:
   • For register writes: The value is copied from the ROB entry to the architectural Register File.
   • For stores: The data is written to the Data Cache.
   • For branches: If mispredicted, the ROB is flushed from this point onward.
   The head pointer advances to the next entry.

Why This Preserves Order:

Because the head pointer only advances sequentially, instructions always commit in program order, even though they may have completed execution in any order. If an older instruction causes an exception, all younger instructions (behind it in the ROB) are simply discarded, preserving a precise machine state.

Dynamic Scheduling is a hardware technique where the processor rearranges the order of instruction execution at runtime to reduce stalls and maximize functional unit utilization.

Key Difference from Static Scheduling:

• Static: The compiler determines instruction order at compile time. The hardware executes instructions exactly as arranged.
• Dynamic: The hardware examines instructions at runtime, determines dependencies, and issues instructions to functional units as soon as operands are available, regardless of program order.

How Dynamic Scheduling Supports ILP:

1. Bypasses Stalled Instructions: If instruction I2 is stalled waiting for a cache miss, dynamic scheduling allows independent instructions I3, I4, I5 to execute past I2. In a statically scheduled (in-order) processor, all instructions behind I2 would stall.
2. Handles Unpredictable Latencies: Cache misses, variable-latency operations (e.g., divides), and data-dependent timing are impossible to predict at compile time. Dynamic scheduling adapts to these at runtime.
3. Exploits ILP Across Basic Blocks: Combined with branch prediction and speculative execution, dynamic scheduling can find and exploit ILP across multiple branches, which is very difficult for a compiler to do statically.
4. Register Renaming: Dynamic scheduling hardware typically includes register renaming, which eliminates WAR and WAW false dependencies, further increasing the pool of independent instructions.

Implementation: Dynamic scheduling is implemented using Tomasulo's algorithm (Reservation Stations + CDB) or Scoreboarding (an earlier, simpler approach). Modern processors combine dynamic scheduling with ROBs for speculative execution.