What is the theoretical speedup with pipeline system over a nonpipelined system?

What is the theoretical speedup that could be achieved with the pipeline system over a nonpipelined system?

The equation I use for speedup is

$$S = \frac{nT}{(k+n-1)t}\,$$

where:

• $n$ is the number of tasks
• $T$ is the time to process a task
• $k$ is the number of stages segments
• $t$ is the time per stage segment

I dont understand how to use this equation for this particular question.

• Is there more to this question? Is there some theoretical machine that you are comparing? Are you just supposed to demonstrate the difference by plugging in some random numbers? – Cogman Dec 31 '14 at 23:27
• Speedup doesn't really make sense as pipelined machines emphasis throughput. the time to compute one task is fixed, but with a perfectly pipelined machine you could have several tasks being processed at the same time. The theoretical speedup is going to depend on the number of stages and on the size of each stage, but the processing time for a given task is going to be, somewhat, fixed. – Cogman Dec 31 '14 at 23:29

The total time to compute $n$ tasks with no pipelining is $nT$ (the top of your fraction). The total time to compute $n$ tasks with a pipeline $k$ stages deep, and a clock cycle time of $t$ is $nt$ (to produce the results once the first task reaches the last pipeline stage) + $(k-1)t$ to get the first task from the beginning of the pipeline to the last stage. This is the $(k + n - 1)t$ in the bottom of your fraction.

The part you are missing is that $kt$ (the time for each task to get from beginning to end of the pipeline) must be larger than $T$. This is because in the perfect case you would divide the circuit of delay $T$ into $k$ exactly equal segment, but then you would need to insert a register between each segment and the next, which will add delay.

So replace $t$ with $T/k$ in your fraction and take the limit as $k\rightarrow\infty$ and you will have your answer.

More interesting is to replace $t$ with $T/k + r$ where $r$ is the constant extra register delay that you need to add between stages, take the derivative of your fraction with respect to $k$ and set it equal to 0 and solve

• Can you give me some link, I want to go in details. – asit_dhal Feb 27 '16 at 22:44

At the limit as $n \to \infty$, $k+n-1$ approaches $n$.

Assuming our pipeline is efficient, $T = kt + c$, where $c$ is small.

Substituting in, $\frac{nkt}{(k+n-1)t} \to k$ as $n \to \infty$.

In other words, the speedup due to pipelines is roughly $k$, the number of stages in the pipeline.

Of course, this implies the absurdity that all we need to do to add speed is to add stages... So you need to measure pipeline efficiency (that is, make sure the cost of staging, $c$, is small).

• To say that "In the limit as $n\to\infty$, $f(n)$ approaches $n$" for some function $f$ means that, for all $\epsilon>0$, we have $|f(n)-n|<\epsilon$ for all large enough $n$. That certainly isn't true for $f(n)=k+n-1$ since, then, $|f(n)-n|=k-1$ for all $n$. – David Richerby Feb 14 '17 at 23:39