Instruction Pipeline

The simplest way to speed up the processor operation is to pipeline it. Pipelining is one specific form of parallelism, where the execution of several instructions can be interleaved on the same hardware. Pipelining does not reduce the time to complete an instruction, but increases the number of instructions that can be processed at once.

Each instruction is split into a sequence of dependent steps.

Different stages of a instruction pipeling :

1. Fetch operands
2. Instruction Decode
3. ALU operation
4. Memory access
5. Register write                                             

                                                        pipeline stages are shown:

                                 Pipeline Performance

The cycle time  of an instruction pipeline can be determined as:

T=max[Ti]+d=Tm+d with 1  i k

where:

Tm = Maximun stage delay through stage

k = number of stages in instruction pipeline

d = time delay of a latch.

In general, the time delay d is equivalent to a clock pulse and Tm >> d. Suppose that n instruction are processed with no branched.

• The total time required Tk to execute all n instruction is:

Tk= [k + (n-1)]

• The speedup factor for the instruction pipeline compared to execution without the pipeline is defined as:

SK=T1TK=nkτ[k+(n−1)]τ=nkk+(n−1)

• An ideal pipeline divides a task into k independent sequential subtasks

– Each subtask requires 1 time unit to complete

– The task itself then requires k time units tocomplete. For n iterations of the task, the execution times will be:

– With no pipelining: nk time units

– With pipelining: k + (n-1) time units

Speedup of a k-stage pipeline is thus

S = nk / [k+(n-1)] ==> k (for large n)        

Pipeline Limitation

Several factors serve to limit the pipeline performance. If the six stage are not of equal duration, there will be some waiting involved at various pipeline stage. Another difficulty is the condition branch instruction or the unpredictable event is an interrupt. Other problem arise that the memory conflicts could occur.

Pipeline Hazard :

The ideal pipeline executes instructions during each clock cycle so that the pipeline hardware is always doing something useful.  Real pipelines with real instructions can encounter situations where an instruction would not execute correctly because of problems with other instructions already in the pipeline.  These situations are called hazards.

1. Structural hazards - When hardware units are being used by instructions already in the 

pipeline, these units will not be available for use by other instructions.  Any situation 

where there is not enough hardware is a structural hazard.

2. Data hazards - Data hazards can occur when two instructions use data from the same 

register.  Data hazards are divided into three categories.

             a. RAW (read after write) hazards - the current instruction must wait to read data 

                                                          until after a previous instruction writes the correct data.

             b. WAR (write after read) hazards - the current instruction must wait to write data 

                                                          until after a previous instruction reads the old data.

             c. WAW (write after write) hazards - the current instruction must wait to write data 

until after a previous instruction writes to the same register.  This hazard is more 

subtle in that neither instruction executes incorrectly.  However, subsequent 

instructions can be incorrect if the writes occur out of order.

Note that RAR (read after read) is not really a hazard because it makes no difference 

which order the same operand is read.

3. Control hazards - In the ideal pipeline, we fetch instructions one after another in order.  

As long as location of the next instruction is known, this process can go forward.  When 

a branch instruction is fetched, the next instruction location is not known until the 

branch instruction finishes execution.  Thus, we may have to wait until the correct loca-

tion of the next instruction is known before fetching more instructions.  This is a con-

trol hazard.

for more detail  go to Hazards in Pipelining

    

                                                               ........to be continued                          R.P