パイプラインハザードの防ぎ方

超高性能プログラミング技術のメモ（４）
自分の備忘録として、プログラミング技術のメモを書き残しています。
今回は、アセンブラならではのループの組み方について書いておきます。

ハザードが起こらないパターン

前回書いたように、最小限の基本的な演算処理、ロード命令LD→演算命令OP→ストア命令STの順序では、必ずレジスタの使用順序がRAW（Read after Write）型になり、パイプラインハザードが発生します。これは、レジスタの使用順序が時間に逆行するためです。仮に、処理時間を逆行しないように並べ替えてみると、下の図のように、演算命令OP→ロード命令LD→ストア命令STの順になります。

XMM1レジスタは、pipeline1で何かしらの演算（加算や乗算など）命令OPに読み出され、pipeline2のメモリロード命令LDで書き込まれます。XMM1に格納されたデータは、pipeline１で使用され、pipeline2の実行段階では用済みとなっているため、pipeline2で上書きしても問題ありません。そのため、pipeline2ではpipeline1の実行完了を待つことなく実行開始でき（＝ハザードが発生せず）、処理の待ち時間がありません。これは、XMM2についても同様です。

XMM3レジスタは、pipeline1の演算命令OPの結果が書き込まれ、pipeline4でメモリストア命令STで読み込まれます。これは、いわゆるRAW（Read After Write）型ですので、パイプラインハザードが発生します。すなわち、pipeline1の処理が完了するまでは、pipleline4の処理を始めることができません。しかしながら、pipeline1とpipeline4の間にロード命令を２つ差し込んだおかげで、pipeline4の実行開始をpipeline1の実行完了まで先送りすることができています。レジスタへの書き込み時間は非常に高速なので、pipeline1のXMM3への書き込みは瞬時に完了します。そのため、ロード命令2個を差し込むだけで充分な先送りができます。

このような命令順序ばかりであれば、処理はほぼ停止せずに稼働し続けることができますが、上の図は正しい計算を行っていません。演算処理としては正しいですが、計算アルゴリズムとしては意味不明な処理を行っています。では、この理想的な命令順を実現するのは不可能かというと、そうでもありません。

反復処理（ループ）なら理想的命令順を作れる

基本的な演算処理（ロード命令LD→演算命令OP→ストア命令ST）をN回繰り返す処理を考えます。この時、反復する基本的演算処理を２回並べて（ループ展開して）書き下すと下の図のようになります。

この図で、点線で囲まれた部分が、元の反復処理の基本的演算処理になります。そして、実線で囲った部分は、理想的な命令順序に非常に近いことが分かります。すなわち、反復処理を実線の囲み部分にすれば（ループをずらせば）、ほぼハザードが発生せずに反復処理を行うことができることになります。

ただし、上の図からも分かる通り、反復処理の前にロード命令LDを２回実行しておき、反復処理の後は演算命令OPとストア命令STを実行しなければなりません。そのため、元の反復回数がN回の場合、ループずらしを行うと反復回数はN-1回になります。とはいえ、N-1回は理想に近い命令順で処理できるため、非常に高速になります。

最後に、現状のままだとXMM3がハザードを発生させてしまうので、ロード命令LDとストア命令STを入れ換えます。

このように、反復処理（ループ）する部分をズラす事で理想的な命令順序を作り出すことができます。

このテクニックは、アセンブラプログラムでは比較的よく見るテクニックですが、高級プログラミング言語によるプログラムではまず見ません。なぜなら、高級プログラミング言語では、ロード命令や演算命令やストア命令を明示的に個別指定する方法がないからです。命令順序の入れ替えは、通常コンパイラの最適化機能で自動的に行われます。

また、ループをズラすテクニックは、通常、コンパイラの最適化でも行われません。なぜなら、反復部分を変更するのは、処理の結果を変えてしまう可能性が高い危険な最適化だからです。人間から見れば問題ないことも、コンパイラの構文解析や意味解析では読み解くのが難しいため、ループを越えた最適化は行わないことが多いです。（一部のコンパイラには積極的最適化を行う機能があったりします）

結局、このテクニックが人間による高性能化がコンパイラの最適化を超えるポイントになってきます。

まとめ

今回は、高性能化に重要なループをずらすテクニックについて説明しました。