Hazard (computer architecture)

Problems with the instruction pipeline in central processing unit (CPU) microarchitectures

This article needs additional citations for verification. Please help improve this article by adding 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 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 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

[edit]

Further information: Instruction pipelining

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

[edit]

### Structural hazards

[edit]

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 sometimes 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)

[edit]

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.

## Pipeline bubbling

[edit]

Main article: Bubble (computing)

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.[3][4]

### Data hazards

[edit]

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:

* 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

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

[edit]

Main article: Operand forwarding

#### Examples

[edit]

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)

[edit]

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

[edit]

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]

## See also

[edit]

* Feed forward (control)
* Register renaming
* Data dependency
* Control dependency
* Hazard (logic)
* Hazard pointer
* Classic RISC pipeline § Hazards
* Speculative execution
* Branch delay slot
* Branch predication
* Branch predictor
* Race condition

## References

[edit]

1. ^ Patterson & Hennessy 2009, p. 335.
2. ^ Patterson & Hennessy 2009, pp. 335–343.
3. ^ "Branch Prediction Schemes". cs.iastate.edu. 2001-04-06. Retrieved 2014-07-19.
4. ^ "Data and Control Hazards". classes.soe.ucsc.edu. 2004-02-23. Retrieved 2014-07-19.
5. ^ Cheng, Ching-Hwa (2012-12-27). "Design Example of Useful Memory Latency for Developing a Hazard Preventive Pipeline High-Performance Embedded-Microprocessor". VLSI Design. 2013: 1–10\. doi:10.1155/2013/425105.

### General

[edit]

* Patterson, David; Hennessy, John (2009). Computer Organization and Design (4th ed.). Morgan Kaufmann. ISBN 978-0-12-374493-7.
* Patterson, David; Hennessy, John (2011). Computer Architecture: A Quantitative Approach (5th ed.). Morgan Kaufmann. ISBN 978-0-12-383872-8.
* Shen, John P.; Lipasti, Mikko H. (2013) [2004]. "2.2.3.2 Identication of Pipeline Hazards". Modern Processor Design: Fundamentals of Superscalar Processors. Waveland Press. pp. 73–78\. ISBN 9781478610762.

## External links

[edit]

* "Automatic Pipelining from Transactional Datapath Specifications" (PDF). Retrieved 23 July 2014.
* Tulsen, Dean (18 January 2005). "Pipeline hazards" (PDF).

* v
* t
* e

Processor technologies

Models|

* Abstract machine
* Stored-program computer
* Finite-state machine
* with datapath
* Hierarchical
* Deterministic finite automaton
* Queue automaton
* Cellular automaton
* Quantum cellular automaton
* Turing machine
* Alternating Turing machine
* Universal
* Post–Turing
* Quantum
* Nondeterministic Turing machine
* Probabilistic Turing machine
* Hypercomputation
* Zeno machine
* Belt machine
* Stack machine
* Register machines
* Counter
* Pointer
* Random-access
* Random-access stored program

Architecture|

* Microarchitecture
* Von Neumann
* Harvard
* modified
* Dataflow
* Transport-triggered
* Cellular
* Endianness
* Memory access
* NUMA
* HUMA
* Load–store
* Register/memory
* Cache hierarchy
* Memory hierarchy
* Virtual memory
* Secondary storage
* Heterogeneous
* Fabric
* Multiprocessing
* Cognitive
* Neuromorphic

Instruction set
architectures|

| Types|

* Orthogonal instruction set
* CISC
* RISC
* Application-specific
* EDGE
* TRIPS
* VLIW
* EPIC
* MISC
* OISC
* NISC
* ZISC
* VISC architecture
* Quantum computing
* Comparison
* Addressing modes

|

Instruction
sets|

* Motorola 68000 series
* VAX
* PDP-11
* x86
* ARM
* Stanford MIPS
* MIPS
* MIPS-X
* Power
* POWER
* PowerPC
* Power ISA
* Clipper architecture
* SPARC
* SuperH
* DEC Alpha
* ETRAX CRIS
* M32R
* Unicore
* Itanium
* OpenRISC
* RISC-V
* MicroBlaze
* LMC
* System/3x0
* S/360
* S/370
* S/390
* z/Architecture
* Tilera ISA
* VISC architecture
* Epiphany architecture
* Others

Execution|

| Instruction pipelining|

