Hazard (computer architecture)
From Wikipedia, the free encyclopedia
In computer architecture, a hazard is a potential problem that can happen in a pipelined processor. It refers to the possibility of erroneous computation when a CPU tries to simultaneously execute multiple instructions which exhibit data dependence. There are typically three types of hazards: data hazards, branching hazards (control hazards), and structural hazards.
Instructions in a pipelined processor are performed in several stages, so that at any given time several instructions are being executed, and instructions may not be completed in the desired order.
A hazard occurs when two or more of these simultaneous (possibly out of order) instructions conflict.
Contents |
[edit] Data hazards
Data hazards occur when data is modified. Ignoring potential data hazards can result in race conditions (sometimes known as race hazards). There are three situations a data hazard can occur in:
- Read after Write (RAW) or True dependency: An operand is modified and read soon after. Because the first instruction may not have finished writing to the operand, the second instruction may use incorrect data.
- Write after Read (WAR) or Anti dependency: Read an operand and write soon after to that same operand. Because the write may have finished before the read, the read instruction may incorrectly get the new written value.
- Write after Write (WAW) or Output dependency: Two instructions that write to the same operand are performed. The first one issued may finish second, and therefore leave the operand with an incorrect data value.
The three hazards are easier to remember if you add "We should" before each acronym: For example: RAW should read as "We should RAW(Read After Write). If not, there will be a hazard."
[edit] RAW - Read After Write
A RAW Data Hazard refers to a situation where we refer to a result that has not yet been calculated, for example:
i1. R2 <- R1 + R3
i2. R4 <- R2 + R3
The 1st instruction is calculating a value to be saved in register 2, and the second is going to use this value to compute a result for register 4. However, in a pipeline, when we fetch the operands for the 2nd operation, the results from the 1st will not yet have been saved, and hence we have a data dependency.
We say that there is a data dependency with instruction 2, as it is dependent on the completion of instruction 1
[edit] WAR - Write After Read
A WAR Data Hazard represents a problem with concurrent execution, for example:
i1. r1 <- r2 + r3
i2. r3 <- r4 x r5
If we are in a situation that there is a chance that i2 may be completed before i1 (i.e. with concurrent execution) we must ensure that we do not store the result of register 3 before i1 has had a chance to fetch the operands.
[edit] WAW - Write After Write
A WAW Data Hazard is another situation which may occur in a Concurrent execution environment, for example:
i1. r2 <- r1 + r3
i2. r2 <- r4 x r7
We must delay the WB (Write Back) of i2 until the execution of i1
[edit] Structural hazards
A structural hazard occurs when a part of the processor's hardware is needed by two or more instructions at the same time. A structural hazard might occur, for instance, if a program were to execute a branch instruction followed by a computation instruction. Because they are executed in parallel, and because branching is typically slow (requiring a comparison, program counter-related computation, and writing to registers), it is quite possible (depending on architecture) that the computation instruction and the branch instruction will both require the ALU (arithmetic logic unit) at the same time.
[edit] Branch (control) hazards
Branching hazards (also known as control hazards) occur when the processor is told to branch - i.e., if a certain condition is true, then jump from one part of the instruction stream to another - not necessarily to the next instruction sequentially. In such a case, the processor cannot tell in advance whether it should process the next instruction (when it may instead have to move to a distant instruction).
This can result in the processor doing unwanted actions.
[edit] Eliminating hazards
We can delegate the task of removing data dependencies 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.
Other methods include on-chip solutions such as:
- Scoreboarding method
- Tomasulo's method
There are several established techniques for either preventing hazards from occurring, or working around them if they do.
- Bubbling the Pipeline
- Bubbling the pipeline (a technique also known as a pipeline break or pipeline stall) is a method for preventing data, structural, and branch hazards from occurring. As instructions are fetched, control logic determines whether a hazard could/will occur. If this is true, then the control logic inserts NOPs into the pipeline. Thus, before the next instruction (which would cause the hazard) is executed, the previous one will have had sufficient time to complete and prevent the hazard. If the number of NOPs is equal to the number of stages in the pipeline, the processor has been cleared of all instructions and can proceed free from hazards. This is called flushing the pipeline. All forms of stalling introduce a delay before the processor can resume execution.
[edit] Eliminating data hazards
- Forwarding
- NOTE: In the following examples, computed values are in bold, while Register numbers are not.
- Forwarding involves feeding output data into a previous stage of the pipeline. For instance, let's say we want 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.:
- Instruction 0: Register 1 = 6
- Instruction 1: Register 1 = 3
- Instruction 2: Register 2 = Register 1 + 7 = 10
- Following execution, register 2 should contain the value 10. However, if Instruction 1 (write 3 to register 1) does not completely exit the pipeline before the second instruction starts execution, it means that Register 1 does not contain the value 3 when Instruction 2 performs its addition. In such an event, Instruction 2 adds 7 to the old value of register 1 (6), and so register 2 would contain 13 instead, i.e:
- Instruction 0: Register 1 = 6
- Instruction 1: Register 1 = 3
- Instruction 2: Register 2 = Register 1 + 7 = 13
- This error occurs because Instruction 2 reads Register 1 before Instruction 1 has committed/stored the result of its write operation to Register 1. So when Instruction 2 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 Instruction 1 (which is 3) can be used by subsequent instructions before the value 3 is committed to/stored in Register 1.
- Forwarding is implemented by feeding back the output of an instruction into the previous stage(s) of the pipeline as soon as the output of that instruction is available. Forwarding applied to our example means that we do not wait to commit/store the output of Instruction 1 in Register 1 (in this example, the output is 3) before making that output available to the subsequent instruction (in this case, Instruction 2). The effect is that Instruction 2 uses the correct (the more recent) value of Register 1: the commit/store was made immediately and not pipelined.
- With forwarding enabled, the 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 (EX/MEM). Additional control logic is used to determine which input to use.
- See feed-forward.
- Register renaming
