34.1 Latency

Definition 34.1.1

A pipeline is balanced iff there exists $C>0$ such that the latency of every task is at most $C$ .

The question then is when is a pipeline balanced? Let us consider some examples of pipelines.

Example 34.1.1

The pipeline composed of $t_{1},t_{2}$ where $|t_{1}|=1$ and $|t_{2}|=2$ 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 $L$ for the $n$ th task follows the formula

L=|t_{1}|+|t_{2}|+(n-1)

(34.1)

(assuming that we start at $n=1$ for the first execution rather than $n=0$ ). This clearly implies that $L$ is unbounded.

Why does the latency grow like that? We can keep scheduling executions of $t_{1}$ , while we have to wait for those of $t_{2}$ . How about if we swap $t_{2}$ and $t_{1}$ (it would not be wrong to guess that the pipeline becomes balanced).

Example 34.1.2

The pipeline from 34.1.1, but where our pipeline executes $t_{2},t_{1}$ , rather than $t_{1},t_{2}$ .

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

Theorem 34.1.1

Let $P=(t_{1},...,t_{n})$ be a pipeline. $P$ is balanced (i.e. the latency of $P$ is bounded) if $|t_{1}|\geq|t_{2}|\geq|t_{3}|\geq...\geq|t_{n}|$ .

Proof: we argue by induction on the number of stages in the pipeline.

The base case is simple; if $P=(t_{1})$ then the latency of $P$ is $|t_{1}|$ .

Next, suppose that the pipeline $P=(t_{1},t_{2},...,t_{n})$ is balanced (and satisfies the condition $|t_{1}|\geq|t_{2}|\geq...\geq|t_{n}|$ ). Let $|t_{n+1}|\leq|t_{n}|$ .

The case that we essentially have so far is a pipeline which looks a bit like this

and if we slot $t_{n+1}$ on the end, we end up with a balanced pipeline. This is because we know that the \sayspace on the end is at most $t_{1}$ and $t_{n+1}\leq t_{1}$ , 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.