1Learning Outcomes¶
Given program instruction code and a processor architecture, identify when control hazards occur.
Explain the approach that the RISC-V five-stage pipeline uses to resolve control hazards.
🎥 Lecture Video
From earlier:
Control hazard: The flow of execution depends on previous instructions. The wrong instructions are executed.
Control hazards occur when the instruction fetched may not be the one needed. In other words, whether an instruction executes depends on the outcome of a previous execution. From P&H 4.6:
Suppose our laundry crew was given the happy task of cleaning the uniforms of a football team. Given how filthy the laundry is, we need to determine whether the detergent and water temperature setting we select are strong enough to get the unifroms clean...In our laundry pipeline, we have to wait until the second stage to examine the dry uniform to see if we need to change the washer setup or not.
Control hazard occur with jump and branch instructions. We must begin fetching the instruction following the jump/branch on the following clock cycle. However, the pipeline cannot possibly know what the next instruction should be—since it only just read the jump/branch instruction from memory.
We demonstrate a control hazard with B-Type instructions in Table 1. We take the branch in the MEM stage, after we know the result of the ALU and branch comparator in the EX stage.[1] Otherwise, if we don’t take the branch, we continue selecting the next instruction as PC + 4.
Table 1:Control hazards can occur with branch instructions, because instructions are executed before the branch outcome is known.
Instruction | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB |
For the beq instruction, we must wait until time cycle 4 (beq’s MEM stage) to determine if the branch is taken. By that time, the next three instructions have already started executing, before the branch outcome was known.
If the branch is indeed taken, to avoid a control hazard we need to ensure that the three instructions sub, or, and xor do not execute to completion. We discuss a naive approach first, then a more clever one.
2Approach 1: Stall on branch¶
One possibility is that whenever we detect a branch (or jump) instruction, we stall the pipeline when we detect a branch until the correct PC is known. This implementation would involve extra wiring so that as soon as a branch is decoded in the ID stage, other instructions are stalled until the branch outcome is determined in the MEM stage.
In Table 2, every branch instruction incurs a three-instruction stall, regardless if the branch is taken or not.
Table 2:Approach 1. On a branch instruction, always stall until the next instruction is determined. A dash (–) indicates that the pipeline is flushed and affected instructions do “nothing.”
Instruction | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| IF | ID | EX | M | WB | ||||
| – | – | – | – | – | ||||
| – | – | – | – | – | ||||
| – | – | – | – | – | ||||
| IF | ID | EX | M | WB |
This approach is simple but slow. It is rather costly if our program has many branches. After all, if we don’t take the branch, we should proceed with executing the sub instruction, or PC + 4.
3Approach 2: Assume branch not taken¶
Another approach could be to stall only when needed. In other words, proceed with executing the instructions in sequence, and immediately flush the pipeline once it is determined that the branch should be taken. Compare the two cases below.
If a branch is taken, we stall three cycles. In Table 3, once it is determined that the branch is taken in cycle 4, flush the pipeline. This involves converting the instructions in the IF, IF, EX stages to no-ops. Then, in cycle 5, the correct instruction (the sw instruction branched to) is executed.
Table 3:Approach 2. In cycle 4, we determine that the branch is taken. A dash (–) indicates that the pipeline is flushed and affected instructions do “nothing.”
Instruction | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| IF | ID | EX | M | WB | ||||
| IF | ID | – | – | – | ||||
| IF | – | – | – | – | ||||
| – | – | – | – | – | ||||
| IF | ID | EX | M | WB |
If the branch is not taken, we stall zero cycles. In Table 4, if it is determined that the branch is not taken in cycle 4, do not do anything out of the ordinary. Because the instructions sub, or, and xor are already in the pipeline, we do not waste any cycles on stalling.
Table 4:Approach 2. If the branch is not taken, proceed as normal. This table therefore looks identical to Table 1!
Instruction | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB | ||||
| IF | ID | EX | M | WB |
Like most all cases we have seen thus far, we can evaluate the performance of this design—that is, assuming that branches are not taken, then stalling if they are—design on a program benchmark. If we have a program that takes many branches, this design will perform poorly. If we have a program that does not take many branches (even though many branch instructions exist), this design will work great!
4Approach 3: Branch Prediction¶
The simple approach used by our five-stage pipeline, described in the previous subsection, is an example of branch prediction.
Computers nowadays use a more sophisticated version of branch prediction. A rigid version could predict before the program executes that some conditional branches are taken and some are untaken. This approach may rely on stereotypical behavior or the average case, or even a “coin flip” on each cycle
More complex versions of branch prediction are dynamic and occur in hardware, which make guesses depending on the behavior of each and every conditional branch. These dynamic hardware predictors may change predictions for a conditional branch over the life of a program.
For more approaches to branch prediction and control hazards, see P&H 4.9.
Review
MEMin the five stages from earlier.