この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。
出典を追加して記事の信頼性向上にご協力ください。（2009年1月）

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

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

順序を並べ替えてパイプラインのストールを防ぐ

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

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

1 データハザード

2 アルゴリズム

3 命令スケジューリングの順序

4 命令スケジューリングの種類

5 関連項目

データハザード

命令スケジューリングは、通常一つのブロックについて実行される。ブロックの振る舞いを保持したままブロック内の命令の再配置を行うかどうかを決定するためにはデータ依存の概念が必要である。依存には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"): も存在する。二つの命令が同じ場所を読み出す。入力の依存性はこの二つの命令の実行順序を制限しないが、配列の要素をスカラーに置き換える場合に有用である。

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

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

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

既にスケジュールされた命令によって使用中のプロセッサの資源は記録する。候補となる命令が使用中の資源を使用する場合には、その優先順位が下げられる。

候補となる命令が、関連するレイテンシ以上に前の命令の近くにスケジュールされると、その優先順位が下げられる。

候補の命令がグラフのクリティカルパス上にある場合には、優先度を上昇させる。この方法はある種の先読みを必要とする。

候補を選択する事により多数の入力が作られる場合には、優先度を上昇させる。この方法はスケジューラに大きな自由度を与える傾向がある。

命令スケジューリングの順序

命令スケジューリングは、レジスタ割り付けの前後あるいはその両方で実行することができる。レジスタ割付の前に実行することの利点は、並列性が最大化されることである。逆に問題は、レジスタ割り当ての際割り当てられないほど多数のレジスタを必要とすることである。これにより、メモリへの書き出し、メモリからの読み込みのコードを生成せざるを得ず、問題のコードの性能が低下する。

スケジュール対象のアーキテクチャに組み合わせられない命令列がある場合には、レジスタ割り当ての後に命令スケジューリングを実行する必要がある。二回目のスケジューリングを行うと、メモリ読み書きのコードの位置を改善することができる。

スケジューリングがレジスタ割り当ての後にのみ実行されると、レジスタ割り当てによって導入された偽の依存関係により、スケジュールが移動できる命令の数が制限される可能性がある。
命令スケジューリングの種類

命令スケジューリングにはいくつかの種類がある。
基本ブロックスケジューリング: 命令は基本ブロックの境界を越えて移動しない

大域的スケジューリング: 命令は基本ブロックの境界を越えて移動できる。

Modulo Scheduling: 別名ソフトウェアパイプライン。ループを繰り返しを並列的に実行する命令スケジューリングの形態である。

トレーススケジューリング: 最も多く実行される制御フローのパスを最適化する大域的スケジューリングの一形態である。

関連項目

コード生成

レジスタ割り付け

命令選択


更新日時:2018年10月23日(火)06:32
取得日時:2019/08/20 17:56