Pipelining

Why pipeline?

Pipelining is an implementation technique in which multiple instructions are overlapped in execution.

MIPS Instructions classically take 5 steps

IF: Fetch instruction from memory

ID: Read registers while decoding the instruction.

EX: Execute the operation or calculate an address

MEM: Access an operand in data memory.

WB: Write the result into a register

Some important definitions

Potential Speedup = Number of pipe stages

Unbalanced lengths of pipe stages reduces speedup

Hazards in Pipelining

Structural Hazard

Structural hazard occurs when the same hardware has to support multiple instructions simultaneously in the same clock cycle.

Example: Lets assume we have a 5 stage pipeline as shown in the image

Here, we can see that Data access and instruction fetch have to occur simultaneously which leads to structural hazard because memory has only one read/write port usually.

Control Hazards

Control hazards occur when we need to make a decision based on the result of a previous instruction still executing in pipeline.

Solutions:

• Delayed Branch: We delay the overlapping instruction so that the conflict never occurs.
• Predict Branch Outcome.
• Stall the pipeline.

Data Hazards

Data hazards occur when the instruction needs data from the result of a previous instruction still executing in the pipeline.

Solutions:

• Forward data if possible

Some MIPS examples for Data Hazards

main:
    lw      $t1, 0($t0)
    lw      $t2, 4($t0)
    add     $t3, $t1, $t2
    sw      $t3, 12($t0)
    lw      $t4, 8($t0)

Data hazard occurs in step 3 since $t1 and $t2 are already trying to get accessed when the instruction for their loading was just a few cycles ago which may cause data hazard in pipelining.

Reordered Code:

main:
    lw      $t1, 0($t0)
    lw      $t2, 4($t0)
    lw      $t4, 8($t0)
    add     $t3, $t1, $t2
    sw      $t3, 12($t0)

Important formulae in pipelining:

Here, 
n = Number of Tasks
k = Number of segments in pipeline
t(n) = Time taken without pipeline
t(p) = Time taken after pipeline