|
命令スケジューリング（めいれいスケジューリング、英: 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"): も存在する。二つの命令が同じ場所を読み出す。入力の依存性はこの二つの命令の実行順序を制限しないが、配列の要素をスカラーに置き換える場合に有用である。 三種類の依存関係を確実に考慮できるよう、依存関係のグラフを構築する。これは有向グラフであり、各ノードが命令を示し、I1 が依存関係のために I2 より先に実行する必要がある場合I1 から I2 へのエッジが引かれる。循環参照を除いて考えれば、依存グラフは有向非環状グラフである。すると、このグラフから得られる位相幾何学的ソートが有効な命令スケジューリングである。グラフのエッジは通常依存のレイテンシを示す。これは、パイプラインがストールせずにその命令に進めるクロック数である。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「命令スケジューリング」の詳細全文を読む スポンサード リンク
|