CHAPTER 10: PARALLEL PROCESSING

PIPELINED?

Instruction pipelining is a technique that implements a form of parallelism called instruction-level parallelism within a single processor.

It therefore allows faster CPU throughput (the number of instructions that can be executed in a unit of time) than would otherwise be possible at a given clock rate.

PIPELINING LESSONS

•          Pipelining doesn’t help latency of single task, it helps throughput of entire workload.
•          Multiple task operating simultaneously using different resources.
•          Potential speedup = Number of stapes
•          Time to “fill” pipeline and time to “drain” it reduces speeduP

PIPELINE SPEEDUP

1.      If all stages are balanced

Time between instruction (pipelined) = Time between instruction (non-pipelined) I p I    n e e I   d    n    k d k    f y j                                                      Number of stages

2.      If not balanced, speedup is less

3.      Speedup due to increased throughput

4.      Ideally 5 stage pipeline should offer nearly five fold improvement over the 800ps non-pipelined time.

SINGLE CYCLE STAGES

Five stages, one step per stage:                

 

PIPELINE REGISTER

DATAPATH WALKTHROUGHS

e.g:     slti $t2, $t1, 17  # if (t1 < 17) t2 = 1 else t2 + 0

STAGE 1: fetch this instruction, increment PC
STAGE 2: decode to determine it is an slti, then read register $t1
STAGE 3: compare value retrieved in Stage 2 with the integer 17
STAGE 4: idle
STAGE 5: write the result of Stage 3(1 if reg source was less than signed immediate, 0 otherwise) into register $t2

      

      e.g:                                                         

                                                 sw $t3, 17($t1)  # Mem [t1 + 17] = t3                                                      

STAGE 1: fetch this instruction, increment PC

STAGE 2: decode to determine it is a sw, then read register $t1 and $t3

STAGE 3: add 17 to value in register $t1(retrieved in Stage 2) to compute address

STAGE 4: write value in register $t3(retrieved in Stage 2) into memory address computed in Stage 3

STAGE 5: idle(nothing to write into a register)

WHY FIVE STAGES?

Could we have a different number of stages?

= Yes

So why do MIPS have five if instructions tend to idle for at least one stage?

= Five stages are the union of all the operations needede by all th instructions.

SINGLE CYCLE PERFORMANCE

Assume time for stages is

• 100ps for register read or write
• 200ps for other stages

Compare pipelined datapath with single-cycle datapath

PIPELINED HAZARD

A pipeline hazard refers to a situation in which a correct program stop to work correctly due to implementing the processor with a pipeline.

There are 3 fundamental types of hazard:

1.      Data Hazard

Arise when an instruction depends on the results of a previous instruction in a way that is exposed by overlapping of instruction in pipeline.

2.      Structural Hazard

Arise from resource conflicts when the hardware can’t support all possible combinations of overlapping instructions.

3.      Control Hazard

Arise from the pipelining of branches and other instructions that change the PC (Program Counter).