Hubbry Logo
Hazard (computer architecture)Hazard (computer architecture)Main
Open search
Hazard (computer architecture)
Community hub
Hazard (computer architecture)
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Hazard (computer architecture)
Hazard (computer architecture)
Hazard (computer architecture)
View on Wikipedia
from Wikipedia

In the domain of central processing unit (CPU) design, hazards are problems with the instruction pipeline in CPU microarchitectures when the next instruction cannot execute in the following clock cycle,[1] and can potentially lead to incorrect computation results. Three common types of hazards are data hazards, structural hazards, and control hazards (branching hazards).[2]

There are several methods used to deal with hazards, including pipeline stalls/pipeline bubbling, operand forwarding, and in the case of out-of-order execution, the scoreboarding method and the Tomasulo algorithm.

Background

[edit]
Further information: Instruction pipelining

Instructions in a pipelined processor are performed in several stages, so that at any given time several instructions are being processed in the various stages of the pipeline, such as fetch and execute. There are many different instruction pipeline microarchitectures, and instructions may be executed out-of-order. A hazard occurs when two or more of these simultaneous (possibly out of order) instructions conflict.

Types

[edit]

Structural hazards

[edit]

A structural hazard occurs when two (or more) instructions which are already in a pipeline need the same resource. The result is that instructions must be executed in series rather than in parallel for a portion of the pipeline. Structural hazards are sometimes referred to as resource hazards.

Example: A situation in which multiple instructions are ready to enter the execution phase but there is a single ALU (Arithmetic Logic Unit). One solution to this resource hazard is to increase available resources, by having multiple ports into main memory and multiple ALUs.

Control hazards (branch hazards or instruction hazards)

[edit]

Control hazard occurs when the control logic incorrectly predicts which program branch will be taken and therefore brings a sequence of instructions into the pipeline that are subsequently discarded. The term branch hazard also refers to a control hazard.

Pipeline bubbling

[edit]
Main article: Bubble (computing)

Bubbling the pipeline, also termed a pipeline break or pipeline stall, is a method to preclude data, structural, and branch hazards. As instructions are fetched, control logic determines whether a hazard could/will occur. If this is true, then the control logic inserts no operations (NOPs) into the pipeline. Thus, before the next instruction (which would cause the hazard) executes, the prior one will have had sufficient time to finish and prevent the hazard. If the number of NOPs equals the number of stages in the pipeline, the processor has been cleared of all instructions and can proceed free from hazards. All forms of stalling introduce a delay before the processor can resume execution.

Flushing the pipeline occurs when a branch instruction jumps to a new memory location, invalidating all prior stages in the pipeline. These prior stages are cleared, allowing the pipeline to continue at the new instruction indicated by the branch.[3][4]

Data hazards

[edit]

There are several main solutions and algorithms used to resolve data hazards:

  • insert a pipeline bubble whenever a read after write (RAW) dependency is encountered, guaranteed to increase latency, or
  • use out-of-order execution to potentially prevent the need for pipeline bubbles
  • use operand forwarding to use data from later stages in the pipeline

In the case of out-of-order execution, the algorithm used can be:

The task of removing data dependencies can be delegated to the compiler, which can fill in an appropriate number of NOP instructions between dependent instructions to ensure correct operation, or re-order instructions where possible.

Operand forwarding

[edit]
Main article: Operand forwarding

Examples

[edit]
In the following examples, computed values are in bold, while Register numbers are not.

For example, to write the value 3 to register 1, (which already contains a 6), and then add 7 to register 1 and store the result in register 2, i.e.: 

i0: R1 = 6
i1: R1 = 3
i2: R2 = R1 + 7 = 10

Following execution, register 2 should contain the value 10. However, if i1 (write 3 to register 1) does not fully exit the pipeline before i2 starts executing, it means that R1 does not contain the value 3 when i2 performs its addition. In such an event, i2 adds 7 to the old value of register 1 (6), and so register 2 contains 13 instead, i.e.: 

i0: R1 = 6
i2: R2 = R1 + 7 = 13
i1: R1 = 3

This error occurs because i2 reads Register 1 before i1 has committed/stored the result of its write operation to Register 1. So when i2 is reading the contents of Register 1, register 1 still contains 6, not 3.

Forwarding (described below) helps correct such errors by depending on the fact that the output of i1 (which is 3) can be used by subsequent instructions before the value 3 is committed to/stored in Register 1.

