命令スケジューリング

コンピュータサイエンスにおいて、命令スケジューリングは、命令レベルの並列性を向上させるために使用されるコンパイラ最適化であり、命令パイプラインを備えたマシンのパフォーマンスを向上させます。簡単に言えば、コードの意味を変えずに次のことを行います。

• 命令の順序を変更することでパイプラインの停止を回避します。 ^[1]
• 不正な操作や意味的に曖昧な操作 (通常は微妙な命令パイプラインのタイミングの問題やインターロックされていないリソースに関連する操作) は避けてください。

パイプラインの停止は、構造上のハザード (プロセッサ リソースの制限)、データ ハザード (ある命令の出力が別の命令で必要になる)、および制御上のハザード (分岐) によって発生する可能性があります。

命令のスケジューリングは、通常、単一の基本ブロックに対して行われます。ブロックの命令を特定の方法で並べ替えることで、そのブロックの動作が維持されるかどうかを判断するには、データ依存性の概念が必要です。依存性には 3 つの種類があり、これらは 3 つのデータ ハザードでもあります。

1. 書き込み後の読み取り (RAW または「True」): 命令 1 は、後で命令 2 で使用される値を書き込みます。命令 1 が最初に来る必要があります。そうでないと、命令 2 は新しい値ではなく古い値を読み取ります。
2. 読み取り後の書き込み (WAR または「Anti」): 命令 1 は、後で命令 2 によって上書きされる場所を読み取ります。命令 1 が最初に来る必要があります。そうでないと、古い値ではなく新しい値が読み取られます。
3. 書き込み後の書き込み (WAW または「出力」): 2 つの命令は両方とも同じ場所に書き込みます。これらは元の順序で発生する必要があります。

技術的には、4 番目のタイプである Read after Read (RAR または「入力」) があります。両方の命令が同じ場所を読み取ります。入力依存性は 2 つのステートメントの実行順序を制約しませんが、配列要素のスカラー置換に役立ちます。

3 種類の依存関係を尊重するために、依存関係グラフを作成します。依存関係グラフは、各頂点が命令であり、依存関係により I _{1 がI 2}の前に来なければならない場合に I ₁からI 2 への_{エッジが存在する}有向グラフです。ループで運ばれる依存関係を除外すると、依存関係グラフは有向非巡回グラフになります。この場合、このグラフの任意の位相ソートは有効な命令スケジュールになります。グラフのエッジには通常、依存関係のレイテンシのラベルが付けられます。これは、パイプラインが停止せずにターゲット命令を続行できるようになるまでに経過する必要があるクロック サイクル数です。

トポロジカル ソートを見つけるための最も単純なアルゴリズムは頻繁に使用され、リスト スケジューリングとして知られています。概念的には、依存関係グラフのソースを繰り返し選択し、それを現在の命令スケジュールに追加して、グラフから削除します。これにより、他の頂点がソースになる可能性があり、その場合、そのソースもスケジューリングの対象になります。グラフが空の場合、アルゴリズムは終了します。

適切なスケジュールを作成するには、ストールを防ぐ必要があります。これは、次にスケジュールする命令の選択によって決まります。一般的に使用されるヒューリスティックはいくつかあります。

• すでにスケジュールされている命令によって使用されるプロセッサ リソースが記録されます。候補が占有されているリソースを使用する場合、その優先順位は下がります。
• 候補が関連するレイテンシよりも先行候補に近い時間にスケジュールされている場合、その優先順位は下がります。
• 候補がグラフのクリティカル パス上にある場合、その優先度が上がります。このヒューリスティックは、ローカルな決定プロセスにおいて、何らかの形で先読みを行うものです。
• 候補を選択すると多くの新しいソースが作成される場合、その優先度が上がります。このヒューリスティックにより、スケジューラの自由度が増す傾向があります。

