命令スケジューリング

命令スケジューリングとは、コンピュータのコンパイラが実行する重要な最適化プロセスの一つです。その目的は、プログラムの論理的な意味や計算結果を変えることなく、命令の実行順序を調整し、ターゲットとするプロセッサの性能を最大限に引き出すことにあります。特に、多くの現代的なプロセッサが採用している命令パイプライン構造の効率を向上させる上で、この技術は不可欠です。

プロセッサは通常、命令を複数の段階（フェッチ、デコード、実行など）に分けて並行処理します。これがパイプライン処理ですが、命令間の依存関係やハードウェア資源の制約により、パイプラインが一時的に停止するストールが発生することがあります。命令スケジューリングは、このようなストールを最小限に抑えるために行われます。

ストールを引き起こす主な要因には、以下の種類があります。

構造ハザード: プロセッサ内の特定のハードウェア資源が同時に複数の命令から要求される場合に発生します。
データハザード: ある命令の実行結果が、後続の命令の入力として必要とされる場合に発生します。結果が準備できる前に後続の命令が実行されると、誤った結果を読み込んでしまいます。
制御ハザード: 分岐命令などが原因で、次に実行すべき命令が確定しない場合に発生します。パイプラインに誤った命令が流入するのを防ぐため、停止や予測失敗時のペナルティが発生します。

データ依存とハザード

命令スケジューリング、特に基本ブロック内での処理では、データハザードの原因となる命令間のデータ依存が中心的な問題となります。主要なデータ依存のタイプは以下の通りです。

Read after Write (RAW): 命令Aが書き込む値を、その後に命令Bが読み込む場合。Aが完了する前にBが実行されると、古い値を読み取ってしまいます。
Write after Read (WAR): 命令Aが読み込む場所へ、その後に命令Bが書き込む場合。BがAより先に実行されると、Aは新しい値を読み取ってしまいます。
Write after Write (WAW): 命令Aが書き込む場所へ、その後に命令Bが書き込む場合。元のプログラム順序とは異なる順序で実行されると、最終的にその場所に残る値が元のプログラムと変わってしまいます。

理論的には、Read after Read (RAR)という依存も考えられますが、これは通常、命令の実行順序に制約を与えません。

依存関係の表現とスケジューリング

これらの依存関係を視覚的かつ形式的に表現するために、依存グラフが用いられます。これは有向グラフであり、各ノードは個々の命令を示し、ある命令I1が別の命令I2よりも先に実行される必要がある場合、I1からI2へ向かうエッジが引かれます。循環参照がない限り、このグラフは有向非環状グラフ (DAG) となります。グラフのエッジには、依存関係を満たしてから後続命令を実行可能になるまでの遅延時間（レイテンシ）が付加されるのが一般的です。有効な命令スケジューリングは、この依存グラフの位相幾何学的ソートによって得られる順序のうちの一つとなります。

スケジューリングアルゴリズム

依存グラフから有効なスケジューリング順序を見つけ出すための最も基本的なアルゴリズムの一つにリストスケジューリングがあります。これは、実行可能な命令のリストの中から、何らかの基準に基づいて次に実行する命令を選択し、グラフから削除していくプロセスを繰り返すものです。より性能の良いスケジュール（ストールを最小限に抑える順序）を得るためには、命令選択の際に様々なヒューリスティック（発見的手法）が利用されます。

利用中のハードウェア資源との競合を避けるような命令を優先する。
依存関係によるレイテンシを考慮し、後続命令の実行開始が遅れないように、依存元命令を早めにスケジュールする。
依存グラフのクリティカルパス（実行に最も時間がかかる可能性のあるパス）上の命令を優先的にスケジュールすることで、全体の実行時間を短縮しようとする。
ある命令をスケジュールすることで、後続の実行可能命令（依存グラフで入力となるノード）が増える場合、そのような命令を優先してスケジューラの自由度を高める。

レジスタ割り付けとの関連

命令スケジューリングは、コンパイル過程における別の重要な最適化であるレジスタ割り付け（プログラム変数や中間結果をプロセッサのレジスタに割り当てる処理）と密接に関連しています。スケジューリングはレジスタ割り付けの前、後、あるいはその両方で行われる可能性があります。

レジスタ割り付け前にスケジューリングを行う利点は、依存関係をより正確に把握しやすく、命令レベルの並列性を最大限に引き出しやすい点です。しかし、結果として必要なレジスタ数が増え、レジスタ不足によるメモリへの退避・読み込み（スピルコード）が増加し、かえって性能が低下するリスクもあります。

レジスタ割り付け後にスケジューリングを行う場合は、レジスタ割り付けによって導入される「偽の依存」（同じレジスタを再利用することによる見かけ上の依存）がスケジューリング可能な範囲を制限する可能性があります。ただし、レジスタ割り付け後に生成されたスピルコードの位置を調整することで、性能を改善できる場合もあります。アーキテクチャによっては、特定の命令シーケンスが許可されないため、レジスタ割り付け後のスケジューリングが必要となることもあります。

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

命令スケジューリングは、その適用範囲によっていくつかの種類に分類されます。

基本ブロックスケジューリング: プログラムの基本的な実行単位である基本ブロックの内部でのみ命令の順序を調整します。最もシンプルで一般的な形式です。
大域的スケジューリング: 基本ブロックの境界を越えて、異なるブロック間でも命令を移動させます。より広い範囲での最適化が可能になります。
Modulo Scheduling (ソフトウェアパイプライン): ループの最適化に特化した大域的スケジューリングの一種で、ループの異なる繰り返し（イテレーション）に属する命令を並行して実行できるように調整します。
トレーススケジューリング: プログラムの実行経路のうち、最も頻繁に実行されると予測される「トレース」と呼ばれる経路に沿って大域的なスケジューリングを行う手法です。

命令スケジューリングは、現代の高性能プロセッサがその能力を十分に発揮するために不可欠な、コンパイラ最適化技術の根幹をなす要素の一つと言えるでしょう。

もう一度検索