Forwarding applied to the example means that there is no wait to commit/store the output of i1 in Register 1 (in this example, the output is 3) before making that output available to the subsequent instruction (in this case, i2). The effect is that i2 uses the correct (the more recent) value of Register 1: the commit/store was made immediately and not pipelined.

With forwarding enabled, the Instruction Decode/Execution (ID/EX) stage of the pipeline now has two inputs: the value read from the register specified (in this example, the value 6 from Register 1), and the new value of Register 1 (in this example, this value is 3) which is sent from the next stage Instruction Execute/Memory Access (EX/MEM). Added control logic is used to determine which input to use.

Control hazards (branch hazards)

[edit]

To avoid control hazards microarchitectures can:

  • insert a pipeline bubble (discussed above), guaranteed to increase latency, or
  • use branch prediction and essentially make educated guesses about which instructions to insert, in which case a pipeline bubble will only be needed in the case of an incorrect prediction

In the event that a branch causes a pipeline bubble after incorrect instructions have entered the pipeline, care must be taken to prevent any of the wrongly-loaded instructions from having any effect on the processor state excluding energy wasted processing them before they were discovered to be loaded incorrectly.

Other techniques

[edit]

Memory latency is another factor that designers must attend to, because the delay could reduce performance. Different types of memory have different accessing time to the memory. Thus, by choosing a suitable type of memory, designers can improve the performance of the pipelined data path.[5]

See also

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Hazard (computer architecture)

View on Grokipedia
from Grokipedia
In computer architecture, a pipeline hazard is a situation in a pipelined processor where an instruction cannot execute during its designated clock cycle due to dependencies on previous instructions or conflicts over shared hardware resources, potentially causing stalls, flushes, or incorrect results if unaddressed. These hazards fundamentally challenge the performance gains of pipelining by disrupting the ideal overlap of instruction execution, increasing cycles per instruction (CPI), and requiring specialized hardware or software techniques for resolution. Pipeline hazards are categorized into three primary types: structural hazards, data hazards, and control hazards, each arising from different aspects of instruction overlap in classic five-stage pipelines like fetch, decode, execute, memory, and write-back. Structural hazards emerge when multiple instructions in the pipeline demand the same hardware resource simultaneously, such as a single port for both instruction fetch and access or limited write ports in the register file. For example, in a MIPS-like , a load instruction accessing while the next instruction fetches from instruction can cause a conflict if only one unit is available. These are typically mitigated by duplicating resources (e.g., separate instruction and caches), redesigning the to avoid overlaps, or inserting stalls to serialize access, though such solutions trade off hardware cost for throughput. Data hazards occur due to dependencies between instructions where a later instruction requires a result from an earlier one that has not yet been computed or written back, altering the expected read-after-write order through pipelining. They are subclassified as read-after-write (RAW, or true data dependence, e.g., an add instruction using a register value produced by a prior load), write-after-read (WAR, anti-dependence), and write-after-write (WAW, output dependence). A common case is the load-use hazard, where an instruction immediately following a load stalls for one cycle because the data is unavailable until write-back. Resolutions include hardware forwarding (bypassing results from execute or memory stages directly to dependent instructions), compiler-inserted no-operation (NOP) instructions, dynamic scheduling via techniques like Tomasulo's algorithm, or register renaming to eliminate false dependencies, which can reduce stall penalties significantly but add complexity. Control hazards arise from instructions that alter the , such as or jumps, creating uncertainty about which instructions to fetch next until the outcome is resolved, often leading to the fetching incorrect instructions (e.g., assuming a is not taken). In a standard , this can result in a multi-cycle penalty, as seen in older architectures like the with up to three stall cycles for . Mitigation strategies encompass delayed branching (where the schedules useful instructions in the ), early branch resolution in the decode stage to minimize penalties to one cycle, static prediction (e.g., always not-taken), and advanced dynamic prediction using branch history tables or predictors, achieving misprediction rates as low as 5-10% in modern processors and reducing effective CPI impact to near 1.0. Overall, addressing pipeline hazards is central to modern processor design, enabling sustained while balancing power, area, and performance; techniques like and have evolved to tolerate hazards from deeper in superscalar and () architectures.

Fundamentals

Definition and Overview

In , a hazard refers to a situation in a pipelined processor where the hardware cannot proceed with the execution of the next instruction in its scheduled clock cycle due to unresolved dependencies or resource conflicts between instructions, leading to pipeline stalls or flushes that reduce overall instruction throughput. These disruptions prevent the ideal overlap of instruction stages, forcing the processor to insert idle cycles or discard partially executed instructions to maintain correctness. , which enables concurrent processing of multiple instructions across stages like fetch, decode, execute, and write-back, is the foundational technique that exposes such hazards. Pipeline hazards were first systematically addressed in early pipelined computer designs of the 1960s, such as the , which used for data hazard detection, and the , which employed in its floating-point unit. The challenges intensified in the 1980s with the rise of (RISC) architectures, including projects like the , Berkeley RISC, and MIPS, which employed deeper pipelines to boost performance but amplified the frequency and severity of hazards due to increased instruction overlap. The performance impact of hazards is quantified through the (CPI) metric, where the effective CPI rises above the ideal value of 1 as stalls accumulate; specifically, effective CPI = 1 + average stall cycles per instruction, directly degrading throughput in pipelined systems. In superscalar processors, which aim to exploit (ILP) by issuing multiple , hazards impose fundamental limits on ILP by restricting how much independent instruction execution can be overlapped without errors.

Instruction Pipeline Basics

In , the classic five-stage pipeline represents a foundational design for processing instructions in reduced instruction set (RISC) processors, dividing the execution of each instruction into five sequential stages to enable overlapping operations. This structure, exemplified in the , assumes a single-issue, in-order execution model where instructions are fetched and processed sequentially without advanced features like caching or branching optimizations beyond basic updates. The stages are as follows:
  • Instruction Fetch (IF): This initial stage retrieves the instruction from memory using the current program counter (PC) value, stores the fetched instruction in the IF/ID pipeline register (buffer), and increments the PC by 4 bytes to point to the next instruction, assuming 32-bit instructions.
  • Instruction Decode and Register Read (ID): Here, the instruction is decoded to identify the operation and operands, registers specified in the instruction are read from the register file, and control signals are generated; the results, including operands and destination register information, are passed to the ID/EX pipeline register.
  • Execute or Address Calculation (EX): The arithmetic logic unit (ALU) performs the required computation (such as addition or subtraction for arithmetic instructions) or calculates a memory address for load/store operations, with the result and updated control information forwarded to the EX/MEM pipeline register.
  • Memory Access (MEM): For load and store instructions, this stage interacts with data memory to read or write the operand; other instructions pass through without memory operations, and the memory result (if any) along with destination details is stored in the MEM/WB pipeline register.
  • Write Back (WB): The final stage writes the execution result (from ALU or memory) back to the destination register in the register file, using information from the MEM/WB pipeline register to complete the instruction.
In an ideal scenario without disruptions, the allows multiple instructions to overlap in execution, with each stage processing a different instruction simultaneously in every clock cycle, achieving a throughput of one instruction per cycle (CPI = 1). This overlapping flow can be visualized as a series of instructions advancing through the stages like an : while one instruction is in WB, another is in MEM, a third in EX, and so on, up to the fifth entering IF. The primary benefit is increased throughput, yielding a potential approaching the pipeline depth—for a five-stage pipeline, up to 5x compared to a non-pipelined processor executing one instruction fully before starting the next—assuming balanced stage latencies and no stalls. Hazards represent disruptions to this smooth overlapping flow, potentially causing stalls or flushes.

Types of Hazards

Structural Hazards

Structural hazards arise in pipelined processors when multiple instructions attempt to use the same hardware simultaneously, leading to conflicts over shared components such as or functional units. Unlike or control hazards, these do not involve dependencies on instruction results or execution flow but rather limitations in hardware availability. A classic example occurs in processors with a unified , where a single unit serves both instructions and . In such systems, the instruction fetch (IF) stage, which retrieves the next instruction, may conflict with the access (MEM) stage of a prior instruction, such as a load or store operation that reads or writes . For instance, in a simple MIPS-like with a single-port , if a store instruction occupies the MEM stage in one clock cycle, the subsequent instruction's IF stage must because the port cannot handle both accesses concurrently. This issue influenced the adoption of separate instruction and caches, drawing from principles, to allow parallel access and eliminate the conflict. In modern high-performance processors, structural hazards are rare due to extensive resource duplication, including split L1 instruction and data caches, multiple execution units, and wider pipelines that provide sufficient parallelism. However, they remain relevant in resource-constrained environments like embedded systems or simple in-order processors using unified caches. In these cases, memory-related structural hazards can contribute to pipeline stalls, increasing (CPI). Split caches mitigate this entirely by dedicating separate ports for instruction fetches and data accesses, avoiding stalls without introducing data dependencies. The primary impact of structural hazards is to force pipeline stalls, inserting no-operation (NOP) bubbles to delay dependent stages until the resource becomes available, which degrades throughput without affecting correctness. These hazards must typically be resolved at the architectural design stage through rather than runtime detection, emphasizing the importance of balanced hardware provisioning in .

