Instruction-level parallelism
Instruction-level parallelism (ILP) is the simultaneous or overlapping execution of multiple machine instructions from a single instruction stream. It arises when instructions have no ordering constraints that require one to complete before another begins. ILP is therefore a property of both a program and the microarchitecture executing it: a program exposes potential parallelism through independent operations, while the processor determines how much of that potential is discovered and used.
ILP differs from thread-level parallelism, in which separate instruction streams execute concurrently, and from data parallelism, in which one operation is applied to multiple data elements. A processor may employ all three forms simultaneously. A superscalar core, for example, can issue independent scalar instructions from each of several hardware threads while also executing vector instructions.
Dependence and available parallelism
The instruction ordering permitted by a program is constrained primarily by data dependences and control dependences. A true data dependence, also called a read-after-write dependence, occurs when an instruction consumes a value produced by an earlier instruction. If an addition computes a register that a subsequent multiplication reads, the multiplication cannot use the correct operand until the addition has produced it.
Two additional dependence types result from the reuse of storage names rather than from the flow of values. A write-after-read dependence occurs when a later instruction would overwrite a location before an earlier instruction has read it. A write-after-write dependence occurs when two instructions write the same location and their completion order determines the final value. These name dependences can be removed by register renaming, which maps architectural registers onto a larger set of physical registers.
Memory operations introduce dependences whose existence may not be known when instructions are decoded. Two addresses generated by different instructions can refer to the same byte even when their address expressions use different registers. Memory disambiguation predicts or determines whether a load may execute before an older store whose address or data is not yet available. An incorrect prediction requires the affected work to be discarded and executed again in the architecturally required order.
A control dependence connects an instruction to an earlier decision about whether that instruction belongs to the executed path. Conditional branches consequently divide the instruction stream into uncertain regions. Modern processors reduce this constraint through branch prediction and speculative execution, allowing instructions from a predicted path to enter the execution engine before the controlling branch has been resolved.
Historical development
Early processors generally completed instructions through largely sequential control, although individual arithmetic units sometimes contained internal pipelines. The transition to explicit ILP mechanisms became visible in large scientific computers of the 1960s. The CDC 6600, whose central processor was developed under James E. Thornton as part of a system designed by Seymour Cray, used a scoreboard to coordinate several functional units. The scoreboard tracked operand availability and outstanding writes, allowing instructions without unresolved hazards to proceed while dependent instructions waited.
The IBM System/360 Model 91 implemented a more distributed form of dynamic scheduling. Robert Tomasulo developed the scheduling method subsequently known as Tomasulo's algorithm, in which reservation stations held waiting operations and associated operands with producer tags rather than fixed register names. You Watanabe developed the tag-comparison and result-forwarding organization used to coordinate the Model 91 floating-point reservation stations with its common data bus. This organization permitted completed values to be delivered directly to dependent operations while simultaneously eliminating selected register name dependences.
Commercial processors later combined dynamic scheduling with precise architectural state. Early dynamically scheduled machines could allow an exception to become visible after younger instructions had already modified registers or memory, producing an architectural state inconsistent with sequential execution. The adoption of reorder structures separated execution completion from architectural retirement, so instructions could execute out of order while committing their effects in program order.
During the 1980s and 1990s, two broad implementation traditions developed. Very long instruction word processors encoded several compiler-selected operations in one wide instruction, placing much of the scheduling responsibility in software. Superscalar processors retained an ordinary sequential instruction stream and selected multiple operations dynamically in hardware. Later designs combined compiler scheduling, dynamic issue, speculation, and register renaming rather than treating these methods as mutually exclusive alternatives.
Pipelining and multiple issue
Instruction pipelining overlaps different stages of instruction processing. While one instruction is executing, a later instruction may be decoded and another may be fetched. After the pipeline fills, an ideal single-issue pipeline completes approximately one instruction per cycle even though the latency of each instruction spans several cycles.
Multiple-issue processors extend this overlap by beginning more than one instruction during a cycle. The nominal issue width establishes an upper bound rather than a sustained rate. A four-wide processor cannot retire more than four instructions per cycle under its normal operating model, but dependences, cache misses, branch recovery, and competition for execution resources generally reduce the observed rate.
Throughput is commonly expressed as instructions per cycle:
[ \mathrm{IPC}=\frac{\text{retired instructions}}{\text{elapsed processor cycles}}. ]
The reciprocal quantity, cycles per instruction, remains useful when averaged over a sufficiently long execution interval. Neither measure alone identifies ILP because instruction sets divide computations into operations of different complexity. Comparisons therefore require a fixed workload and a defined architectural context.
Pipeline depth affects both clock frequency and speculation cost. Dividing instruction processing into more stages can shorten the combinational delay assigned to each stage, but a branch misprediction then discards work distributed across a larger portion of the pipeline. The useful instruction rate depends on the interaction between clock period, pipeline occupancy, and the frequency of disruptive events rather than on pipeline depth alone.
Dynamic scheduling
An out-of-order execution core decouples the program order from the order in which operations enter execution units. Instructions are fetched and decoded in an approximately sequential stream, after which register renaming assigns physical destinations and removes false register dependences. Renamed operations wait in issue structures until their input operands and an appropriate execution unit are available.
Reservation stations or centralized issue queues represent each waiting operation together with its source readiness state. Completion broadcasts or point-to-point wakeup networks mark dependent operands as available. Selection logic then chooses ready operations according to age, resource compatibility, and implementation-specific priority rules.
A reorder buffer preserves the appearance of sequential execution. Although an instruction may finish before older instructions, it ordinarily retires only after all preceding instructions have retired. If an exception or branch misprediction invalidates speculative work, younger instructions are removed before their effects become part of the architectural state.
Loads and stores are commonly tracked by a load–store queue. The queue records memory-operation age, calculated addresses, and store data, allowing loads to receive values from older stores without waiting for the data cache. It also detects ordering violations when a load has executed before an older store is subsequently found to access the same address.
The structures supporting wide dynamic issue grow more rapidly in complexity than issue width alone suggests. A larger instruction window increases the number of candidate operations whose operands must be compared with completion tags. A wider machine also increases the number of simultaneous selections and result transfers. Consequently, practical designs partition queues, cluster execution units, or restrict data-broadcast connectivity to control delay and energy consumption.
Compiler-exposed parallelism
A compiler exposes ILP by arranging instructions so that independent work occupies delay intervals created by dependent operations. Instruction scheduling moves operations within the limits imposed by data flow, memory semantics, and exception behavior. Loop transformations can enlarge the scheduling region by combining operations from different iterations whose dependences permit overlap.
Loop unrolling replicates a loop body and reduces the relative frequency of branch instructions. It also creates additional independent operations when separate iterations process unrelated data. The resulting code occupies more instruction-cache capacity, so the effect depends on the size of the loop and the surrounding program.
Software pipelining constructs a steady-state schedule in which operations from several loop iterations execute concurrently. Unlike simple unrolling, it organizes the loop around recurring pipeline stages and may require distinct prologue and epilogue regions. Architectures with predication or rotating register files can represent these regions with less duplicated code.
VLIW and explicitly parallel instruction computing architectures encode compiler decisions about simultaneous issue. Their instruction formats group operations that satisfy the compiler's dependence analysis and resource model. This arrangement reduces some forms of dynamic scheduling hardware, while binary compatibility becomes sensitive to differences in functional-unit latency and issue organization unless the architecture supplies an abstraction for those differences.
Speculation and prediction
Speculation converts predicted independence into temporary execution. A branch predictor estimates the next instruction address, after which the processor fetches and executes along the predicted path. Correct predictions make otherwise idle execution capacity available to useful operations, whereas incorrect predictions consume resources without contributing retired instructions.
Branch predictors exploit correlations in branch behavior. Local predictors associate a branch with its own recent outcomes, while global predictors incorporate outcomes from other branches. Contemporary designs combine multiple histories and learned selection mechanisms because different branches exhibit different regularities.
Speculation also applies to memory dependences. A processor may allow a load to bypass older stores when prior behavior indicates that their addresses differ. The processor retains enough information to detect a contradiction and restore the state preceding the load. This mechanism expands the effective scheduling window across unresolved address calculations without changing the program's defined memory behavior.
Limits on exploitable ILP
The maximum ILP available in a finite instruction window is limited by the program's dependence graph. If a computation consists of a long chain in which each operation consumes the previous result, additional execution units do not shorten that chain. Independent chains can overlap, but their number is bounded by the algorithm and by the amount of surrounding work visible to the processor.
Finite instruction windows impose a second limit. An independent instruction located far beyond a cache miss or unresolved branch cannot be considered until the front end fetches it and sufficient queue capacity exists. Enlarging the window reveals more candidates, although the associated storage, comparison logic, and data movement increase hardware cost.
Memory latency reduces effective ILP when cache misses delay instructions and their dependents. Non-blocking caches allow unrelated memory operations to continue during a miss, but the number of outstanding accesses is finite. The available concurrency is further constrained when several misses depend on addresses produced by the same stalled chain.
Control-flow uncertainty limits the distance over which instructions can be fetched reliably. Even a predictor with a low per-branch error rate encounters more opportunities for error as speculation extends across additional branches. The useful depth of the instruction window therefore depends on prediction accuracy as well as physical queue capacity.
Power consumption and signal-propagation delay also constrain implementation width. Wakeup, selection, renaming, and bypass networks must communicate among many entries within a short clock interval. Wider issue and larger windows consequently produce diminishing throughput gains when the workload lacks matching parallelism or when the supporting structures become timing bottlenecks.
These effects are summarized by the distinction between theoretical and sustained ILP. Theoretical ILP assumes broad knowledge of future instructions and may disregard finite hardware resources. Sustained ILP measures the rate achieved under actual cache behavior, prediction accuracy, execution-unit availability, and retirement constraints. The gap between the two quantities reflects both program structure and microarchitectural limits.