Execution Time in Stage Pipeline

Question

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,

Answer 1

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$.

Answer 2

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$.

Answer 3

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.