Data Hazards

Data hazards arise in pipelined processors when there is a dependency between instructions on the values of operands, such that a later instruction requires produced by an earlier one that has not yet completed its execution. These hazards occur due to the overlapping nature of instruction execution stages, particularly when the result of one instruction is needed in the execute stage of a subsequent instruction before it is written back to the register file. Unlike structural hazards, which involve , data hazards stem from logical dependencies in the flow. Data hazards are classified into three types based on the order of read and write operations: read-after-write (RAW), write-after-read (WAR), and write-after-write (WAW). RAW hazards, also known as true or flow dependencies, are the most prevalent in in-order , occurring when an instruction reads a register before a previous instruction writes to it. For example, consider the sequence add $t0, $t1, $t2 followed by sub $t3, $t0, $t4 in a classic MIPS ; if the sub enters the execute stage before the add completes its write-back, it would read the stale value of $t0, leading to incorrect results unless the is . This type dominates because most programs exhibit flow dependencies, where data flows from producer to consumer instructions. WAR hazards, or antidependencies, arise when an instruction writes to a register that a previous instruction intends to read, potentially overwriting a value before it is used; these are less common in in-order pipelines, as instructions execute sequentially, but they can manifest in if a write completes prematurely relative to an earlier read. An illustrative sequence is sub $t0, $t1, $t2 followed by add $t3, $t4, $t0; here, if the add reads $t0 after the sub has written but before the original value is consumed, the dependency is violated, though in-order execution typically avoids this without reordering. Similarly, WAW hazards, or output dependencies, occur when two instructions write to the same register, with the second potentially overwriting before the first commits; for instance, add $t0, $t1, $t2 followed by or $t0, $t3, $t4 risks the second write dominating if the first has not yet stored its result. Both WAR and WAW are name dependencies rather than true data flows and are rarer in simple in-order designs but require attention in advanced architectures. These hazards are characterized by the dependency distance, or the number of instructions between the dependent pair, which determines the overlap in stages. True dependencies (RAW) represent actual data flow and are unavoidable in dependent code, while anti- () and output (WAW) dependencies arise from register naming and can be illustrated in sequences like the loop for (i=0; i<100; i++) { A[i] = B[i] + C[i]; D[i] = A[i] + E[i]; }, where the second statement has a RAW on A[i] from the first (true dependence with distance 1), but if registers are reused across iterations, WAR or WAW may emerge on shared names. Short dependency distances (1-2 instructions) cause immediate stage overlaps, such as the execute stage of the consumer clashing with the write-back of the producer, exacerbating issues in integer ALU operations. In classic MIPS-like processors, data hazards are the dominant source of pipeline stalls, particularly RAW types in integer pipelines, accounting for a significant portion of performance degradation. For instance, in SPEC89 benchmarks on floating-point pipelines, FP result stalls—a type of data hazard—contributed an average of 0.71 stalls per instruction and represented 82% of all stalled cycles. In integer units, where latencies are shorter, RAW hazards from loads and ALU operations are a major source of stall cycles in unoptimized pipelines, highlighting the need for careful dependency management to maintain throughput.

Control Hazards

Control hazards occur in pipelined processors when the decision on the next instruction to fetch cannot be determined in time due to unresolved control flow instructions, such as branches, leading the pipeline to potentially fetch incorrect instructions. This primarily impacts the fetch and decode stages, as the program counter update depends on the branch outcome, which is typically resolved later in the execution stage. In a classic five-stage pipeline, this results in a penalty of 2-3 cycles for a taken branch, measured by the number of flushed instructions after the branch resolution. The main types of control hazards stem from conditional branches, which depend on runtime conditions to decide between taken or not-taken paths, and unconditional jumps, which always alter the control flow without condition checks. Conditional branches, such as equality checks (e.g., BEQZ in MIPS), introduce uncertainty in the fetch sequence, while unconditional jumps force an immediate redirect. These hazards disrupt sequential execution assumed by the pipeline, requiring the flushing of erroneously fetched instructions. In typical programs, branches constitute 5-20% of all instructions, with variations observed across benchmarks like SPEC integer programs where frequencies range from about 13-14% in compression tasks to higher in others. This frequency directly influences cycles per instruction (CPI) through the branch penalty, quantified as the product of branch frequency, misprediction rate, and misprediction cost in cycles, amplifying overall pipeline inefficiency. Data hazards can compound this by delaying the resolution of branch conditions dependent on prior computations. A representative example arises in if-then-else structures, where the pipeline initially speculates and fetches instructions sequentially after a conditional branch, but must flush the pipeline and restart from the taken path if the condition evaluates true, incurring the full branch penalty. Exceptions and interrupts represent severe forms of control hazards, as they abruptly redirect execution to handler routines, overlapping with operating system management but still causing pipeline flushes similar to branches.