命令のスケジューリングは、レジスタ割り当ての前または後、あるいはその前後両方で実行できます。レジスタ割り当ての前に行う利点は、最大限の並列処理が得られることです。レジスタ割り当ての前に行う欠点は、レジスタ アロケータが使用可能なレジスタ数を超える数のレジスタを使用する必要がある可能性があることです。これにより、スピル/フィル コードが導入され、問題のコード セクションのパフォーマンスが低下します。

スケジュールされているアーキテクチャに、潜在的に不正な組み合わせを持つ命令シーケンスがある場合 (命令インターロックが不足しているため)、レジスタ割り当て後に命令をスケジュールする必要があります。この 2 回目のスケジュール パスにより、スピル/フィル コードの配置も改善されます。

レジスタ割り当て後にのみスケジューリングが行われる場合、レジスタ割り当てによって誤った依存関係が導入され、スケジューラによる命令移動の量が制限されます。

命令スケジューリングにはいくつかの種類があります。

1. ローカル(基本ブロック)スケジューリング: 命令は基本ブロックの境界を越えて移動できません。
2. グローバル スケジューリング: 命令は基本ブロックの境界を越えて移動できます。
3. モジュロ スケジューリング:ソフトウェア パイプラインを生成するアルゴリズム。これは、内部ループの異なる反復をインターリーブすることで命令レベルの並列性を高める方法です。
4. トレース スケジューリング: グローバル スケジューリングの最初の実用的なアプローチであるトレース スケジューリングは、最も頻繁に実行される制御フロー パスを最適化しようとします。
5. スーパーブロック スケジューリング: トレースの「サイド エントランス」で制御フロー パスをマージしない、トレース スケジューリングの簡略化された形式。代わりに、複数のスケジュールでコードを実装できるため、コード ジェネレーターが大幅に簡素化されます。

GNU コンパイラ コレクションは、-march (命令セットとスケジューリングの両方) または(スケジューリングのみ) フラグを使用して命令スケジューリングを実行することで知られるコンパイラの 1 つです。このコンパイラは、タスクを実行するため-mtuneに、各マイクロアーキテクチャの命令のレイテンシと並列実行可能な命令 (または同等に、各「ポート」を使用する) の記述を使用します。この機能は、GCC がサポートするほぼすべてのアーキテクチャで利用できます。^[2]

バージョン12.0.0までは、 LLVM /Clangの命令スケジューリングは、命令セットとスケジューリングの両方に対してスイッチ-march（LLVM用語ではスイッチと呼ばれる）のみを受け入れることができました。バージョン12では、x86のみで（ ）target-cpuのサポートが追加されました。 ^[3]-mtunetune-cpu

レイテンシとポートの使用状況に関する情報源には次のものがあります。

• GCC と LLVM;
• x86アーキテクチャに関する膨大なデータをまとめたAgner Fog氏[ 4 ^]
• InstLatx64はAIDA64を使用してx86 CPU上のデータを収集します。^[5]

LLVMはllvm-exegesisすべてのマシンで使用可能であり、特にx86以外のマシンで情報を収集するために使用可能である。^[6]

• 分岐予測
• コード生成
• 指導ユニット
• アウトオブオーダー実行

• フィッシャー、ジョセフ A. (1981)。「トレース スケジューリング: グローバル マイクロコード圧縮のテクニック」。IEEE Transactions on Computers。30 ( 7): 478–490。doi :10.1109/ TC.1981.1675827。S2CID 1650655  。(トレーススケジュール)
• Nicolau, Alexandru; Fisher, Joseph A. (1984)。「非常に長い命令語アーキテクチャで利用可能な並列性の測定」IEEE Transactions on Computers。33 ( 11 )。(パーコレーションスケジューリング)
• Bernstein, David; Rodeh, Michael (1991 年 6 月)。「スーパースカラー マシンのグローバル命令スケジューリング」(PDF)。ACM 、SIGPLAN '91 プログラミング言語の設計と実装に関する会議の議事録。(グローバルスケジュール)
• Cordes、Peter。「アセンブリ - x86 / x64 asm での命令の並べ替え - 最新の CPU によるパフォーマンスの最適化」。Stack Overflow。