# Execution Time in Stage Pipeline

Exam Question: A five-stage pipeline has stage delays of 150,120,150,160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each. The total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is _______ nanoseconds.

Solution: k(stage)=5, n(instruction)=100

where k=number of pipeline stages, n=number of instructions,tp=pipeline cycle time.

Total time=(k+n-1)*tp

tp=max(stage delays) + register delay tp=max(150,120,150,160,140)+5ns tp=160+5=165ns

Total time =(5+100-1)165=104165=17160 ns.

My Question In the above solution why we are using the formula for total time is like that. We can use something like:

tp*(n-1) + (sum of delays in all stages)

Can anyone tell me why total time formula is given as "(k+n-1)*tp" ? If we put n as 1 we will get wrong answer.

Thanks,

• do you understand what pipelining does and why is it used? putting n=1 doesn't make sense as for a single instruction, pipelining doesn't provide any benefits, but of course you can plug in values as its math, and it would work out. Aug 17, 2022 at 7:54
• @RinkeshP I do understand pipe-lining a little. My question here is the equation does not satisfy maths. The equation "tp*(n-1) + (sum of delays in all stages)" would be satisfying math in most of cases right? But why we are using this equation "(k+n-1)*tp" ? Why there is k in that equation? If you remove k then my equation would be similar to this one. Aug 17, 2022 at 8:34

Read it like this: total time = $$n*tp + (k-1)*tp$$

$$n*tp$$ is the time the instructions take .. sort of. But it would be the time between when the first instruction starts, and when the last instruction starts. That means the program has not finished yet, some instructions are still in the pipeline, we have to wait a little bit longer. Those instructions that are still in the pipeline at that point stick around for $$k-1$$ more cycles (not $$k$$, that would allow a whole extra instruction to run, that's too much) and only then is the program done.

If we put n as 1 we will get wrong answer.

If we put $$n$$ as 1 then we get $$k*tp$$, which seems fine to me. Any less than that would mean the instruction has not made it all the way through the pipeline, and so far there is no concrete reason to say that it will take longer (a more detailed model may reveal such reasons, but then the original formula for the time would also be modified).

Consider 5 instructions being executed by a 5-stage pipeline (pictured below). How many cycles does that take? The answer isn't 5, after 5 cycles only the first instruction is done, and 4 instructions are still in the pipeline. It takes another 4 cycles to finish them.

Multiply the number of cycles by the length of a cycle, $$tp$$. • Thanks for the answer, I do understand why we are taking (k-1)*tp. But I do not understand why we need n*tp. "n" is number of stages but all stages have different time so it does not make sense to me. Say all stage have 0 delay except one having delay of 160 as given. Then we will be getting same answer even my system is better than the other. Aug 17, 2022 at 8:28
• @AamodThakur k is the number of stages. We take the maximum stage time because that will determine the highest clock frequency. IE if all stages had zero delay except one had a delay of 160, that would not improve the processor at all, it would still run at about 6MHz at most, due to the clock frequency still being limited by the slowest stage. Any stage that is faster than the slowest stage, just sits there doing nothing for a while. Aug 17, 2022 at 9:20
• thanks for comment, you are right about delay won't change. I got one more doubt. Why is total time changing with stage. Say we got 100 stages 99 with 0 delay and 1 with 160 delay. And other with 5 stage 4 with 0 delay and 1 with 160 delay. As per the formula why is one with 100 stage taking more total time even though both of them are similar. Aug 17, 2022 at 10:19
• @AamodThakur they're really not similar though, they're only similar in their "steady state" behaviour. As long as both of those processors are running, they're executing instruction at the same rate (well, under optimistic assumptions anyway - once you introduce branch mispredictions it won't look so good for the 100-stage processor). But the processor with a hundred stages has a disadvantage at the end: it takes a long time to drain its pipeline. Aug 17, 2022 at 10:31
• Thanks for comment. I do understand that practically it won't be feasible. But if we see it mathematically (k + n - 1)*tp increasing number of stages increase the total time by large amount. But if you try to manually calculate time taken by both the case will be same (max_delay * number_of_instruction). But with (k + n - 1)*tp we will get extremely different answer. This is what I am unable to understand. You are right practically it is difficult do it but still I want to think this question in ideal way first. Aug 17, 2022 at 10:49

Let's brush up pipelining a bit. To summarize, the goal of pipelining is to make the clocks per instruction (CPI) approach $$1$$, which means that as you keep increasing the number of instructions they take only $$1$$ clock cycle(which is the time taken by the slowest stage in the pipeline) to complete.

Assume you have a single instruction. Now, to complete it's execution this must go through all the $$k$$ stages of the pipeline(including the buffer delays & in this case $$5$$ stages) so it takes $$k$$ clock cycles to complete. Now lets take $$2$$ instructions, naturally both of them have to pass through the complete pipeline to complete their execution. Here is where the pipelining shows its benefits. As the first instruction moves from $$stage$$ $$1$$ to $$stage$$ $$2$$, simultaneously the second instruction enters $$stage$$ $$1$$. Its easy to infer that when the first instruction would be at stage $$k$$, the second would be right behind it at stage $$k-1$$ (assuming no stalls). So now the first instruction completes at $$kth$$ clock cycle and the second instruction at $$k+1th$$ clock cycle.

Generalizing it, when you have n instructions, the $$1st$$ one will always be completed at the $$kth$$ clock cycle, and the remaining $$n-1$$ instructions would get completed at subsequent $$n-1$$ clock cycles as each of them would take only $$1$$ clock cycle to complete, giving a total of $$k+n-1$$ clock cycles. $$tp$$ is the multiplicative factor, which here is the time taken by $$1$$ clock cycle. Take note that all the instructions take the complete time of the whole pipeline to execute, but since we do not let the pipeline sit idle, the overall completion time is greatly reduced, which is what pipelining aims at.

My Question In the above solution why we are using the formula for total time is like that. We can use something like:

tp*(n-1) + (sum of delays in all stages)

Well you are correct, as I mentioned the $$1st$$ instruction would be completed at the $$kth$$ clock cycle, which is after passing through all the $$k$$ stages and their delays, which turns out to be $$k*tp$$, and the complete expression becomes $$tp*(n-1)+k*tp$$ which is the same as $$(k+n-1)*tp$$.

The longest stage takes 160ns + 5ns = 165ns. That means one instruction can leave the fourth stage every 165ns, not quicker. You just calculate the time until the first instruction leaves the 4th stage, then the time until the 100th instruction leaves the 4th stage, and the time until the 100th instruction exits the pipeline.

Instruction 1 leaves stage 4 after (155 + 125 + 155 + 165)ns. Instruction 100 moves from exiting stage 4 to the end of the pipeline in after 145ns.

So the total is (n-1)*tp plus the time for the k stages. If we round the time for the stages up to the times of the longest stage, that adds 80ns, and the total time is now (n + k - 1) * tp. So there is a tiny difference (80ns) between the given answer and your answer.

In practice, having stages at different lengths and saving time because of it would be a horror to implement. It is much easier to have one 165ns clock to control everything. So in practice your CPU will behave as if it had five stages of (160 + 5)ns each. Which of course makes the different times for different stages irrelevant, and the (k + n - 1) * tp answer correct.