Back to ComputerTerms

See DataPath

MIPS 5 stage pipeline

1. IF Instruction Fetch instruction from memory

2. ID Instruction Decode / Read registers - while decoding the instruction (the format of MIPS instructions allow reading and decoding to occur simultaneously)

3. EX Execution or Memory address calculation

4. MEM Access an operand in data memory.

5. WB Write the result Back into a register. We note that this happens on the first half of the cycle and that reads can then happen concurrently in the ID stage.

Structure Hazards

This means that the hardware can not support the combination of instructions that we want to execute in the same clock cycle. Since MIPS was designed with pipelining in mind it is fairly easy to avoid structural hazards. If we allowed instruction 1 & 4 simultaneously without providing two mechanisms to access memeory this could be a structural hazard.

Control Hazards

Control hazards arise from the need to make a decision (branch) before continuing. There are two solutions:

1. Stall: Just operate sequentially until the decision can be made. This is often refered to as inserting a bubble into the pipeline.
2. Predict: Make a guess and continue. If you are right nothing is lost, if you are wrong you have to start over just like a stall.

Prediction is obviously a better route! Dynamic branch prediction is about 90% accurate. Longer pipelines incur a larger penalty on a missed branch prediction! (P444 Computer Organization and Design)

To further complicate our lives and make things a bit faster hardware is added to be able to predict the branch in the ID stage so that we only have to insert one bubble into the pipeline.

Dynamic branch prediction uses a branch prediction buffer or branch history table so that when a branch instruction is fetched we look up a history of the lower bits of the instruction address. The value is either 1 taken or 0 not taken. More complicated schemes such as two bits of history can improve prediction.

Data Hazards

Suppose we have

     add $s0, $t0, $t1
     sub $t2, $s0, $t3

In this cas $s0 is accessed before it is written to the register!

To take care of this we can use Forwarding also called Bypassing.

     IF | ID/REG | ALU                         | (DA) | Reg |
                 | Value available from ALU                   Value available in Register
                                             \
                                              \  Forwarding or bypassing
                                               \
                                                \   
        | IF     | ID/REG Needed               | ALU  | DA  | REG

Forwarding without stalling can cause a data hazard, or a control hazard in the calculation of a new PC.

Back to ComputerTerms