Detection Mechanisms

Hazard Detection in Pipelines

Hazard detection in pipelined processors involves dedicated hardware logic that identifies potential conflicts arising from data, control, or structural dependencies as instructions progress through pipeline stages, enabling subsequent mitigation without violating correctness. This logic is typically implemented using combinational circuits for low-latency decisions, often placed in the instruction decode (ID) or execute (EX) stages to inspect opcode, operands, and pipeline registers. In classic in-order pipelines like the , detection focuses on read-after-write (RAW) data hazards by comparing source registers of the current instruction with destination registers of prior instructions still in execution. For data hazards, the detection unit examines whether the destination register (Rd) of an instruction in the EX/MEM or MEM/WB stages matches the source register (Rs or Rt) of the instruction in the ID stage, signaling a RAW dependency if the prior instruction has not yet written back its result. This is particularly critical for load-use cases, where the condition is checked as: if (ID/EX.MemRead && ((ID/EX.RegisterRt == IF/ID.RegisterRs) || (ID/EX.RegisterRt == IF/ID.RegisterRt))), indicating a stall signal to prevent forwarding from being insufficient. In more advanced dynamically scheduled pipelines, a scoreboard serves as the primary detection mechanism, tracking register dependencies across multiple outstanding instructions by maintaining status flags for each register (busy or available) and functional unit, flagging hazards when an instruction attempts to read a register still being written by a prior operation. Control hazards are detected during branch condition evaluation, typically in the EX stage, where the ALU computes the branch outcome and target address, then asserts a signal to redirect the program counter (PC) if the branch is taken, flushing incorrectly fetched instructions from the fetch (IF) and ID stages. To reduce latency, some designs shift this logic to the ID stage using equality comparators on register operands (e.g., XOR gates followed by OR reduction) and immediate offset addition to the PC, signaling an immediate fetch redirect while incorporating additional hazard checks for operand availability. Structural hazards are identified through resource arbitration signals, such as busy indicators from shared hardware units like memory ports or functional units, where detection logic in the ID or EX stage monitors if two instructions in overlapping stages (e.g., IF and MEM both accessing instruction/data memory) contend for the same resource, often resolved by prioritizing one and delaying the other via stall signals. In designs with unified caches, this may involve a multiplexer selector that detects conflicts and routes access accordingly. Implementation of these units relies on simple pseudocode-like conditions embedded in hardware, for example, for RAW data detection in the ID stage:

if (ID.rs == EX.rd && EX.RegWrite) or (ID.rs == MEM.rd && MEM.RegWrite) then signal_data_hazard;

if (ID.rs == EX.rd && EX.RegWrite) or (ID.rs == MEM.rd && MEM.RegWrite) then signal_data_hazard;

Such logic ensures hazards are flagged with minimal cycle overhead, typically within a single clock using parallel comparators.

Pipeline Stalling and Bubbling

Pipeline stalling and bubbling are fundamental techniques used to maintain correctness in pipelined processors when hazards cannot be immediately resolved, by deliberately delaying the progression of instructions through the pipeline stages. Stalling involves pausing the execution of earlier pipeline stages, such as the instruction fetch (IF) and instruction decode (ID) stages, while allowing later stages to continue their operations. This is achieved through control signals that disable the writing of new values to pipeline registers, effectively holding the program counter (PC) and the IF/ID register in their current state to prevent fetching or decoding subsequent instructions until the hazard is cleared. Bubbling, on the other hand, complements stalling by inserting no-operation (NOP) instructions into the pipeline, creating "bubbles" that propagate through the stages and maintain the timing without executing meaningful work, which is particularly useful for propagating the stall effect downstream. These mechanisms are primarily applied to unresolved data hazards, such as read-after-write (RAW) dependencies, where an instruction requires a result from a prior instruction that has not yet completed its write-back (WB) stage. For instance, in a classic five-stage RISC pipeline (IF, ID, EX, MEM, WB), a load-use hazard occurs when a load instruction fetches data in the MEM stage, but the dependent instruction attempts to use it in the ID stage one cycle too early; the pipeline is stalled for one or two cycles by holding the ID stage and inserting a bubble until the data reaches WB and becomes available. Upon detection of such a hazard, the stall is triggered to ensure the dependent instruction does not proceed with incorrect operands. This approach preserves program correctness by enforcing proper data dependencies, though it introduces idle cycles that reduce overall throughput. The primary cost of stalling and bubbling is an increase in average cycles per instruction (CPI), as each stall effectively adds latency without productive computation; for example, in a MIPS-like pipeline with frequent load instructions, stalling can elevate CPI from an ideal 1 to around 1.3 or higher depending on hazard frequency. While these methods guarantee serial correctness equivalent to non-pipelined execution, their limitations become evident in designs with frequent hazards, where repeated stalls degrade performance significantly, often motivating more advanced optimizations to minimize their use.

