体系ガイド · 基礎から応用へ

アウトオブオーダ実行と依存関係

ロード待ちの横で独立した加算を進める予定表から、発行・実行完了・リタイア、リネーミングと本当の依存を区別します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 待っている命令の横を先へ進む
  2. 独立した加算と依存する加算を並べる
  3. 実行の順番と確定の順番を照合する
  4. 名前の再利用と本当の依存を分ける
  5. 例外とメモリにも順序の条件がある
  6. 性能を見るときは依存鎖を揃える
  7. 同時に発行できる幅を変える
  8. ロードの待ちを変える課題と解答
  9. この記事をロゲイアに質問する理解を確かめる

待っている命令の横を先へ進む

CPUの中で命令を重ねて実行しても、前の命令の結果を必要とする計算は、その結果が届くまで進めません。一方、前の命令と関係のない計算まで同じ理由で待つ必要があるとは限りません。アウトオブオーダ実行は、命令をプログラムの順に取り込んだ後、入力と実行資源の準備ができた命令から実行する仕組みです。主教材のパイプラインで学ぶ依存と資源の不足を、命令ごとの予定表へ広げます。前提はレジスタ、ロード、加算、命令の取込みと書戻しの区別です。

最初に三つの時点を分けます。発行は、ここでは待機していた命令を実行器へ渡す時点と呼びます。実行完了は計算や読取りの結果が得られた時点です。リタイアは、その命令の結果をプログラムから見える状態へ順番に確定する時点です。資料によってissueが解読後のキューへの投入を指す場合もあるので、用語だけで表を比較せず、どの境界を呼んでいるかを確認してください。早く計算できた命令が、直ちに前の命令を追い越して確定するとは限りません。

独立した加算と依存する加算を並べる

四つの命令を考えます。I1はメモリからr1へ読むロード、I2はr1へ1を足してr2へ書く加算、I3はr4とr5を足してr3へ書く加算、I4はr3へ1を足してr6へ書く加算です。I2にはI1の値が必要ですが、I3には必要ありません。I4はI3に依存します。レジスタ名を眺めるだけでなく、各命令が読む値を、どの命令が最後に作るかで矢印を引きます。初期値をr4=10、r5=20、読んだメモリの値を7とすれば、正しい最終値はr2=8、r3=30、r6=31です。

説明用に、一度に1命令を発行でき、ロードは4サイクル、加算は1サイクル、完了した値は次のサイクルから使えるとします。取込みと解読は済み、四つとも待機中です。ロードをサイクル1に発行すると、I2は待ちますが、サイクル2にI3、サイクル3にI4を発行できます。依存のない仕事をロードの待ち時間に重ねたのです。この数字は特定CPUの性能値ではなく、依存関係を追うための仮定です。

実行の順番と確定の順番を照合する

表ではI3がサイクル2の終わり、I4が3の終わりに完了します。I1は4の終わりに完了し、I2は5に発行して5の終わりに完了します。さらに「完了の次サイクル以降に、1サイクルで1命令を順にリタイアする」と決めると、I1は5、I2は6、I3は7、I4は8で確定します。I3は早く終わっていても、未確定のI1とI2を飛び越えてリタイアしません。完了とリタイアの列を一つにすると、この仕組みを見失います。

同じ条件で順番どおりにしか発行できない場合、サイクル2から4にはI2が先頭で待ち、I3を発行できません。I2、I3、I4の発行は5、6、7になります。アウトオブオーダ実行で隠せたのは、この模型の一部の待ちです。ロード自体が4サイクルから1サイクルへ縮んだわけではありません。また最終時刻の差は、発行幅、リタイア幅、キューの大きさ、同時に使える実行器を変えると変化します。計算の途中経過と前提をセットで残してください。

命令発行完了(末尾)リタイア
I1: load r1145
I2: r2=r1+1556
I3: r3=r4+r5227
I4: r6=r3+1338

名前の再利用と本当の依存を分ける

同じレジスタ名が何度も現れる場合、以前の命令が読む値と、後の命令が上書きする値を分ける必要があります。例えばJ1がr1を読んでr2を作り、J2が新しい値をr1へ書くとします。J2を先に計算して古いr1を消すとJ1の答えが変わります。しかしJ1が必要なのは古い版のr1であり、J2の計算結果そのものではありません。レジスタリネーミングでは、見かけのr1に対して異なる物理レジスタを割り当て、複数の版を混ぜずに保持します。

