Lecture 4: Control Hazards

This is lecture from my old class notes; it is more in line with my research point of view and less consistent with your text, but it is a good alternate introduction to branch prediction

Control Hazards

Instructions that disrupt the sequential flow of control present problems for pipelines. The effects of these instructions can't be exactly determined until late in the pipeline, so instruction fetch can't continue unless we do something special. The following types of instructions can introduce control hazards: Let's see how control hazards are manifested with an example:
	ld	r2, 0(r4)	// r2 := memory at r4
	ld	r3, 4(r4)	// r3 := memory at r4+4
	sub	r1, r2, r3	// r1 := r2 - r3
	beqz	r1, L1		// if r1 is not 0, goto L1
	ldi	r1, 1		// r1 := 1
L1:	not	r1, r1		// r1 := not r1
	st	r1, 0(r5)	// store r1 to memory at r5
This code has the effect of comparing two memory locations and storing the result of that comparison (1 for equal, 0 for not equal) to another location. If the beqz branch is taken, then a 1 is stored; otherwise, a 0 is stored. Let's assume we have a five-stage pipeline as in the last class.

   Cycles----->
 ________________________                        	Instructions 
|_IF_|_ID_|_EX_|_MM_|_WB_|_____				ld	r2, 0(r4)
     |_IF_|_ID_|_EX_|_MM_|_WB_|_________		ld	r3, 4(r4)
          |_IF_|_EX |_ID_|_EX_|_MM_|_WB_|____		sub	r1, r2, r3
               |_IF_|_EX |_ID_|_EX_|_MM_|_WB_|____	beqz	r1, L1
                    |_??_|_?? |_??_|_??_|_??_|_??_|____ ???
                         |_??_|_?? |_??_|_??_|_??_|_??_|???
beqz and sub instructions. Since the beqz instruction is a control instruction, there are two problems here: This little example illustrates the problem with branches in pipelines. Two unresolved issues in the pipeline cause control hazards: branch outcome (e.g., taken or not taken) and branch target (i.e. computing the next value for the PC register).

Solutions for Control Hazards

The following are solutions that have been proposed for mitigating aspects of control hazards:

Branch Prediction Strategies

Let's take a look at some strategies that have been proposed for conditional branch prediction. There are two issues: outcome prediction and target prediction. The most important aspect of a branch prediction strategy is accuracy. Higher levels of sophistication in branch prediction strategies lead to higher accuracy.

Branch Direction Prediction

Here are some ideas for branch outcome prediction (or "branch direction prediction"), the problem of predicting whether a conditional branch will be taken or not taken. Let's look at an example of how two-level prediction works. We'll assume a history length of 4. Consider the following C code:
int A[100][3];
int main () {
	int	i, j;

	for (i=0; i<100; i++) for (j=0; j<3; j++) A[i][j] = 0;
}

The history of the inner loop looks like this:
110110110110110110...
Let's assume the 4-bit history register for that branch is initialized to all bits 0. As we go through the loops, the history would shift through these combinations:
history		outcome
0000		1
0001		1
0011		0
0110		1
1101		1
1011		0
0110		1
1101		1
1011		0
0110		1
1101		1
1011		0
...
So the table of 16 counters for that branch would look like this: 0000 01 // only on warm-up 0001 01 // only on warm-up 0010 00 // never happens 0011 00 // never happens 0100 00 // never happens 0101 00 // never happens 0110 11 // predict the back edge taken 0111 00 // never happens 1000 00 // never happens 1001 00 // never happens 1010 00 // never happens 1011 00 // predict the back edge not taken 1100 00 // never happens 1101 11 // predict the back edge taken 1110 00 // never happens 1111 00 // never happens
What about the outer loop? To learn that loop's behavior perfectly, we would need a history length of at least 100. That would be impossible with two-level prediction. However, it doesn't hurt us much if we mispredict that branch once in the entire run of the function; we will predict it correctly 99% of the time.

Branch Target Prediction

Predicting branch targets can be just as important as predicting branch directions. For jumps and taken branches, or any other time when the flow of control is no longer sequential, the address of the next instruction must be given to the fetch stage as quickly as possible. Some techniques for predicting targets: