Pipeline Hazards in the Instruction Pipeline

In 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, and can potentially lead to incorrect computation results. Three common types of hazards are data hazards, structural hazards, and control hazards (branch hazards).

Several methods are used to deal with hazards, including pipeline stalls/bubbles, operand forwarding, and, in the case of out-of-order execution, scoreboarding and Tomasulo's algorithm.

In a pipelined processor, instructions execute in several stages, so that at any given moment several instructions are being processed at different pipeline stages, such as fetch and execute. There are many different microarchitectures for instruction pipelining, and instructions may be executed out of order. A hazard arises when two or more such simultaneous (possibly out-of-order) instructions conflict.

Three classes of such hazards are distinguished:

• Structural hazards ( structural hazards ) — occur when the pipeline's hardware resources cannot be allocated among its individual stages to ensure it is fully loaded
• Data hazards ( data hazards ) — occur when there are dependencies between data in different instructions located in the pipeline.
• Control hazards ( control hazards or branching hazards ) — occur as a consequence of pipelining a branch instruction that changes the value of the program counter.

A structural hazard occurs when two (or more) instructions already in the pipeline require the same resource. As a result, the instructions must execute sequentially rather than in parallel at a given pipeline stage. Structural hazards are sometimes called resource hazards.

Example: A situation where several instructions are ready to execute, but there is only one ALU (arithmetic logic unit). One solution to this resource-shortage problem is to increase the available resources by providing several ports into main memory and several ALUs.

A control hazard occurs when the control logic incorrectly predicts which branch will be taken within the program, and, consequently, a sequence of instructions enters the pipeline that is subsequently discarded. The term “branch hazard” also refers to a control hazard.

Structural hazards ( structural hazards ) in the pipeline most often occur where the functional units directly responsible for computation are not fully pipelined, or their number is insufficient to execute an arbitrary combination of machine instructions loaded into the pipeline.

​

The figure shows a situation that results in a structural hazard. Here it is assumed that the processor has only one unit for performing the multiplication operation, executing this operation in two machine cycles and, accordingly, does not allow further subdivision into separate stages. A pipeline stage, in turn, has the duration of one machine cycle.

Two multiplication instructions with no data hazards between them are loaded into the pipeline in sequence, but combining the execution of these instructions at the direct-multiplication stage is impossible, since the multiplication unit cannot be shared between them. Therefore, for the second of the instructions, the pipeline stalls for one machine cycle.

To avoid such a stall, an additional multiplication unit may be added to the processor, or the existing one pipelined, or its speed increased (brought down to the duration of one pipeline cycle).

A pipeline stall , also called a pipeline break or pipeline stop , is a method for preventing data hazards, structural hazards, and branch hazards. As instructions are fetched, the control logic determines whether a hazard may/will occur. If so, the control logic inserts NOP operations into the pipeline. Thus, before the next instruction (which would cause a hazard) executes, the previous one will have had enough time to complete and prevent the hazard. If the number of NOP operations equals the number of pipeline stages, the processor is flushed of all instructions and can continue operating without hazards. All forms of stalling introduce a delay before the processor resumes execution.

A pipeline flush occurs when a branch instruction jumps to a new memory location, invalidating all preceding pipeline stages. These preceding stages are cleared, allowing the pipeline to continue operating from the new instruction specified by the branch instruction.

Several primary solutions and algorithms are used to address problems related to data hazards:

• Insert a data-processing block when a “read after write” (RAW) dependency is detected, which is guaranteed to increase latency, or
• Using out-of-order execution can potentially eliminate the need for pipeline “bubbles”.
• Use operand forwarding to use data from later stages of the data-processing pipeline.

In the case of out-of-order execution, the following approach may be used:

• scoreboarding , in which case a pipeline bubble is needed only when a functional unit is unavailable.
• Tomasulo's algorithm , which uses register renaming , allows instructions to be issued continuously.

The task of eliminating data dependencies can be delegated to the compiler, which can insert the appropriate number of NOP instructions between dependent instructions to ensure correct operation, or reorder instructions where possible.

In the following examples, computed values are shown in bold, while register numbers are not.

For example, to write the value 3 into register 1 (which already contains 6), 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

After execution, register 2 should contain the value 10. However, if i1 (writing 3 to register 1) does not completely leave the pipeline before i2 begins execution, this means that R1 does not contain the value 3 when i2 performs the addition. In that case, 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 commits/stores the result of the write operation to register 1. Therefore, when i2 reads the contents of register 1, register 1 still contains 6 , not 3 .

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

Applying forwarding in this example means that there is no wait for the output value of i1 to be committed/stored in register 1 (in this example, the output value is 3 ) before that value becomes available to the subsequent instruction (in this case, i2). As a result, i2 uses the correct (more up-to-date) value of register 1: the commit/store happens immediately, without pipelining.

With data forwarding enabled, the instruction decode/execute (ID/EX) stage of the pipeline now has two inputs: the value read from the specified register (in this example — the value 6 from register 1), and the new value of register 1 (in this example — the value 3 ), which is passed from the next instruction execute/memory-access stage (EX/MEM). Additional control logic is used to determine which input to use.

To prevent control hazards, microarchitectures may:

• insert a “bubble” into the pipeline (discussed above), which is guaranteed to increase latency , or
• Use branch prediction and, in effect, make educated guesses about which instructions should be inserted; in this case, a pipeline “bubble” will be needed only in the event of a misprediction.

If a branch causes a “bubble” in the pipeline after incorrect instructions have entered it, measures must be taken to prevent any effect of the incorrectly loaded instructions on the processor's state, except for the energy lost in processing them before it was discovered that they had been loaded incorrectly.

Control hazards ( control hazards ) — a type of pipeline hazard caused by the characteristics of pipelined execution of branch instructions.

Let i and j — be two machine instructions , with j following i in the program. j is said to depend on the branch from i when the decision as to whether j should execute or not is made based on the result obtained during the execution of i . That is, j depends on i via a branch if i – is a branch instruction.

The difficulty of pipelined execution of such code fragments lies in the fact that it is not known in advance which instruction's execution will begin as a result of the branch (i.e., whether it will occur or not). In the case of sequential (non-pipelined) execution, the branch decision is obtained before the next instruction is loaded into the execution unit. But in the pipelined model, the execution stages of different instructions overlap in time, i.e. the stage that directly computes the result of one instruction overlaps with the loading of the next, and so on, and it is impossible to know during this loading whether it is needed at all, since the result of the branch instruction has not yet been computed.

​

This situation is shown in the figure. For such a pipeline, executing a branch means stalling the pipeline for three clock cycles in order to flush the now-unneeded instructions and load the ones needed from the other branch of the program. Obviously, the more stages there are in the pipeline, and the farther the branch-address computation stage is from the beginning, the greater the performance loss will be.

Memory access latency is another factor developers should pay attention to, since latency can reduce performance. Different types of memory have different memory access times. Thus, by choosing an appropriate type of memory, developers can improve the performance of the pipelined datapath.