Control Hazards
Control Hazards are another type of hazard that can have disastrous effects when not rectified. But to understand why so, we first need to understand what control hazards are.
Let’s take a very simple example where you want to find the sum of numbers from 1 to 10. In a high-level language like C, we write code like this:
int sum = 0 ;
for(int i = 1; i <= 10; i++)
sum += i ;Here’s how it would look like in RISC-V assembly:
addi x8, x0, 10
addi x9, x0, 1
addi x10, x0, 0
loop:
add x10, x10, x9
addi x9, x9, 1
ble x9, x8, loop
sd x10, 0(x14)Assume that the last instruction is a store that writes our result back to memory. Let’s plot the execution of instructions over time (memory is in yellow for ALU instructions since this stage is not used, but the instruction passes through it anyways):
Notice something? The first time we execute this loop, the branch compares and sees if x9 <= x8. This condition is true, since x9 is 1, and x8 is 10. Hence, the processor should transfer control 2 instructions back. In our pipelined implementation, the branch is executed at cycle 8, and only then it realizes that it should loop back. However, due to pipelining, the next instruction (sd) is already fetched in cycle 7, and decoded in cycle 8. Ideally, the processor should fetch a different instruction in cycle 7. However, the processor did not know that, since the branch was evaluated in cycle 8. This creates an inconsistency in the execution flow and leads to erroneous output.
Mitigating control hazards
Similar to data hazards, we can mitigate control hazards by using the following techniques:
Inserting nop
Similar to how we resolved data hazards, we can resolve control hazards by inserting nops between the branch instruction and its subsequent instruction.
Get Ruban S’s stories in your inbox
Join Medium for free to get updates from this writer.
Let’s go ahead and add a couple of nops between the branch and the subsequent store:
ble x9, x8, loop
nop
nop
sd x10, 0(x14)This is how it looks like in the pipeline:
Here, the branch is fetched in cycle 6 and executed in cycle 8. Right after the branch is fetched, the CPU fetches both nops in consecutive cycles. By cycle 8, the execute stage evaluates the condition and realizes that the CPU should fetch a different instruction. Hence, it sends a redirect signal to the fetch unit to fetch from the correct memory address.
The nops continue to go through the pipeline as usual. They don’t affect the architectural state in any way, nor do they create data dependencies with subsequent instructions.
Just like the case with the data hazard, this solution is not performance-efficient. The extra cost comes in the form of extra instructions and cycles. While the performance drop might not be as much as with the data hazard case, the performance drop is still significant enough. Hence, we need a more efficient solution.
Stalling instructions
This solution is also similar to the one discussed in the data hazard post. However, we cannot stall the next instruction because there is a chance that the next instruction might not be the right one to fetch according to the program flow. Hence, we stall the fetch unit itself, until we resolve the branch condition in the execute stage. Let’s see how it looks:
Here the CPU stalls the fetch unit for 2 cycles, until the execute stage figures out the correct target. This is similar to inserting nops, without the additional overhead of the extra instructions.
Just like stalling instructions to resolve data hazards, stalling instructions to resolve control hazards has a performance impact, and there are better ways to resolve control hazards without the performance drop.
Branch Prediction
Imagine there was a magical block in the fetch unit that could self-determine if the instruction fetched was a branch, and if so, which path the branch would take. We call such a unit as “branch predictor”, and it performs the action of predicting a branch path. For now, we’ll represent a branch predictor using a box as follows:
“branch_pred” takes in the current PC as input, and arrives at the target, otherwise known as the “predicted” target. It also outputs a 1-bit value to specify which target to consider (whether the immediate next instruction, which is a not-taken branch, or some other target to jump to, which is a taken branch).
Branch prediction is a vast topic and definitely requires a blog post of its own at the least. Hence, we shall explore branch prediction techniques in the next post.
