Separate execution from architectural commitment
A pipeline cannot consume a result before its producing instruction makes that result available. It does not follow that every unrelated instruction must wait for the same result. Out-of-order execution selects work whose operands and execution resources are ready, even when an earlier instruction is stalled. Read the CPU pipeline textbook first: this guide extends its dependency and resource hazards into a schedule for individual instructions. Registers, loads, addition and the distinction between fetching an instruction and producing its result are prerequisites.
We distinguish three boundaries. Here, issue means dispatching a waiting ready instruction to an execution unit. Completion means obtaining its arithmetic or load result. Retirement means committing the instruction's architectural effects in program order. Some documentation uses issue for admission to a queue instead, so compare the boundary described by a term before comparing diagrams. A completed younger instruction need not retire immediately. This distinction explains how useful work can move ahead while the machine still presents the program's required results and exception behavior.
Build two dependency chains
Use four instructions. I1 loads memory into r1. I2 adds one to r1 and writes r2. I3 adds r4 and r5 into r3. I4 adds one to r3 and writes r6. Draw edges from I1 to I2 and from I3 to I4. There is no value dependency from I1 to I3. With r4 equal to ten, r5 equal to twenty and the loaded value equal to seven, the required final values are r2=8, r3=30 and r6=31. Draw dependencies from actual producers to consumers rather than treating nearby source lines as dependent by default.
For the teaching schedule, allow one issue per cycle, a four-cycle load and a one-cycle addition. A completed result becomes available in the following cycle. Assume fetching and decoding have already placed all instructions in waiting structures. Issue I1 in cycle one, I3 in cycle two and I4 in cycle three. I2 still waits for the load. These numbers define a scheduling exercise, not measured latencies of a named processor.
Compare completion with retirement
In the table, I3 completes at the end of cycle two and I4 at the end of cycle three. I1 completes at the end of four, allowing I2 to issue and complete in five. Add an explicit retirement rule: at most one instruction retires per cycle, no earlier than the cycle after completion, and always in program order. Retirement then occurs in cycles five, six, seven and eight for I1 through I4. Early completion of I3 does not permit skipping unresolved older instructions at retirement.
With strictly ordered issue under the same assumptions, I2 blocks younger issue during cycles two through four. I2, I3 and I4 issue in five, six and seven. Out-of-order execution overlaps useful work with part of the wait; it does not shorten the load's own latency. The final difference depends on issue width, retirement width, queue capacity and the available execution units. Keep the rules alongside the table so another reader can reproduce the schedule rather than interpreting a particular cycle count as a hardware promise.
| Instruction | Issue | Complete, end of cycle | Retire |
|---|---|---|---|
| I1: load r1 | 1 | 4 | 5 |
| I2: r2=r1+1 | 5 | 5 | 6 |
| I3: r3=r4+r5 | 2 | 2 | 7 |
| I4: r6=r3+1 | 3 | 3 | 8 |
Distinguish reused names from needed values
Suppose J1 reads the old r1 to produce r2, while J2 writes a new value into r1. Executing J2 first must not erase the value J1 needs. Yet J1 does not need J2's result; the conflict concerns reuse of a name. Register renaming assigns different physical storage to different versions of an architectural register. It can remove this naming obstacle while preserving which producer each consumer depends on. A diagram should identify the version, rather than labeling every edge simply r1.
Renaming cannot remove I2's need for the value loaded by I1. That value must actually become available. Nor are rename registers, waiting structures or reorder capacity unlimited. A long stalled older load can leave many completed younger instructions unable to retire, eventually filling the window and stopping further admission. Source-level independence is therefore necessary for some overlap opportunities but does not establish unlimited parallelism. Identify both the value dependency and the finite storage or execution resource that could prevent the proposed schedule.
Include exceptions and memory dependencies
If I1 faults on an invalid address, the processor must present an architectural exception state consistent with encountering I1 in program order. I3 may already have computed a result, but that does not make its result an irrevocable architectural update. Holding speculative results until retirement supports this distinction. Microarchitectural traces, such as cache effects left by speculation, are another matter. Do not merge architectural exception correctness with claims about the absence of side channels.
Loads and stores also depend on whether their addresses overlap, and those addresses may not yet be known. Processor scheduling, compiler reordering and the ISA's inter-core memory ordering promises are different layers. A correct single-thread schedule does not eliminate the need for synchronization between threads. Use the programming language's memory model and appropriate synchronization operations to explain shared-variable visibility. Adding volatile is not a general replacement for those operations. The useful question at each layer is which ordering relation must be preserved and which mechanism actually preserves it.
Measure the dependency structure you intended
A reduction through one accumulator forms a chain, whereas several independent accumulators may expose overlapping arithmetic. Compare equal work and equal inputs before attributing a difference to that opportunity. Compilers can replace loops algebraically or vectorize them, so consume the results and inspect the resulting instructions. Signed integer overflow in C is not a valid device for manufacturing a fast benchmark. Choose defined arithmetic and verify that the relevant chains remain in the binary.
Changing accumulation order can also change floating-point rounding. A mathematically equivalent expression need not produce identical bits, so establish the required numerical contract before allowing reassociation. Hiding memory latency additionally depends on knowing future load addresses early enough. Pointer chasing, where the next address depends on the previous load, differs from a sequential array traversal. Elapsed time includes many factors beyond the schedule studied here. Do not convert one timing difference into a claimed measurement of issue width or a precise hardware latency.
Vary issue width without merging resource limits
Suppose issue width becomes two and two independent additions are ready together. Two suitable execution units can accept them in the same cycle, but one available unit can still constrain execution. Issue width, execution-unit admission and operation latency are separate limits. If retirement remains one instruction per cycle, simultaneous completion still does not permit two architectural commits together. Annotate which schedule rule changed instead of multiplying performance by one changed width.
Solve the longer-load exercise
Extend only I1's load latency to eight cycles. I3 and I4 still issue in cycles two and three. I1 completes at the end of eight, and I2 issues and completes in nine. Under the same retirement rule, I1 through I4 retire in cycles nine, ten, eleven and twelve. Mark I3 and I4 as complete but waiting for retirement. This shows why doing useful work early can coexist with an older operation still delaying architectural progress.
Now change I3 to compute r3=r2+r5. The dependency graph becomes one chain, I1 to I2 to I3 to I4. More renamed registers cannot supply a value that has not been produced. Conversely, adding independent work does not make a one-issue machine issue unlimited instructions per cycle. The exercise is complete when you can explain required values, finite resources and retirement order separately. Continue to branch prediction and SIMD for two other dimensions: predicting future control flow and increasing the number of data elements processed by an instruction.