これで名前の衝突を避けられても、I2がI1のロード値を必要とする依存は消えません。計算に必要な値がまだ存在しないからです。リネーミングが依存を全てなくす、と説明しないでください。さらに物理レジスタや待機枠にも数の限りがあります。前のロードが長く待つ間に若い命令の結果が溜まると、確定できない仕事が窓を埋め、新しい命令を取り込めなくなります。独立した命令がソースにあることと、実際に同時実行へ使える場所があることも別の条件です。

例外とメモリにも順序の条件がある

I1のロードが許されないアドレスだった場合を考えます。I3の計算がすでに終わっていても、CPUはプログラムがI1で例外を起こしたことに対応する状態を提示する必要があります。確定前の結果を保持する仕組みは、そのためにも使われます。ただし、破棄した計算がキャッシュなどへ痕跡を残す可能性と、レジスタの値として確定することは別です。投機実行があることを理由に、例外処理や側信道を一つの説明へまとめないでください。

メモリへのロードとストアには、同じアドレスを指すかという追加の依存があります。ポインタの値が決まるまで別の場所だと判断できないこともあります。CPUの実行順、コンパイラの並べ替え、ISAが別のコアに約束するメモリ順序はそれぞれ異なる層です。単一スレッドのこの予定表だけで、共有変数の同期が不要になるとは言えません。複数スレッドの可視性には言語のメモリモデルと同期操作を使います。volatileを付ければ必要な同期が全て成立するという結論にもなりません。

性能を見るときは依存鎖を揃える

一つの変数へ加算を繰り返すループと、四つの独立した変数へ加算するループを比べると、後者は複数の演算を重ねられる候補になります。しかし加算回数や入力を揃えずに比べれば、依存の効果を測ったことにはなりません。コンパイラがループを数式へ置き換えたりSIMD化したりする場合もあります。実験では計算結果を実際に使い、生成命令を読んで、どの依存鎖が残ったかを確認します。Cの符号付き整数のオーバーフローを速度を出す手段にしてはいけません。

依存を減らすために集計順を変えると、浮動小数点では丸めの結果が変わることがあります。同じ数学式だから同じビット列になるとは限りません。必要な精度を定め、許される変換かを先に判断します。またメモリの待ちを隠すには、独立したロードのアドレスを早く計算できることも関係します。連結リストのように次の場所が前の値から決まる処理では、配列の走査と同じ機会がありません。実時間は依存以外の要因も含むので、一回の差を発行幅の実測値へ換算しないでください。

同時に発行できる幅を変える

追加の模型として、発行幅だけを2へ変え、独立した加算二つの入力が同時に揃っている場合を考えます。二つの加算器へ渡せるなら同じサイクルへ発行する候補になりますが、加算器が一つなら発行枠が空いていても両方を実行できるとは限りません。発行幅、実行器の入口、演算の完了までの遅延はそれぞれ別の制約です。さらにリタイア幅を1のままにすると、二つが同時に完了しても一度に二つ確定しません。予定表の列ごとに変えた条件を記し、幅を一つ増やしたことから全体の倍率を決めないようにします。

ロードの待ちを変える課題と解答

課題は、I1のロードだけを8サイクルへ延ばした場合の表を作ることです。ほかの規則は変えません。解答ではI3とI4の発行は2と3のままで、I1の完了は8、I2の発行と完了は9です。リタイアはI1が9、I2が10、I3が11、I4が12になります。独立な加算が早く終わっても、確定の先頭で待つロードを消せません。表の右側に「完了したが確定待ち」という状態を書き込むと、計算が進むことと全体の遅れが残ることを同時に説明できます。

次にI3をr3=r2+r5へ変えると、I1→I2→I3→I4という一本の依存鎖になります。リネーミングでレジスタを増やしても、必要な値の到着を先取りできません。これが追加課題の解答です。逆に独立な命令を増やしても、発行器が一つなら一サイクルに何でも発行できるわけではありません。値、資源、確定順の三つを別々に説明できれば、このガイドの到達点です。続く分岐予測とSIMDのガイドでは、先へ進む場所の予測と、一命令で扱うデータ数という別の方向から性能を考えます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 7

AI基盤へ進む · STEP 4

学習コースから次を選ぶ