Preface

The Pipeline Pattern is a design method that improves system throughput and operating frequency by dividing the logic circuit into stages. It decomposes complex tasks into multiple substeps, with each step processing data and passing it to the next until all steps are complete.

Never mind the BS above — just jargon meant to shroud everything in fog.

In parallelizable programs, a pipeline can compress a job that needs 5 sequential steps into the time of just 1 step (5-way parallel). Design — pretty amazing, huh?

I recently explained pipelines to my buddies and drew a pretty decent excalidraw diagram. It'd be a waste not to use it on the blog.

The Scenario

Let's assume a computation that starts from a set of initial conditions and then iterates based on a random condition. The +1 simply stands for an operation that consumes some compute and time based on the original condition.

Let's also assume hardware capable of running 5 threads in parallel, to make the rest of the discussion easier.

/* 初始条件 */
A = 0
B = 0
C = 0
D = 0
E = 0

/* 不断迭代计算 */
while( 1e20 次 )
{
    A = x + 1; // x 表示一个迭代条件值，在这里可以视为随机
    B = A + 1;
    C = B + 1;
    D = C + 1;
    E = D + 1;
}

Serial Execution

If you write the above computation as single-threaded C code, it obviously looks something like the following, with the horizontal axis as the clock.

The lanes 1, 2, 3, 4, 5 can be read as the computation steps above. In this simple example, they can also be seen as CPU cores running in parallel — core 1 dedicated to thread A, core 2 dedicated to thread B...

Some clever friends might ask: since these are CPU cores, shouldn't thread scheduling be possible? How can we let cores sit idle? Max them out! They must be maxed out!

But look at our scenario: thread B has to wait for thread A's result, thread C has to wait for thread B's result...

So are we just supposed to let the CPU slack off?

Parallel Execution

Same as the serial case: pre-compute 5 iterations, pick out some of the values, and use them as the basis for parallel execution.

From then on, every cycle can be computed in parallel, and the CPU stays completely jam-packed.

Another Scenario

The above is the idea of converting a small module from serial to parallel.

Now let's assume a more scientific computation, to discuss whether the so-called pipeline is feasible for self-iterating loops. This is iteration in the more commonly understood sense.

/* 不断迭代计算 */
while( 1e20 次 )
{
    A = E + 1; // 线程A 需要 线程E 的结果 
    B = A + 1;
    C = B + 1;
    D = C + 1;
    E = D + 1;
}

In this scenario, the result of each self-iteration is the initial condition for the next, so there is no room at all for pipeline-style optimization. If we applied our earlier parallel optimization and stacked all the lanes together, thread A would need thread E's result from 5 cycles later — that means predicting the future, and adding such an algorithm would only drag down performance.

Summary

Think about a computation module's input and output: if the input comes from outside, pipeline parallelization applies; if the module is self-iterating, it doesn't.

Postscript

A month later, looking back, I finally got what this so-called throughput improvement really means: in highly parallel programs, it improves data I/O efficiency — as if each stage has an internal queue, so that every step can queue up independently.

I figure this is just a perfectly normal way of thinking, isn't it? In software modularization and assembly, each submodule is supposed to be self-contained and run independently, communicating only through data I/O — so assembling them naturally yields a parallel program. This way of thinking isn't confined to FPGAs; it's a foundational idea and guiding principle in all software design. Tossing around jargon just makes it incomprehensible. In fact, before this, I'd only heard of pipeline design in passing.