Dependencies and Hazards - The Beard Sage

Control Dependencies

A control dependence determines the ordering of an instruction, $i$ , with respect to a branch instruction so that instruction $i$ is executed in correct program order and only when it should be. All subsequent instructions after a branch instruction have a control dependence on that branch instruction.

if p1 {
    S1;
};
if p2 {
    S2;
}

$\texttt{S1}$ is control dependent on $\texttt{p1}$ , and $\texttt{S2}$ is control dependent on $\texttt{p2}$ but not on $\texttt{p1}$ .

Two constraints are imposed by control dependences

An instruction that is control dependent on a branch cannot be moved before the branch so that its execution is no longer controlled by the branch.
An instruction that is not control dependent on a branch cannot be moved after the branch so that its execution is controlled by the branch.

Generally, $20\%$ of all instructions are branch/jump and slightly more than $50\%$ of branch/jump instructions are taken. If the correct branch/jump target is computed at $n$ th stage of a pipeline

$\begin{equation*} \text{CPI} = 1 + 0.5*0.2 * n \end{equation*}$

Data Dependencies

An instruction $j$ is data dependent on instruction $i$ if either of the following holds:

Instruction $i$ produces a result that may be used by instruction $j$ .
Instruction $j$ is data dependent on instruction $k$ , and instruction $k$ is data dependent on instruction $i$ (chain of dependencies).

A dependence within a single instruction (such as $\texttt{ADDD R1,R1,R1}$ ) is not considered a dependence.

Read after Write (RAW/Flow/True)

The following code has a RAW dependence on R1

ADD R1, R2, R3
SUB R7, R1, R8

If two instructions are data dependent, they must execute in order and cannot execute simultaneously or be completely overlapped.

Dependences are a property of programs. Whether a given dependence results in an actual hazard being detected and whether that hazard actually causes a stall are properties of the pipeline organization.

A data dependence conveys three things

the possibility of a hazard
the order in which results must be calculated
an upper bound on how much parallelism can possibly be exploited

A data dependence can be overcome in two different ways

maintaining the dependence but avoiding a hazard
eliminating a dependence by transforming the code

Name Dependencies

A name dependence occurs when two instructions use the same register or memory location, called a name, but there is no flow of data between the instructions associated with that name.

Write after Read (WAR/Anti/False/Name)

An antidependence between instruction $i$ and instruction $j$ occurs when instruction $j$ writes a register or memory location that instruction $i$ reads. The original ordering must be preserved to ensure that $i$ reads the correct value.

The following code has a WAR dependence on R1.

SUB R7, R1, R8
MUL R1, R5, R6

Write after Write (WAW/Output/False/Name)

An output dependence occurs when instruction $i$ and instruction $j$ write the same register or memory location. The ordering between the instructions must be preserved to ensure that the value finally written corresponds to instruction $j$ .

The following code has a WAW dependence on R1.

ADD R1, R2, R3
MUL R1, R5, R6

Because a name dependence is not a true dependence, instructions involved in a name dependence can execute simultaneously or be reordered, if the name (register number or memory location) used in the instructions is changed so the instructions do not conflict.

This renaming can be more easily done for register operands, where it is called register renaming. Register renaming can be done either statically by a compiler or dynamically by the hardware.

Hazards

There are situations in pipelining when the next instruction cannot execute in the following clock cycle. These events are called hazards. Hazards in pipelines can make it necessary to stall the pipeline.

$\begin{equation*} \text{Pipeline CPI} = \text{Ideal pipeline CPI} + \text{Structural stalls} + \text{Data hazard stalls} + \text{Control stalls} \end{equation*}$

Structural Hazard

When a planned instruction cannot execute in the proper clock cycle because the hardware does not support the combination of instructions that are set to execute. Each logical component of the datapath – such as instruction memory, register read ports, ALU, data memory, and register write port – can be used only within a single pipeline stage.

For example, a processor may have only one register-file write port, but under certain circumstances, the pipeline might want to perform two writes in a clock cycle.

LW  R0, 0(R0)
ADD R1, R0, R0

When a sequence of instructions encounters this hazard, the pipeline will stall one of the instructions until the required unit is available. Such stalls will increase the CPI from its usual ideal value of $1$ .

Structural hazards can be avoided by providing a separate memory access for instructions, either by splitting the cache into separate instruction and data caches or by using instruction buffers.

Data Hazard

By convention, the hazards are named by the ordering in the program that must be preserved by the pipeline. Consider two instructions $i$ and $j$ , with $i$ preceding $j$ in program order. The possible data hazards are

RAW (read after write)

$j$ tries to read a source before $i$ writes it, so $j$ incorrectly gets the old value. This hazard is the most common type and corresponds to a true data dependence. Program order must be preserved to ensure that $j$ receives the value from $i$ .

WAW (write after write)

$j$ tries to write an operand before it is written by $i$ . The writes end up being performed in the wrong order, leaving the value written by $i$ rather than the value written by $j$ in the destination. This hazard corresponds to an output dependence. WAW hazards are present only in pipelines that write in more than one pipe stage or allow an instruction to proceed even when a previous instruction is stalled.

WAR (write after read)

$j$ tries to write a destination before it is read by $i$ , so $i$ incorrectly gets the new value. This hazard arises from an antidependence (or name dependence). A WAR hazard occurs either when there are some instructions that write results early in the instruction pipeline and other instructions that read a source late in the pipeline, or when instructions are reordered.

Control Hazard (Branch Hazard)

When the proper instruction cannot execute in the proper pipeline clock cycle because the instruction that was fetched is not the one that is needed; that is, the flow of instruction addresses is not what the pipeline expected.

Control Hazards can be avoided by using prediction to handle branches. One simple approach is to predict that branches will always be not taken. When the prediction is correct, the pipeline proceeds at full speed. Only when the branches are taken does the pipeline stall.

A more sophisticated version of branch prediction would have some branches predicted as taken and some as not taken. One popular approach to dynamic prediction of branches is keeping a history for each branch as taken or not taken, and then using the recent past behavior to predict the future. When the guess is wrong, the pipeline control must ensure that the instructions following the wrongly guessed branch have no effect and must restart the pipeline from the proper branch address.

Hazards and pipelining

For modern pipelines, structural hazards usually revolve around the floating-point unit, which may not be fully pipelined, while control hazards are usually more of a problem in integer programs, which tend to have higher branch frequencies as well as less predictable branches}. Data hazards can be performance bottlenecks in both integer and floating-point programs. Often it is easier to deal with data hazards in floating-point programs because the lower branch frequency and more regular memory access patterns allow the compiler to try to schedule instructions to avoid hazards. It is more difficult to perform such optimizations in integer programs that have less regular memory access, involving more use of pointers.