Hazard (computer architecture)

In the domain of 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,[1] and can potentially lead to incorrect computation results. Three common types of hazards are data hazards, structural hazards, and control flow hazards (branching hazards).[2]

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

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 microarchitectures, 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 modify data in different stages of a pipeline. Ignoring potential data hazards can result in race conditions (also termed race hazards). There are three situations in which a data hazard can occur:

  1. read after write (RAW), a true dependency
  2. write after read (WAR), an anti-dependency
  3. write after write (WAW), an output dependency

Consider two instructions i1 and i2, with i1 occurring before i2 in program order.

Read after write (RAW)

(i2 tries to read a source before i1 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 <- R1 + R3
i2. R4 <- R2 + R3

The first instruction is calculating a value to be saved in register R2, and the second is going to use this value to compute a result for register R4. However, in a pipeline, when operands are fetched for the 2nd operation, the results from the first will not yet have been saved, and hence a data dependency occurs.

A data dependency occurs with instruction i2, as it is dependent on the completion of instruction i1.

Write after read (WAR)

(i2 tries to write a destination before it is read by i1) 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 i2 may finish before i1 (i.e., with concurrent execution), it must be ensured that the result of register R5 is not stored before i1 has had a chance to fetch the operands.

Write after write (WAW)

(i2 tries to write an operand before it is written by i1) 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 i2 must be delayed until i1 finishes executing.

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 canonical example is a single memory unit that is accessed both in the fetch stage where an instruction is retrieved from memory, and the memory stage where data is written and/or read from memory.[3] They can often be resolved by separating the component into orthogonal units (such as separate caches) or bubbling the pipeline.

Control hazards (branch hazards)

Branching hazards (also termed control hazards) occur with branches. On many instruction pipeline microarchitectures, the processor will not know the outcome of the branch when it needs to insert a new instruction into the pipeline (normally the fetch stage).

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 no 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 of NOPs 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.[4][5]

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 to potentially prevent the need for pipeline bubbles
  • use operand forwarding to use data from later stages in the pipeline

In the case of out-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 of NOP 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 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.[6]

See also

References

  1. ^ Patterson & Hennessy 2009, p. 335.
  2. ^ Patterson & Hennessy 2009, pp. 335-343.
  3. ^ Patterson & Hennessy 2009, p. 336.
  4. ^ "Branch Prediction Schemes". cs.iastate.edu. 2001-04-06. Retrieved 2014-07-19. 
  5. ^ "Data and Control Hazards". classes.soe.ucsc.edu. 2004-02-23. Retrieved 2014-07-19. 
  6. ^ "Design Example of Useful Memory Latency for Developing a Hazard Preventive Pipeline High-Performance Embedded-Microprocessor". hindawi.com. 2012-12-27. Retrieved 2014-07-29. 

External links

Hazard

See also: Hazard

English

English Wikipedia has an article on:
Wikipedia

Etymology

From Old French hasart (a game of dice) (noun), hasarder (verb), probably from Arabic اَلزَّهْر (az-zahr, the dice). Compare Spanish azar, Portuguese azar.

Pronunciation

Noun

hazard (countable and uncountable, plural hazards)

  1. (historical) A type of game played with dice. [from 14th c.]
  2. Chance. [from 16th c.]
    • c. 1597, William Shakespeare, Richard III, act 5, scene 4:
      I will stand the hazard of the die.
    • 2006 May 20, John Patterson, The Guardian:
      I see animated movies are now managing, by hazard or design, to reflect our contemporary reality more accurately than live-action movies.
  3. The chance of suffering harm; danger, peril, risk of loss. [from 16th c.]
    He encountered the enemy at the hazard of his reputation and life.
    • (Can we date this quote?) Rogers
      Men are led on from one stage of life to another in a condition of the utmost hazard.
    • 1599, Wm. Shakespeare, The Tragedy of Julius Caesar:
      Why, now, blow wind, swell billow, and swim bark! The storm is up and all is on the hazard.
    • 1749, Henry Fielding, The History of Tom Jones, a Foundling
      He then launched forth into a panegyric on Allworthy's goodness; into the highest encomiums on his friendship; and concluded by saying, he should never forgive his brother for having put the place which he bore in that friendship to a hazard.
    • 2006, Edwin Black, chapter 1, in Internal Combustion[1]:
      If successful, Edison and Ford—in 1914—would move society away from the ever more expensive and then universally known killing hazards of gasoline cars:  [] .
    • 2009 December 27, Barbara Ellen, The Guardian:
      Quite apart from the gruesome road hazards, snow is awful even when you don't have to travel.
  4. An obstacle or other feature which causes risk or danger; originally in sports, and now applied more generally. [from 19th c.]
    The video game involves guiding a character on a skateboard past all kinds of hazards.
  5. (golf) A sand or water obstacle on a golf course.
  6. (billiards) The act of potting a ball, whether the object ball (winning hazard) or the player's ball (losing hazard).
  7. (obsolete) Anything that is hazarded or risked, such as a stake in gambling.
    • c.1600?, William Shakespeare, The Merchant of Venice
      But if you please
      To shoot another arrow that self way
      Which you did shoot the first, I do not doubt,
      As I will watch the aim, or to find both
      Or bring your latter hazard back again
      And thankfully rest debtor for the first.

Hyponyms

Derived terms

Translations

Verb

hazard (third-person singular simple present hazards, present participle hazarding, simple past and past participle hazarded)

  1. To expose to chance; to take a risk.
    • (Can we date this quote?) John Clarke
      Men hazard nothing by a course of evangelical obedience.
    • (Can we date this quote?) Fuller
      He hazards his neck to the halter.
  2. To risk (something); to venture, to incur, or bring on.
    • (Can we date this quote?) Shakespeare
      I hazarded the loss of whom I loved.
    • (Can we date this quote?) Landor
      They hazard to cut their feet.
    I'll hazard a guess.

Translations


Czech

Etymology

Borrowed from German [Term?], from Old French hasart.[1]

Pronunciation

Noun

hazard m

  1. gambling
  2. risk, gamble

Declension

References

  1. ^ hazard in Jiří Rejzek, Český etymologický slovník, electronic version, Leda, 2007

French

Noun

hazard m (plural hazards)

  1. Archaic spelling of hasard, chiefly used before 1800

Italian

Noun

hazard m (invariable)

  1. hazard lights (on a vehicle)

Middle French

Noun

hazard m (plural hazards)

  1. hazard; obstacle

Descendants


Polish

Pronunciation

Noun

hazard m inan

  1. (singular only) gambling
  2. (electronics) race condition

Declension


Serbo-Croatian

Pronunciation

  • IPA(key): /xǎzard/
  • Hyphenation: ha‧zard

Noun

hàzard m (Cyrillic spelling ха̀зард)

  1. gamble, gambling
  2. risk, hazard

Declension

Definitions by https://www.wiktionary.org/
 
Sorry Isnare.com is offline for a short while. Please check back after 5 minutes.