* Pipeline stall
* Operand forwarding
* Classic RISC pipeline

|

Hazards|

* Data dependency
* Structural
* Control
* False sharing

Out-of-order|

* Scoreboarding
* Tomasulo's algorithm
* Reservation station
* Re-order buffer
* Register renaming
* Wide-issue

Speculative|

* Branch prediction
* Memory dependence prediction

Parallelism|

| Level|

* Bit
* Bit-serial
* Word
* Instruction
* Pipelining
* Scalar
* Superscalar
* Task
* Thread
* Process
* Data
* Vector
* Memory
* Distributed

|

Multithreading|

* Temporal
* Simultaneous
* Hyperthreading
* Simultaneous and heterogenous
* Speculative
* Preemptive
* Cooperative

Flynn's taxonomy|

* SISD
* SIMD
* Array processing (SIMT)
* Pipelined processing
* Associative processing
* SWAR
* MISD
* MIMD
* SPMD

Processor
performance|

* Transistor count
* Instructions per cycle (IPC)
* Cycles per instruction (CPI)
* Instructions per second (IPS)
* Floating-point operations per second (FLOPS)
* Transactions per second (TPS)
* Synaptic updates per second (SUPS)
* Performance per watt (PPW)
* Cache performance metrics
* Computer performance by orders of magnitude

Types|

* Central processing unit (CPU)
* Graphics processing unit (GPU)
* GPGPU
* Vector
* Barrel
* Stream
* Tile processor
* Coprocessor
* PAL
* ASIC
* FPGA
* FPOA
* CPLD
* Multi-chip module (MCM)
* System in a package (SiP)
* Package on a package (PoP)

| By application|

* Embedded system
* Microprocessor
* Microcontroller
* Mobile
* Ultra-low-voltage
* ASIP
* Soft microprocessor

|

Systems
on chip|

* System on a chip (SoC)
* Multiprocessor (MPSoC)
* Cypress PSoC
* Network on a chip (NoC)

Hardware
accelerators|

* Coprocessor
* AI accelerator
* Graphics processing unit (GPU)
* Image processor
* Vision processing unit (VPU)
* Physics processing unit (PPU)
* Digital signal processor (DSP)
* Tensor Processing Unit (TPU)
* Secure cryptoprocessor
* Network processor
* Baseband processor

Word size|

* 1-bit
* 4-bit
* 8-bit
* 12-bit
* 15-bit
* 16-bit
* 24-bit
* 32-bit
* 48-bit
* 64-bit
* 128-bit
* 256-bit
* 512-bit
* bit slicing
* others
* variable

Core count|

* Single-core
* Multi-core
* Manycore
* Heterogeneous architecture

Components|

* Core
* Cache
* CPU cache
* Scratchpad memory
* Data cache
* Instruction cache
* replacement policies
* coherence
* Bus
* Clock rate
* Clock signal
* FIFO

| Functional
units|

* Arithmetic logic unit (ALU)
* Address generation unit (AGU)
* Floating-point unit (FPU)
* Memory management unit (MMU)
* Load–store unit
* Translation lookaside buffer (TLB)
* Branch predictor
* Branch target predictor
* Integrated memory controller (IMC)
* Memory management unit
* Instruction decoder

|

Logic|

* Combinational
* Sequential
* Glue
* Logic gate
* Quantum
* Array

Registers|

* Processor register
* Status register
* Stack register
* Register file
* Memory buffer
* Memory address register
* Program counter

Control unit|

* Hardwired control unit
* Instruction unit
* Data buffer
* Write buffer
* Microcode ROM
* Counter

Datapath|

* Multiplexer
* Demultiplexer
* Adder
* Multiplier
* CPU
* Binary decoder
* Address decoder
* Sum-addressed decoder
* Barrel shifter

Circuitry|

* Integrated circuit
* 3D
* Mixed-signal
* Power management
* Boolean
* Digital
* Analog
* Quantum
* Switch

Power
management|

* PMU
* APM
* ACPI
* Dynamic frequency scaling
* Dynamic voltage scaling
* Clock gating
* Performance per watt (PPW)

Related|

* History of general-purpose CPUs
* Microprocessor chronology
* Processor design
* Digital electronics
* Hardware security module
* Semiconductor device fabrication
* Tick–tock model
* Pin grid array
* Chip carrier

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template