命令スケジューリング
命令スケジューリングは、通常一つのブロックについて実行される。ブロックの振る舞いを保持したままブロック内の命令の再配置を行うかどうかを決定するためにはデータ依存の概念が必要である。依存には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 へのエッジが引かれる。循環参照を除いて考えれば、依存グラフは有向非環状グラフである。すると、このグラフから得られる位相幾何学的ソートが有効な命令スケジューリングである。グラフのエッジは通常依存のレイテンシを示す。これは、パイプラインがストールせずにその命令に進めるクロック数である。