 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Hazard" computer architecture – news ·newspapers ·books ·scholar ·JSTOR(January 2014) (Learn how and when to remove this message) |
In the domain ofcentral processing unit (CPU)design,hazards are problems with theinstruction pipeline in CPUmicroarchitectures 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, includingpipeline stalls/pipeline bubbling,operand forwarding, and in the case ofout-of-order execution, thescoreboarding method and theTomasulo algorithm.
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 pipelinemicroarchitectures, and instructions may beexecuted out-of-order. A hazard occurs when two or more of these simultaneous (possibly out of order) instructions conflict.
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 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.
Bubbling the pipeline, also termed apipeline break orpipeline 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 insertsno 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 ofNOPs 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]
There are several main solutions and algorithms used to resolve data hazards:
In the case ofout-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 ofNOP instructions between dependent instructions to ensure correct operation, or re-order instructions where possible.
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 =6i1: R1 =3i2: R2 = R1 +7 =10
Following execution, register 2 should contain the value10. However, if i1 (write3 to register 1) does not fully exit the pipeline before i2 starts executing, it means that R1 does not contain the value3 when i2 performs its addition. In such an event, i2 adds7 to the old value of register 1 (6), and so register 2 contains13 instead, i.e.:
i0: R1 =6i2: R2 = R1 +7 =13i1: 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 contains6,not3.
Forwarding (described below) helps correct such errors by depending on the fact that the output of i1 (which is3) can be used by subsequent instructionsbefore the value3 is committed to/stored in Register 1.
Forwarding applied to the example means thatthere is no wait to commit/store the output of i1 in Register 1 (in this example, the output is3) 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, theInstruction Decode/Execution (ID/EX) stage of the pipeline now has two inputs: the value read from the register specified (in this example, the value6 from Register 1), and the new value of Register 1 (in this example, this value is3) which is sent from the next stageInstruction Execute/Memory Access (EX/MEM). Added control logic is used to determine which input to use.
To avoid control hazards microarchitectures can:
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.
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]