命令スケジューリング

命令スケジューリング（めいれいスケジューリング、英: Instruction scheduling）は、コンパイラ最適化において考慮されるもののひとつで、具体的な内容はターゲットのマイクロアーキテクチャに依るが、より効率的にコードが実行されるよう、演算結果に影響を与えない範囲で命令の順序を入れ替え、より良い順序にするものである。例えば命令パイプラインの深いプロセッサなどで、そのプロセッサの命令レベルの並列性を可能な限り引き出すことが目標となる。
具体例としては、例えば、コードの意味を変えずに以下のようなことを実現する。
パイプラインのストールは、構造的なハザード(プロセッサのハードウェア資源の制限)、データハザード（ある命令の出力が他の命令の実行に必要）、制御ハザード（分岐）によって引き起こされる。
データハザード.
命令スケジューリングは、通常一つのブロックについて実行される。ブロックの振る舞いを保持したままブロック内の命令の再配置を行うかどうかを決定するためには"データ依存"の概念が必要である。依存には3つの種類があり、3種類のが存在する。
理論的には、さらにもう一種類Read after Read (RAR あるいは "Input"): も存在する。二つの命令が同じ場所を読み出す。入力の依存性はこの二つの命令の実行順序を制限しないが、配列の要素をスカラーに置き換える場合に有用である。
三種類の依存関係を確実に考慮できるよう、依存関係のグラフを構築する。これは有向グラフであり、各ノードが命令を示し、I1 が依存関係のために I2 より先に実行する必要がある場合I1 から I2 へのエッジが引かれる。循環参照を除いて考えれば、依存グラフはである。すると、このグラフから得られるが有効な命令スケジューリングである。グラフのエッジは通常依存のレイテンシを示す。これは、パイプラインがストールせずにその命令に進めるクロック数である。
アルゴリズム.
位相幾何学的ソートの結果を見つける最も単純なアルゴリズムで、しばしば用いられるのがリストスケジューリングである。概念的には依存グラフの入力を繰り返し選択し現在の命令を追加してグラフから削除する。これにより別の命令が入力となるが、それらもまたスケジューリングの対象となる。アルゴリズムは、グラフが空になると終了する。
よりよいスケジュール結果に到達するためにはストールを避けなければならない。これは、スケジュールする次の命令を選択することにより決定できる。多数の発見的な方法が一般的に使用されている。
命令スケジューリングの順序.
命令スケジューリングは、レジスタ割り付けの前後あるいはその両方で実行することができる。レジスタ割付の前に実行することの利点は、並列性が最大化されることである。逆に問題は、レジスタ割り当ての際割り当てられないほど多数のレジスタを必要とすることである。これにより、メモリへの書き出し、メモリからの読み込みのコードを生成せざるを得ず、問題のコードの性能が低下する。
スケジュール対象のアーキテクチャに組み合わせられない命令列がある場合には、レジスタ割り当ての後に命令スケジューリングを実行する必要がある。二回目のスケジューリングを行うと、メモリ読み書きのコードの位置を改善することができる。
スケジューリングがレジスタ割り当ての後にのみ実行されると、レジスタ割り当てによって導入された偽の依存関係により、スケジュールが移動できる命令の数が制限される可能性がある。
命令スケジューリングの種類.
命令スケジューリングにはいくつかの種類がある。