Hazard (computer architecture)
In the domain of central processing unit 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.
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
s 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 instructions conflict.Types
Data hazards
Data hazards occur when instructions that exhibit data dependence modify data in different stages of a pipeline. Ignoring potential data hazards can result in race conditions. There are three situations in which a data hazard can occur:- read after write, a true dependency
- write after read, an anti-dependency
- write after write, an output dependency
Read after write (RAW)
A read after write data hazard refers to a situation where an instruction refers to a result that has not yet been calculated or retrieved. This can occur because even though an instruction is executed after a prior instruction, the prior instruction has been processed only partly through the pipeline.Example
For example:i1. R2 <- R5 + R3
i2. R4 <- R2 + R3
The first instruction is calculating a value to be saved in register, and the second is going to use this value to compute a result for register. However, in a pipeline, when operands are fetched for the 2nd operation, the results from the first have not yet been saved, and hence a data dependency occurs.
A data dependency occurs with instruction, as it is dependent on the completion of instruction.
Write after read (WAR)
A write after read data hazard represents a problem with concurrent execution.Example
For example:i1. R4 <- R1 + R5
i2. R5 <- R1 + R2
In any situation with a chance that may finish before , it must be ensured that the result of register is not stored before has had a chance to fetch the operands.
Write after write (WAW)
A write after write data hazard may occur in a concurrent execution environment.Example
For example:i1. R2 <- R4 + R7
i2. R2 <- R1 + R3
The write back of must be delayed until finishes executing.
Structural hazards
A structural hazard occurs when two instructions that are already in pipeline need the same resource. The result is that instruction must be executed in series rather than parallel for a portion of pipeline. Structural hazards are sometime referred to as resource hazards.Example:
A situation in which multiple instructions are ready to enter the execute instruction phase and there is a single ALU. One solution to such resource hazard is to increase available resources, such as having multiple ports into main memory and multiple ALU units.
Control hazards (branch hazards or instruction hazards)
Control hazard occurs when the pipeline makes wrong decisions on branch prediction and therefore brings instructions into the pipeline that must subsequently be discarded. The term branch hazard also refers to a control hazard.Eliminating hazards
Generic
Pipeline bubbling
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 s into the pipeline. Thus, before the next instruction executes, the prior one will have had sufficient time to finish and prevent the hazard. If the number of s 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.
Data hazards
There are several main solutions and algorithms used to resolve data hazards:- insert a pipeline bubble whenever a read after write 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
- scoreboarding, in which case a pipeline bubble is needed only when there is no functional unit available
- the Tomasulo algorithm, which uses register renaming, allowing continual issuing of instructions
Operand forwarding
Examples
For example, to write the value 3 to register 1,, 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 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, 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 helps correct such errors by depending on the fact that the output of i1 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 before making that output available to the subsequent instruction. The effect is that i2 uses the correct value of Register 1: the commit/store was made immediately and not pipelined.
With forwarding enabled, the Instruction Decode/Execution stage of the pipeline now has two inputs: the value read from the register specified, and the new value of Register 1 which is sent from the next stage Instruction Execute/Memory Access. Added control logic is used to determine which input to use.
Control hazards (branch hazards)
To avoid control hazards microarchitectures can:- insert a pipeline bubble, 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