はじめに

パイプライン設計パターン（Pipeline Pattern）とは、論理回路を分割することでシステムのスループットと動作周波数を高める設計手法である。複雑なタスクを複数のサブステップに分解し、各ステップがデータを処理して次のステップへ渡す。これをすべてのステップが処理を完了するまで繰り返す

さっきのデタラメは無視してほしい。専門用語を並べて煙に巻いているだけだから。

並列化が可能なプログラムでは、パイプライン設計によって、順番に5ステップかかる処理を、たった1ステップ分の時間に圧縮できる（5並列）。設計って、すごいでしょ。

最近、仲間にパイプラインを説明するときに、なかなかいい感じのexcalidrawを描いたので、ブログに載せないのはもったいない。

想定するシナリオ

ある計算プロセスを仮定しよう。一連の初期条件があり、その後、ランダムな条件に基づいて反復計算を行うものとする。ここでの +1 は、単に元の条件に基づいて計算リソースと時間を消費する操作を意味しているだけだ。

さらに、説明を進めやすくするために、5スレッドの並列計算が可能なハードウェアを仮定しよう。

/* 初始条件 */
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;
}

直列実行

上記の計算プロセスをC言語でシングルスレッド実行すると、おおよそ次のような流れになる。横軸はクロックと見なしてほしい。

ここでの1、2、3、4、5のレーンは、上記の計算ステップと見なせる。この単純な例では、並列実行用のCPUコアと見なすこともできる。コア1はスレッドAに専念し、コア2はスレッドBに専念する、といった具合だ……

賢い人ならこう言うかもしれない。「CPUコアならスレッドスケジューリングで何とかできるんじゃないの？」どうしてコアを遊ばせておくんだ。フル稼働だ！絶対にフル稼働させる！

しかし、今回のシナリオをよく見てみると、スレッドBの実行にはスレッドAの結果を待つ必要があり、スレッドCの実行にはスレッドBの結果を待つ必要がある……

ということは、CPUをサボらせるしかないのか？

並列実行

直列実行と同様に、あらかじめ5回分の反復を計算しておき、その中の一部の値を取り出して、並列実行の基礎とする。

それ以降の計算サイクルは並列で計算できる。CPUは満員御礼だ。

もうひとつのシナリオ

以上が、小さなモジュールを直列から並列へ変換する考え方だ。

では、もう少し科学的な計算プロセスを仮定して、いわゆるパイプラインが自己反復に適用できるかを考えてみよう。こちらは、より一般的な意味での反復計算だ。

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

このシナリオでは、自己反復の結果が次のステップの初期条件になるため、パイプライン的な最適化の余地はまったくない。先ほどの並列最適化のように、すべての横線を重ね合わせると、スレッドAは5サイクル後のスレッドEの結果に基づくことになり、未来を予測しなければならない。そんなアルゴリズムを追加するくらいなら、むしろ実行効率を落としてしまう。

まとめ

演算モジュールの入力と出力に注目しよう。入力が外部から来るなら、パイプラインによる並列化が適用できる。演算モジュールが自己反復型なら、適用できない。

あとがき

1か月経って、ようやくこの「いわゆるスループット向上」の意味が分かってきた。つまり、並列度の高いプログラムでデータIOの効率を上げられる、ということで、各ステージに内部キューがあって、各ステップが独立して待機できる、ということだ。

いや、これってすごく普通の考え方だと思うんだけどな？ソフトウェアのモジュール化と組み立てにしたって、本来は各サブモジュールが自己完結して独立に動作し、つながっているのはデータIOだけだ。だったら、組み立てた先も並列なプログラムになる。この考え方はFPGAに限らず、あらゆるソフトウェア設計における基礎的な考え方であり、指針でもある。専門用語を並べて分かりにくくしているけれど、実は僕もこれまでパイプライン設計については、ほんの少し聞きかじった程度だったんだ。