|
There are situations, called hazards, that prevent
the next instruction
in the instruction stream from being executing during its designated clock
cycle.
Hazards reduce the performance from the ideal speedup gained by pipelining.
There are three classes of hazards:
Structural
Hazards. They arise from resource conflicts when the hardware cannot
support all possible combinations of instructions in simultaneous overlapped
execution.
Data
Hazards. They arise when an instruction depends on the result of a
previous instruction in a way that is exposed by the overlapping of instructions
in the pipeline.
Control
Hazards. They arise from the pipelining of branches and other instructions
that change the PC.
Hazards in pipelines can make it necessary to stall the pipeline.
The processor can stall on different events:
A cache
miss. A cache miss stalls all the instructions on pipeline both
before and after the instruction causing the miss.
A hazard in pipeline.
Eliminating a hazard often requires that some instructions in the pipeline
to be allowed to proceed while others are delayed. When the instruction
is stalled, all the instructions issued later than the stalled instruction
are also stalled. Instructions issued earlier than the stalled instruction
must continue, since otherwise the hazard will never clear.
A hazard causes pipeline bubbles to be inserted.The following table shows
how the stalls are actually implemented. As a result, no new instructions
are fetched during clock cycle 4, no instruction will finish during
clock cycle 8.
In case of structural hazards:
Clock cycle number |
Instr |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Instr i |
IF |
ID |
EX |
MEM |
WB |
|
|
|
|
|
Instr i+1 |
|
IF |
ID |
EX |
MEM |
WB |
|
|
|
|
Instr i+2 |
|
|
IF |
ID |
EX |
MEM |
WB |
|
|
|
Stall |
|
|
|
bubble |
bubble |
bubble |
bubble |
bubble |
|
|
Instr i+3 |
|
|
|
|
IF |
ID |
EX |
MEM |
WB |
|
Instr i+4 |
|
|
|
|
|
IF |
ID |
EX |
MEM |
WB |
To simplify the picture it is also commonly shown like this:
Clock cycle number |
Instr |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Instr i |
IF |
ID |
EX |
MEM |
WB |
|
|
|
|
|
Instr i+1 |
|
IF |
ID |
EX |
MEM |
WB |
|
|
|
|
Instr i+2 |
|
|
IF |
ID |
EX |
MEM |
WB |
|
|
|
Instr i+3 |
|
|
|
stall |
IF |
ID |
EX |
MEM |
WB |
|
Instr i+4 |
|
|
|
|
|
IF |
ID |
EX |
MEM |
WB |
In case of data hazards:
Clock cycle number |
Instr |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Instr i |
IF |
ID |
EX |
MEM |
WB |
|
|
|
|
|
Instr i+1 |
|
IF |
ID |
bubble |
EX |
MEM |
WB |
|
|
|
Instr i+2 |
|
|
IF |
bubble |
ID |
EX |
MEM |
WB |
|
|
Instr i+3 |
|
|
|
bubble |
IF |
ID |
EX |
MEM |
WB |
|
Instr i+4 |
|
|
|
|
|
IF |
ID |
EX |
MEM |
WB |
which appears the same with stalls:
Clock cycle number |
Instr |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
Instr i |
IF |
ID |
EX |
MEM |
WB |
|
|
|
|
|
Instr i+1 |
|
IF |
ID |
stall |
EX |
MEM |
WB |
|
|
|
Instr i+2 |
|
|
IF |
stall |
ID |
EX |
MEM |
WB |
|
|
Instr i+3 |
|
|
|
stall |
IF |
ID |
EX |
MEM |
WB |
|
Instr i+4 |
|
|
|
|
|
IF |
ID |
EX |
MEM |
WB |
|