Mitigation Techniques

Operand Forwarding

Operand forwarding, also known as bypassing or data bypassing, is a hardware technique in pipelined processors that resolves read-after-write (RAW) data hazards by directly routing computed results from a later pipeline stage to the input of an earlier stage, thereby avoiding unnecessary stalls while the result awaits writing to the register file. This optimization enables dependent instructions to access required operands as soon as they are available, typically from the execute (EX) or memory (MEM) stages, without full pipeline bubbling. Implemented via dedicated forwarding paths, it forms a core component of modern CPU designs to maintain high instruction throughput. In a classic five-stage RISC pipeline—such as instruction fetch (IF), instruction decode (ID), execute (EX), memory access (MEM), and write-back (WB)—forwarding paths consist of multiplexers (muxes) positioned before the ALU inputs in the EX stage. These muxes select between values from the register file (read in ID) and forwarded data from the EX/MEM pipeline register (ALU result from the previous instruction's EX stage) or the MEM/WB pipeline register (ALU or memory result from two instructions prior). Full forwarding supports both paths for all ALU operations, while half forwarding might limit it to one operand or specific cases; universal forwarding extends this to additional sources like branch resolution units for broader coverage. Comparators in the forwarding unit check register indices (e.g., Rs and Rt fields) against those in prior instructions to generate control signals for the muxes, ensuring precise operand selection without altering program semantics. For RAW hazards, forwarding eliminates stalls in common scenarios. In a one-cycle dependency, such as an ADD instruction in EX producing a result needed by a subsequent SUB also entering EX, the ADD's ALU output is muxed directly from the EX/MEM boundary to the SUB's ALU input, allowing execution without delay. For a two-cycle dependency, where the consumer is separated by one unrelated instruction, the result forwards from the MEM/WB boundary to the EX input. This approach requires modest additional hardware—typically two 3-to-1 muxes per ALU operand and a small control logic block—but significantly reduces data hazard stalls in integer pipelines. Despite its effectiveness, operand forwarding cannot resolve all dependencies. Load-use hazards, where a load (LW) instruction's memory result is required in the immediate next instruction's EX stage, persist because the data emerges only after MEM; a mandatory one-cycle stall is inserted, with forwarding applicable only for subsequent uses. It also does not inherently mitigate write-after-read (WAR) or write-after-write (WAW) hazards, which arise from out-of-order value availability but are typically prevented in simple in-order pipelines by fixed issue rates. In a representative MIPS pipeline circuit, the forwarding unit comprises comparators decoding ID/EX.Rs/Rt against EX/MEM.Rd and MEM/WB.Rd; if matches occur and the prior instruction is non-branching, signals ForwardA and ForwardB route the appropriate values, bypassing the register file ports while preserving the WB stage for final commitment. This setup, visualized as muxes branching from pipeline latches to EX inputs, underscores the technique's efficiency in balancing hardware cost and performance. Operand forwarding emerged as a cornerstone of RISC architectures in the 1980s, first integrated in prototypes like Berkeley's RISC II (1982), where internal bypassing avoided bubbles in operand-dependent sequences. Early Stanford MIPS designs (1985) instead relied on compiler techniques for hazard avoidance, but hardware forwarding became ubiquitous in subsequent RISC implementations, including later MIPS processors, and is now standard in all pipelined CPUs.

Branch Prediction and Speculation

Branch prediction is a technique employed in pipelined processors to mitigate control hazards arising from conditional branch instructions by anticipating their outcome—taken or not taken—before resolution, thereby allowing the pipeline to continue fetching and executing instructions without interruption. In conjunction with speculative execution, this approach enables processors to provisionally process instructions along the predicted path, deferring commitment until the branch resolves, which significantly reduces idle cycles in deep pipelines. Static branch prediction employs fixed rules without runtime history, such as always predicting branches as not taken, which achieves approximately 60-70% accuracy for forward branches due to the prevalence of straight-line code execution in typical programs. Another variant, always taken, yields similar overall accuracy of 60-70% but performs better on loop-closing backward branches; delayed branching, where instructions following the branch are always executed regardless of outcome, simplifies hardware but limits applicability to architectures with compiler support for branch delay slots. Dynamic branch prediction leverages runtime information to adapt predictions, improving accuracy over static methods. The 1-bit saturating counter predictor, which flips its prediction after each outcome, achieves around 80-90% accuracy but suffers from oscillation in alternating patterns, as demonstrated in early benchmarks like the SPEC suite. The 2-bit saturating counter, introduced by Smith, uses a 2-bit state machine (00/01 predict not taken, 10/11 predict taken) that increments on taken outcomes and decrements otherwise, providing hysteresis against short-term fluctuations and boosting accuracy to 93-95% with modest table sizes. To capture correlations, two-level predictors employ a global branch history register (e.g., 12 bits recording recent outcomes) indexing a pattern history table of 2-bit counters per branch address, as proposed by Yeh and Patt, yielding up to 97% accuracy by distinguishing context-dependent behaviors. Tournament predictors combine multiple component predictors—such as local (per-branch history) and global (shared history)—using a meta-table of 2-bit selectors to choose the best performer for each branch, achieving over 97% accuracy in SPEC benchmarks with balanced hardware budgets. Speculative execution complements these predictors by fetching, decoding, and executing instructions along the predicted path while buffering results in a reorder buffer (ROB) until branch resolution; upon misprediction, the pipeline flushes speculative state and redirects to the correct path, enabling out-of-order processors to tolerate latencies. Branch misprediction penalties in modern deep pipelines range from 10-20 cycles, as seen in Intel Core processors where flushing 15-20 stages incurs significant throughput loss, though predictors exceeding 95% accuracy—common in contemporary designs—minimize the effective impact to under 1% of instructions. Advanced techniques address specific challenges: indirect branch predictors use target buffers or perceptron-based models for multi-target jumps, while return address stacks (RAS) provide near-perfect accuracy (>99%) for function returns by pushing call addresses and popping on returns, crucial in superscalar processors issuing multiple fetches per cycle to sustain high .

Architectural Design Solutions

Architectural designs in pipelined processors address hazards by incorporating hardware features that prevent conflicts and dependencies at the design stage, rather than relying on runtime interventions. One fundamental approach is resource separation, where critical components like caches and s are partitioned to enable parallel access without contention. For instance, standard processor architectures employ separate instruction caches (I-cache) and caches (D-cache) at the first level to eliminate structural hazards that would otherwise arise from simultaneous instruction fetches and accesses in the . This separation allows the fetch stage to access instructions independently of load/store operations, a necessity for high-performance machines including superscalar designs. Similarly, multi-port s mitigate structural hazards by supporting multiple simultaneous reads and writes; a three-port , for example, permits two operand reads and one write per cycle, accommodating the needs of multiple stages or execution units without stalling. Out-of-order execution represents a key architectural solution for data hazards, particularly read-after-write (RAW) dependencies, by dynamically rescheduling instructions based on operand availability rather than program order. , introduced in 1967 for the , achieves this through reservation stations that buffer instructions and tag operands with register names, enabling execution as soon as data is ready without inserting stalls. This design uses a common data bus for result broadcasting and a reorder buffer to maintain architectural state, effectively resolving RAW hazards in floating-point units while supporting multiple arithmetic units. By decoupling issue from execution, out-of-order architectures like those based on Tomasulo increase and reduce pipeline bubbles from data dependencies. Very long instruction word (VLIW) and superscalar architectures further alleviate hazards through instruction bundling and multiple functional units, allowing parallel execution to mask latencies and reduce structural conflicts. In VLIW designs, the packs multiple independent operations into a single wide instruction word, which is dispatched to dedicated functional units, thereby avoiding by statically scheduling around potential hazards. Superscalar processors extend this dynamically, issuing multiple instructions per cycle to replicated execution units such as arithmetic logic units (ALUs), which minimizes structural hazards by providing sufficient hardware resources for concurrent operations. For example, equipping a processor with multiple ALUs enables simultaneous computations, distributing workload and preventing stalls from unit unavailability. Deep pipelining introduces trade-offs in hazard management, as increasing the number of stages amplifies the penalty from mispredictions and dependencies but enables higher clock frequencies for overall throughput gains. The Intel Pentium 4's NetBurst architecture, with up to 31 stages, prioritized clock speeds exceeding 3 GHz by shortening per-stage logic, yet this depth exacerbated control and hazard recovery times, often requiring 20+ cycles for mispredictions. In contrast, modern processors like those in the series typically use 14-20 stages, balancing hazard exposure with power efficiency and achieving better despite lower peak clocks around 4-5 GHz. This shallower approach reduces the cumulative latency of hazard flushes, though it demands sophisticated front-end designs to sustain high issue widths.

References

  1. https://www.cs.umd.edu/~meesh/411/CA-online/chapter/pipeline-hazards/index.html
  2. https://people.duke.edu/~tkb13/courses/ece250-2017su/slides/12-pipelining.pdf
  3. https://www.cise.ufl.edu/~mssz/CompOrg/CDA-pipe.html
  4. https://www2.seas.gwu.edu/~bhagiweb/cs211/lectures/pipeline
  5. https://www.engr.colostate.edu/~sudeep/wp-content/uploads/CD4.15-P374493.pdf
  6. https://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-529.pdf
  7. https://people.duke.edu/~tkb13/courses/ece250-2017fa/slides/12-pipelining.pdf
  8. https://www.cs.umd.edu/~meesh/411/CA-online/chapter/pipelining-mips-implementation/index.html
  9. https://www.icsa.inf.ed.ac.uk/cgi-bin/hase/dlx-scb-m.pl?/depend-t.html
  10. https://www.ic.unicamp.br/~cortes/mo401/slides/ap_C_v4.pdf
  11. https://www.sciencedirect.com/topics/computer-science/control-hazard
  12. http://www.cs.umd.edu/~meesh/411/CA-online/chapter/handling-control-hazards/index.html
  13. https://www.sciencedirect.com/science/article/pii/B9780123944245000070
  14. https://people.engr.tamu.edu/djimenez/taco/utsa-www/cs5513-fall07/lecture4.html
  15. https://www.doc.ic.ac.uk/~phjk/AdvancedCompArchitecture/Lectures/pdfs/Ch03-part1-BranchPrediction.pdf
  16. https://www.sciencedirect.com/science/article/pii/B9780128000564000078
  17. https://www.cs.umd.edu/~meesh/411/CA-online/chapter/handling-data-hazards/index.html
  18. https://www.cs.virginia.edu/~evans/greatworks/tomasulo.pdf
  19. https://www.cs.umd.edu/~meesh/411/CA-online/chapter/handling-control-hazards/index.html
  20. https://www.cs.utexas.edu/~byoung/cs429/slides16-pipeline3.pdf
  21. https://www.cs.princeton.edu/courses/archive/fall15/cos375/lectures/10-Pipeline-3x1.pdf
  22. https://faculty-web.msoe.edu/meier/ce1921/slidesets/pipelining.pdf
  23. https://people.eecs.berkeley.edu/~randy/Courses/CS252.S96/Lecture07.pdf
  24. https://www.cs.ucf.edu/courses/cda5106/summer02/papers/risc-patterson.pdf
  25. https://users.cs.duke.edu/~lkw34/papers/yeh-2level_brpred-micro1991.pdf
  26. https://www.ece.ucdavis.edu/~akella/270W05/mcfarling93combining.pdf
  27. https://marxify.pages.dev/720584_51bf3902a67f435798652b7873ffd67b.pdf
  28. https://www.engineering.iastate.edu/~zzhang/courses/cpre585-f03/reading/smith-isca81-bpred.pdf
  29. https://www.researchgate.net/publication/257668178_Data_cache_organization_for_accurate_timing_analysis
  30. https://dl.acm.org/doi/pdf/10.1145/165123.165154
  31. https://dl.acm.org/doi/10.1145/1838002.1838083
  32. https://ieeexplore.ieee.org/document/5392028/
  33. https://dl.acm.org/doi/pdf/10.1145/74926.74935
  34. https://dl.acm.org/doi/pdf/10.1145/384286.264156
  35. https://www.sciencedirect.com/topics/computer-science/deep-pipeline
  36. https://www.cs.cmu.edu/afs/cs/academic/class/15740-f03/public/doc/discussions/uniprocessors/technology/deep-pipelines-isca02.pdf
  37. https://dl.acm.org/doi/pdf/10.1145/1044823.1044824
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.