ソフトウェアパイプライン
下記のようなループ例を考える。
この例では、A(i), B(i), C(i), がそれぞれiを操作する命令であり、互いに依存関係がある。
すなわち A(i) は B(i) の開始前に完了している必要がある。例えば、A はメモリからレジスタにデータをロードし、Bがデータに算術演算を行い、Cがデータをメモリに書き戻す。しかし、それぞれが異なるiの値に対して依存がないと仮定すると、A(2) は A(1) が完了する前に開始することができる。ソフトウェアパイプラインを考えない場合には、コードは下記の順序で実行される。
各命令は完了に 3 クロックかかるとする(制御ループのコストを考えない)。また(現代的なシステムでは一般的だが)実行中の命令に対して依存関係がなければ命令を各サイクルで割り当てることができるものとする。パイプライン化しない場合には、各ループが7サイクル(3 + 3 + 1, A(i+1) は C(i) を待つ必要がないため)かかることになる。
ソフトウェアパイプラインによって下記のように命令列を並べ替えると、
毎サイクルで命令を割り当てることができ、全体が9サイクル、ループが平均 3 サイクルで実行できる。