Data Hazard
   HOME

TheInfoList



OR:

In the domain of
central processing unit A central processing unit (CPU), also called a central processor, main processor or just processor, is the electronic circuitry that executes instructions comprising a computer program. The CPU performs basic arithmetic, logic, controlling, an ...
(CPU)
design A design is a plan or specification for the construction of an object or system or for the implementation of an activity or process or the result of that plan or specification in the form of a prototype, product, or process. The verb ''to design'' ...
, hazards are problems with the
instruction pipeline In computer engineering, instruction pipelining or ILP is a technique for implementing instruction-level parallelism within a single processor. Pipelining attempts to keep every part of the processor busy with some instruction by dividing inco ...
in CPU
microarchitecture In computer engineering, microarchitecture, also called computer organization and sometimes abbreviated as µarch or uarch, is the way a given instruction set architecture (ISA) is implemented in a particular processor. A given ISA may be impl ...
s 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 (branching hazards). There are several methods used to deal with hazards, including
pipeline stall In the design of pipelined computer processors, a pipeline stall is a delay in execution of an instruction in order to resolve a hazard. Details In a standard five-stage pipeline, during the decoding stage, the control unit will determine whe ...
s/pipeline bubbling,
operand forwarding Operand forwarding (or data forwarding) is an optimization in pipelined CPUs to limit performance deficits which occur due to pipeline stalls. A data hazard can lead to a pipeline stall when the current operation has to wait for the results of ...
, and in the case of
out-of-order execution In computer engineering, out-of-order execution (or more formally dynamic execution) is a paradigm used in most high-performance central processing units to make use of instruction cycles that would otherwise be wasted. In this paradigm, a proce ...
, the
scoreboarding Scoreboarding is a centralized method, first used in the CDC 6600 computer, for dynamically scheduling instructions so that they can execute out of order when there are no conflicts and the hardware is available. In a scoreboard, the data dependen ...
method and the
Tomasulo algorithm Tomasulo's algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units. It was developed by Robert Tomasulo at IBM in ...
.


Background

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
microarchitecture In computer engineering, microarchitecture, also called computer organization and sometimes abbreviated as µarch or uarch, is the way a given instruction set architecture (ISA) is implemented in a particular processor. A given ISA may be impl ...
s, 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


Data hazards

Data hazards occur when instructions that exhibit
data dependence A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is c ...
modify data in different stages of a pipeline. Ignoring potential data hazards can result in
race condition A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...
s (also termed race hazards). There are three situations in which a data hazard can occur: # read after write (RAW), a ''true dependency'' # write after read (WAR), an ''anti-dependency'' # write after write (WAW), an ''output dependency'' Read after read (RAR) is not a hazard case. Consider two instructions and , with occurring before in program order.


Read after write (RAW)

( tries to read a source before writes to it) A read after write (RAW) 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 Pipeline may refer to: Electronics, computers and computing * Pipeline (computing), a chain of data-processing stages or a CPU optimization found on ** Instruction pipelining, a technique for implementing instruction-level parallelism within a s ...
, 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)

( tries to write a destination before it is read by ) A write after read (WAR) 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 (i.e., with concurrent execution), 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)

( tries to write an operand before it is written by ) A write after write (WAW) data hazard may occur in a concurrent execution environment.


=Example

= For example: i1. R2 <- R4 + R7 i2. R2 <- R1 + R3 The write back (WB) of must be delayed until finishes executing.


Structural hazards

A structural hazard occurs when two (or more) 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 (Arithmetic Logic Unit). One solution to such resource hazard is to increase available resources, such as having multiple ports into main memory and multiple ALU (Arithmetic Logic Unit) 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 (s) 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 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 (RAW) dependency is encountered, guaranteed to increase latency, or * use
out-of-order execution In computer engineering, out-of-order execution (or more formally dynamic execution) is a paradigm used in most high-performance central processing units to make use of instruction cycles that would otherwise be wasted. In this paradigm, a proce ...
to potentially prevent the need for pipeline bubbles * use ''
operand forwarding Operand forwarding (or data forwarding) is an optimization in pipelined CPUs to limit performance deficits which occur due to pipeline stalls. A data hazard can lead to a pipeline stall when the current operation has to wait for the results of ...
'' to use data from later stages in the pipeline In the case of
out-of-order execution In computer engineering, out-of-order execution (or more formally dynamic execution) is a paradigm used in most high-performance central processing units to make use of instruction cycles that would otherwise be wasted. In this paradigm, a proce ...
, the algorithm used can be: *
scoreboarding Scoreboarding is a centralized method, first used in the CDC 6600 computer, for dynamically scheduling instructions so that they can execute out of order when there are no conflicts and the hardware is available. In a scoreboard, the data dependen ...
, in which case a ''pipeline bubble'' is needed only when there is no functional unit available * the
Tomasulo algorithm Tomasulo's algorithm is a computer architecture hardware algorithm for dynamic scheduling of instructions that allows out-of-order execution and enables more efficient use of multiple execution units. It was developed by Robert Tomasulo at IBM in ...
, which uses
register renaming In computer architecture, register renaming is a technique that abstracts logical registers from physical registers. Every logical register has a set of physical registers associated with it. When a machine language instruction refers to a particu ...
, allowing continual issuing of instructions The task of removing data dependencies can be delegated to the compiler, which can fill in an appropriate number of instructions between dependent instructions to ensure correct operation, or re-order instructions where possible.


Operand forwarding


Examples

: ''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)

To avoid control hazards microarchitectures can: * insert a ''pipeline bubble'' (discussed above), guaranteed to increase latency, or * use
branch prediction In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow ...
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

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.


See also

*
Feed forward (control) A feed forward (sometimes written feedforward) is an element or pathway within a control system that passes a controlling signal from a source in its external environment to a load elsewhere in its external environment. This is often a command ...
*
Register renaming In computer architecture, register renaming is a technique that abstracts logical registers from physical registers. Every logical register has a set of physical registers associated with it. When a machine language instruction refers to a particu ...
*
Data dependency A data dependency in computer science is a situation in which a program statement (instruction) refers to the data of a preceding statement. In compiler theory, the technique used to discover data dependencies among statements (or instructions) is c ...
*
Hazard (logic) In digital logic, a hazard is an undesirable effect caused by either a deficiency in the system or external influences in both synchronous circuit, synchronous and asynchronous circuits. Logic hazards are manifestations of a problem in which cha ...
*
Hazard pointer In a Thread (computer science), multithreaded computer science, computing environment, hazard pointers are one approach to solving the problems posed by dynamic memory management of the nodes in a non-blocking algorithm, lock-free data structure. T ...
* *
Speculative execution Speculative execution is an optimization technique where a computer system performs some task that may not be needed. Work is done before it is known whether it is actually needed, so as to prevent a delay that would have to be incurred by doing t ...
*
Branch delay slot In computer architecture, a delay slot is an instruction slot being executed without the effects of a preceding instruction. The most common form is a single arbitrary instruction located immediately after a branch instruction on a RISC or DSP a ...
*
Branch predication In computer science, predication is an architectural feature that provides an alternative to conditional transfer of control, as implemented by conditional branch machine instructions. Predication works by having conditional (''predicated'') non- ...
*
Branch predictor In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e.g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow ...
*
Race condition A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...


References


General

* * *


External links

* * {{DEFAULTSORT:Hazard (Computer Architecture) Instruction processing