A pipeline is balanced iff there exists such that the latency of every task is at most .
The question then is when is a pipeline balanced? Let us consider some examples of pipelines.
The pipeline composed of where and is unbalanced.
Intuitively we can understand this by drawing a diagram of this pipeline, which looks something like this
and from the diagram it is not unreasonable to guess that the latency for the th task follows the formula
(assuming that we start at for the first execution rather than ). This clearly implies that is unbounded.
Why does the latency grow like that? We can keep scheduling executions of , while we have to wait for those of . How about if we swap and (it would not be wrong to guess that the pipeline becomes balanced).
The pipeline from 34.1.1, but where our pipeline executes , rather than .
We now end up with a diagram which looks a bit like this
And from the pattern, we can see that we can neatly slot each new task in. Previously we could very quickly execute the first step in the pipeline, but then had to wait a long time for the slow steps from previous executions to complete. Now we can execute the first step slowly, but because it took longer than the first step, we know that the subsequent machines will definitely be free for us to use.
This lends itself to the following theorem
Let be a pipeline. is balanced (i.e. the latency of is bounded) if .
Proof: we argue by induction on the number of stages in the pipeline.
The base case is simple; if then the latency of is .
Next, suppose that the pipeline is balanced (and satisfies the condition ). Let .
The case that we essentially have so far is a pipeline which looks a bit like this
and if we slot on the end, we end up with a balanced pipeline. This is because we know that the \sayspace on the end is at most and , so it (geometrically) will \sayfit.
Author’s note: this proof clearly needs some work.
Of course, it also makes sense to ask for when a pipeline is unbalanced. Intuitively, if one of the later stages takes more time than one of the earlier ones, then we will run into problems - the pipeline will take too long.