命令スケジューリング

命令スケジューリング（めいれいスケジューリング、英: Instruction scheduling）は、コンパイラ最適化において考慮されるもののひとつで、具体的な内容はターゲットのマイクロアーキテクチャに依るが、より効率的にコードが実行されるよう、演算結果に影響を与えない範囲で命令の順序を入れ替え、より良い順序にするものである。例えば命令パイプラインの深いプロセッサなどで、そのプロセッサの命令レベルの並列性を可能な限り引き出すことが目標となる。

具体例としては、例えば、コードの意味を変えずに以下のようなことを実現する。

順序を並べ替えてパイプラインのストールを防ぐ
不正な、あるいは意味的にあいまいな操作(命令パイプラインのタイミング問題や、同期が取れていないハードウェア資源など）を避ける

パイプラインのストールは、構造的なハザード(プロセッサのハードウェア資源の制限)、データハザード（ある命令の出力が他の命令の実行に必要）、制御ハザード（分岐）によって引き起こされる。

データハザード

命令スケジューリングは、通常一つのブロックについて実行される。ブロックの振る舞いを保持したままブロック内の命令の再配置を行うかどうかを決定するためにはデータ依存の概念が必要である。依存には3つの種類があり、3種類のデータハザードが存在する。

Read after Write (RAW あるいは "True"): 命令 1 が後で命令 2 で必要な値を書き込む。命令 1 が先に実行されなければ、命令 2 が新しい値でなく古い値を読み込んでしまう。
Write after Read (WAR あるいは "Anti"): 命令 1 が後で命令 2 で上書きされる値を読み込む。命令 1 が先に実行されなければ、古い値でなく新しい値を読み込んでしまう。
Write after Write (WAW あるいは "Output"):二つの命令が同じ箇所に値を書き込む。元の順序で実行されなければならない。

理論的には、さらにもう一種類Read after Read (RAR あるいは "Input"): も存在する。二つの命令が同じ場所を読み出す。入力の依存性はこの二つの命令の実行順序を制限しないが、配列の要素をスカラーに置き換える場合に有用である。

三種類の依存関係を確実に考慮できるよう、依存関係のグラフを構築する。これは有向グラフであり、各ノードが命令を示し、I₁ が依存関係のために I₂ より先に実行する必要がある場合I₁ から I₂ へのエッジが引かれる。循環参照を除いて考えれば、依存グラフは有向非環状グラフである。すると、このグラフから得られる位相幾何学的ソートが有効な命令スケジューリングである。グラフのエッジは通常依存のレイテンシを示す。これは、パイプラインがストールせずにその命令に進めるクロック数である。

アルゴリズム

位相幾何学的ソートの結果を見つける最も単純なアルゴリズムで、しばしば用いられるのがリストスケジューリングである。概念的には依存グラフの入力を繰り返し選択し現在の命令を追加してグラフから削除する。これにより別の命令が入力となるが、それらもまたスケジューリングの対象となる。アルゴリズムは、グラフが空になると終了する。

よりよいスケジュール結果に到達するためにはストールを避けなければならない。これは、スケジュールする次の命令を選択することにより決定できる。多数の発見的な方法が一般的に使用されている。

既にスケジュールされた命令によって使用中のプロセッサの資源は記録する。候補となる命令が使用中の資源を使用する場合には、その優先順位が下げられる。
候補となる命令が、関連するレイテンシ以上に前の命令の近くにスケジュールされると、その優先順位が下げられる。
候補の命令がグラフのクリティカルパス上にある場合には、優先度を上昇させる。この方法はある種の先読みを必要とする。
候補を選択する事により多数の入力が作られる場合には、優先度を上昇させる。この方法はスケジューラに大きな自由度を与える傾向がある。