4
$\begingroup$

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
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ the runtime formula works good for the architecture you assumed, but if I calculate the runtime of the set of instructions I've I get 4*(4)+(4-1)*(4) = 28 where the chart shows that I've only used 20 ??? can you please help me calculate the runtime of the set of instruction's I've displayed on my question $\endgroup$ – vikkyhacks Sep 18 '14 at 17:45
  • $\begingroup$ My chart / formula uses the same pipeline delays that you used. The difference is that I assume there is a no buffer between stages: data can not move from S1 to S2 until S2 is clear. I also assume that the pipeline is already filled. This is why I have the n markers in my chart; it stands for "no-op" or "no operation". $\endgroup$ – superdesk Sep 18 '14 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.