[Solved]: Why is the processor's pipeline delay calculated as N*max(Delay) ? why not N*(D1 + D2 + D3 ... )?

Problem Detail: 

Consider a four stage pipeline, and each stage has delays D1, D2, D3 and D4, so the total delay because of the various stages should be N * (D1 + D2 + D3 + D4) where N is the number of instructions, but I see that this is not the case, I see here that the delay is calculated as N*max(D1,D2,D3,D4) , why is only the max value taken into account ?

I try to apply the above two ideas for the below chart and none of them work.

For the below chart consider that the numbers on top are the time and the S1, S2, S3 and S4 denote the time spent any stage of an instruction on the pipeline

with N*(max(S1,S2,S3,S4)) = 4*(4) = 16, and with N*(S1 + S2 + S3 + S4) = 4*(1+2+4+1) = 32  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 S1 S2 S2 S3 S3 S3 S3 S4    S1    S2 S2       S3 S3 S3 S3 S4       S1       S2 S2             S3 S3 S3 S3 S4          S1          S2 S2                   S3 S3 S3 S3 S4 

Asked By : vikkyhacks

Answered By : superdesk

Each stage of the pipeline is only as fast as the slowest stage. The calculation for the latency expresses this by taking the maximum delay (max(D1, D2, D3, D4)) and multiplying it by N, which is the number of stages. Thus: N*max(D1, D2, D3, D4).

Keep in mind, N is the number of stages, not instructions. The formula measures the latency, not the total run time.

Your chart demonstrates this, as you can see that there is more and more delay building up in the first and second stages as they finish faster than the next stage. But there is a problem: where does the data from each stage go before it enters the next stage? The simple answer is nowhere: it is stuck in the current stage until the next stage is free. Your third stage is creating a traffic jam!

Consider this chart, in which each stage has been slowed down to take 4 time units (the n represents that processing is done but the data must wait for the next stage to clear):

    1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28     S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!                 S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!                             S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done!                                         S1 n  n  n  S2 S2 n  n  S3 S3 S3 S3 S4 n  n  n  Done! 

Here we can see that it takes each individual instruction 16 time units to make it through the pipeline (4 stages * max delay of 4). The total run time is only 28 time units. It takes 16 units for the first instruction to run, and 4 more time units for each additional instruction. So the run time formula is something like: N*max(D1, D2, D3, D4) + (IC - 1) * max(D1, D2, D3, D4) where N is the number of stages and IC is the number of instructions.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30081