高性能コンピューティング論２ 第5回 Out-of-Order実行機構 高性能コンピューティング学講座 三輪　忍 miwa@is.uec.ac.jp

本日の講義内容 Out-of-Order スーパスカラプロセッサの基本構造の復習 レジスタリネーミングの実際 命令スケジューリングの実際 高性能コンピューティング論２ 本日の講義内容 Out-of-Order スーパスカラプロセッサの基本構造の復習 レジスタリネーミングの実際 命令スケジューリングの実際 正確な例外

Out-of-Orderスーパスカラ プロセッサの基本構造の復習 高性能コンピューティング論２ Out-of-Orderスーパスカラ プロセッサの基本構造の復習

スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令キュー 演算器 フロントエンド Front-end バックエンド 高性能コンピューティング論２ スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 キャッシュ 命令キュー リネーム ロジック 演算器 フェッチ Fetch リネーム Rename ディスパッチ Dispatch スケジュール Schedule 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB フロントエンド Front-end バックエンド Back-end ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

命令スケジューリング add r4 = r1 + r2 add r5 = r4 + r3 add r8 = r6 + r7 add 高性能コンピューティング論２ 命令スケジューリング 命令スケジューリング 命令キューの中から実行可能な命令を発見 実行可能 ＝ 制約（次スライド）を満たす 実行可能な命令の中から次に実行すべき命令を選択 バックエンド： スケジュールされた命令を実際に実行 命令ウィンドウ 　（スケジューリング･ウィンドウ）： スケジュール対象の命令の集合 命令キュー内の全命令 フロントエンド： 命令ウィンドウを下流に拡大 add r4 = r1 + r2 add r5 = r4 + r3 add r8 = r6 + r7 命令ウィンドウ add r8 = r8 + 1 sub r5 = r5 – r8 bz r5

命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 「演算器など，計算資源が空いていなければ実行できない」 高性能コンピューティング論２ 命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 「演算器など，計算資源が空いていなければ実行できない」 命令間の依存：「実行されるプログラム側の問題」 先行制約：命令間の先行関係の制約 制御依存 (control dependence) 「分岐命令があると，後の命令は先に実行できない」 データ依存 (data dependence) 「2つの命令が同一のロケーションを定義/参照していると， 　後の命令は先に実行できない」 パイプライン･ハザードと同じ だが 「どの命令にインターロックかけるか？」より，簡潔 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

データ依存 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is 高性能コンピューティング論２ データ依存 後 続 命 令 Read Write 先行命令 入力依存 (input) 逆依存 (anti) フロー依存 (flow) 出力依存 (output) Ip Ip Is Is time time Ip Ip Is Is time time ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

真のデータ依存，偽のデータ依存 フロー依存：真の (true) データ依存 入力依存 逆依存，出力依存：偽の (false) データ依存 高性能コンピューティング論２ 真のデータ依存，偽のデータ依存 フロー依存：真の (true) データ依存 データの授受のため 先行制約を生じる 入力依存 一般に，複数の読み出しがあるため 先行制約を生じない 逆依存，出力依存：偽の (false) データ依存 ロケーションの再利用のため 原理的には，先行制約を生じない リネーミングにより解消 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r1 = r1 << 2 高性能コンピューティング論２ データ依存の具体例 ld r1 = *($sp) フロー依存 sla r2 = r1 << 1 逆依存 sla r1 = r1 << 2 add r4 = r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

データ依存の具体例 ld r1 = *($sp) sla r1 << 1 = r2 sla r1 << 2 = 高性能コンピューティング論２ データ依存の具体例 ld r1 = *($sp) sla r1 << 1 = r2 sla r1 << 2 = add r4 = r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r3 r1 = r1 高性能コンピューティング論２ データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 逆依存 sla r3 r1 = r1 << 2 add r4 = r3 r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

リネーミングの真髄 要は，「1つのデータに1つのロケーション」 データの寿命 r1 r2 r3 r4 ld r1 = *($sp) sla 高性能コンピューティング論２ リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r1 << 1 = r2 sla r3 r1 = r1 << 2 定義 add r4 = r3 r1 + r2 参照 time 要は，「1つのデータに1つのロケーション」 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

リネーミングの真髄 要は，「1つのデータに1つのロケーション」 データの寿命 r1 r2 r3 r4 ld r1 = *($sp) sla 高性能コンピューティング論２ リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r1 << 1 = r2 sla r1 << 2 = r3 定義 add r2 = r4 + r3 参照 time 要は，「1つのデータに1つのロケーション」 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

リネーミングの問題 r1 を r3 にリネーム 「1つのデータに1つのロケーション」が理想だが… コンパイラならできるが， 高性能コンピューティング論２ リネーミングの問題 r1 を r3 にリネーム コンパイラならできるが， HW が r3 をどうやって見つけるのか？ 「1つのデータに1つのロケーション」が理想だが… ロケーションが無限に必要！ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「Out-of-Order実行機構」より

高性能コンピューティング論２ レジスタリネーミングの実際

論理レジスタと物理レジスタ op Rs Rt Rd shamt func 論理レジスタ (logical register) 高性能コンピューティング論２ 論理レジスタと物理レジスタ 論理レジスタ (logical register) 命令のフィールドで指定する r0 ～ r31 「データ･フロー（命令間のデータ授受関係）を表現するための名前」 コンパイラが管理 物理レジスタ (physical register) 「データの物理的な格納場所」 ＝ レジスタ・ファイル ハードウェアが管理 レジスタリネーミングを行わないプロセッサは，論理レジスタ ＝ 物理レジスタ op Rs Rt Rd shamt func 31 25 20 15 10 レジスタ・ファイル 命令キュー リネーム ロジック 命令 キャッシュ 演算器

物理レジスタの管理 レジスタマップ表 フリーリスト 割り当て (allocation)： 解決 (resolution)： 高性能コンピューティング論２ 物理レジスタの管理 論理 Reg マップ 表 r1 P31 レジスタマップ表 論理 Reg と物理 Reg の対応を記録 フリーリスト 空き物理 Reg 番号のプール 割り当て (allocation)： 空き物理 Reg 番号をプールから取得 デスティネーションに割り当てる 論理→物理マッピングを確立 解決 (resolution)： マップ表を参照し，ソースの論理 Reg にマップされている物理 Reg を発見 解放 (free)： 不要になった物理 Reg をプールに返す r2 P31 P5 P62 P18 head フリー リスト

物理レジスタの管理 レジスタマップ表 フリーリスト 割り当て (allocation)： 解決 (resolution)： 高性能コンピューティング論２ 物理レジスタの管理 論理 Reg マップ 表 r1 P31 レジスタマップ表 論理 Reg と物理 Reg の対応を記録 フリーリスト 空き物理 Reg 番号のプール 割り当て (allocation)： 空き物理 Reg 番号をプールから取得 デスティネーションに割り当てる 論理→物理マッピングを確立 解決 (resolution)： マップ表を参照し，ソースの論理 Reg にマップされている物理 Reg を発見 解放 (free)： 不要になった物理 Reg をプールに返す r2 P5 P5 P62 P18 head フリー リスト

物理レジスタの管理 レジスタマップ表 フリーリスト 割り当て (allocation)： 解決 (resolution)： 高性能コンピューティング論２ 物理レジスタの管理 論理 Reg マップ 表 r1 P31 レジスタマップ表 論理 Reg と物理 Reg の対応を記録 フリーリスト 空き物理 Reg 番号のプール 割り当て (allocation)： 空き物理 Reg 番号をプールから取得 デスティネーションに割り当てる 論理→物理マッピングを確立 解決 (resolution)： マップ表を参照し，ソースの論理 Reg にマップされている物理 Reg を発見 解放 (free)： 不要になった物理 Reg をプールに返す r2 P5 P62 P18 head フリー リスト P5

スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令キュー 演算器 フロントエンド Front-end バックエンド 高性能コンピューティング論２ スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 キャッシュ 命令キュー リネーム ロジック 演算器 フェッチ Fetch リネーム Rename ディスパッチ Dispatch スケジュール Schedule 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB フロントエンド Front-end バックエンド Back-end ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より

スーパスカラ･プロセッサの基本構造 物理レジスタ・ファイル 命令キュー 演算器 フロントエンド Front-end バックエンド 高性能コンピューティング論２ スーパスカラ･プロセッサの基本構造 物理レジスタ・ファイル 命令 キャッシュ 命令キュー マップ表 演算器 フリーリスト フェッチ Fetch リネーム Rename ディスパッチ Dispatch スケジュール Schedule 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB フロントエンド Front-end バックエンド Back-end

レジスタ･リネーミング― 割り当て と 解決 マップ表 物理レジスタ ファイル r1 p11 p13 ld r1 = *($sp) r2 高性能コンピューティング論２ レジスタ･リネーミング― 割り当て と 解決 命令は，リネーム･ロジックを In-Order に通過する プログラム・オーダが分かる データ依存が分かる マップ表 物理レジスタ ファイル r1 p11 p13 ld r1 = *($sp) r2 p12 p0 1000 p11 r3 sla r2 = r1 << 1 r4 p14 p12 p11 p10 320 p11 (empty) sla r1 = r1 << 2 p13 p11 r31 p12 (empty) p13 (empty) add r4 = r1 + r2 フリーリスト p14 p13 p12 p14 (empty) p11 p12 p13 p63 (empty) p14 p63

レジスタ・リネーミング ― 解放 理想的な解放タイミング 普通は保守的に解放 最後のレジスタ参照が完了した時 検出が困難 高性能コンピューティング論２ レジスタ・リネーミング ― 解放 理想的な解放タイミング 最後のレジスタ参照が完了した時 検出が困難 普通は保守的に解放 同一の論理レジスタを上書きする命令がプロセッサから追い出された時 この先，当該物理レジスタを参照する命令は絶対に出現しない cycle ld r1 = *($sp) OR EX MEM WB p11 sla r2 = r1 << 1 OR EX MEM WB p12 p11 sla r1 = r1 << 2 OR EX MEM WB p13 p11 保守的な 解放タイミング 理想的な解放タイミング

レジスタ･リネーミング― 解放 マップ表 物理レジスタ ファイル r1 p11 p13 ld r1 = *($sp) r2 p12 p0 高性能コンピューティング論２ レジスタ･リネーミング― 解放 物理レジスタ番号をフリーリストに返却 物理レジスタを空の状態に変更 マップ表 物理レジスタ ファイル r1 p11 p13 ld r1 = *($sp) r2 p12 p0 1000 p11 r3 sla r2 = r1 << 1 r4 p14 p12 p11 p10 320 p11 4 (empty) sla r1 = r1 << 2 p13 p11 r31 p12 8 p13 16 add r4 = r1 + r2 フリーリスト p14 p13 p12 p14 24 p63 p63 (empty) p11

静的命令 と 動的命令 静的命令 動的命令 例えば短いループ メモリ上にある命令 PCと 1対1 に対応 フェッチされて処理中の命令 高性能コンピューティング論２ 静的命令 と 動的命令 静的命令 メモリ上にある命令 PCと 1対1 に対応 動的命令 フェッチされて処理中の命令 In-Flight な命令 例えば短いループ 同じ PC の命令が複数存在 0x00500000: 0x00500004: 0x00500008: 0x0050000C: 0x00500010: 0x00500014: 0x00500018: set r1 = 0; # s = 0; set r2 = 1; # i = 1; set r3 = 11; LOOP: beq r2 == r3, EXIT; add r1 = r1 + r2; add r2 = r2 + 1; b LOOP; EXIT:

タグ 物理レジスタ：命令ごとに1つずつ割り当てられる 物理レジスタ番号 = タグ 同一視してよい： 高性能コンピューティング論２ タグ 物理レジスタ：命令ごとに1つずつ割り当てられる 同一視してよい： 動的命令 と それに割り当てられた物理レジスタ そこに書かれる結果 物理レジスタ番号 = タグ プロセッサ上の，動的命令 = データ（結果）を一意に識別する識別子 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「Out-of-Order実行機構」より

投機ミス時のレジスタの回復処理 投機ミスした場合， 投機的に実行された命令 ex) 予測した分岐命令の，プログラム・オーダ上で下流の命令 高性能コンピューティング論２ 投機ミス時のレジスタの回復処理 投機的に実行された命令 ex) 予測した分岐命令の，プログラム・オーダ上で下流の命令 投機ミスした場合， 投機的に実行された命令の実行を取り消す 　デスティネーション・レジスタ（論理）の内容を元に戻す 　レジスタ・マッピングと物理レジスタの内容を元に戻す

レジスタの回復処理 マップ表 物理レジスタ ファイル r1 p11 p13 be r3 = r31 , LABEL r2 p12 p0 r3 高性能コンピューティング論２ レジスタの回復処理 レジスタ・マッピングを投機を行う前の状態に戻す 投機的に割り当てた物理レジスタを空の状態に戻す マップ表 物理レジスタ ファイル r1 p11 p13 be r3 = r31 , LABEL r2 p12 p0 1000 r3 p10 ld r1 = *($sp) r4 p14 p11 p10 320 sla r2 = r1 << 1 p11 (empty) 4 p12 p11 r31 p0 p12 8 (empty) sla r1 = r1 << 2 p13 (empty) 16 フリーリスト p13 p11 p14 24 (empty) add r4 = r1 + r2 p12 p11 p13 p14 p63 p14 p13 p12 p63 (empty)

高性能コンピューティング論２ 命令スケジューリングの実際

命令スケジューリング ２つのステップ ウェイクアップ セレクト 命令キューの中から実行可能な命令を発見 高性能コンピューティング論２ 命令スケジューリング ２つのステップ ウェイクアップ 命令キューの中から実行可能な命令を発見 実行可能な命令 ＝ フロー依存による先行制約を満たす命令 セレクト ウェイクアップされた命令の中から次に実行する命令を選択 資源制約を考慮 セレクト回路 ウェイク アップ 回路 命令キュー

ウェイクアップ dtag (destination tag) stag (source tag) rdy (ready bit) 高性能コンピューティング論２ ウェイクアップ = = = = dtag stag rdy stag rdy dtag (destination tag) デスティネーション・オペランド のタグ stag (source tag) ソース・オペランドのタグ rdy (ready bit) タグが利用可能か否か？ = = = = = = = = セレクト回路 = = = =

ウェイクアップ ld *($sp) = p11 p11 1 1 sla p11 << 1 = p12 p12 p11 1 sla 高性能コンピューティング論２ ウェイクアップ = = = = ld *($sp) = p11 p11 1 1 = = = = sla p11 << 1 = p12 p12 p11 1 = = = = セレクト回路 sla p11 << 2 = p13 p13 p11 1 = = = = add p12 = p14 + p13 p14 p13 p12

ウェイクアップ ld *($sp) = p11 p11 1 1 sla p11 << 1 = p12 p12 p11 1 1 高性能コンピューティング論２ ウェイクアップ = = = = ld *($sp) = p11 p11 1 1 = = = = sla p11 << 1 = p12 p12 p11 1 1 = = = = セレクト回路 sla p11 << 2 = p13 p13 p11 1 1 = = = = add p12 = p14 + p13 p14 p13 p12

ウェイクアップ ld *($sp) = p11 p11 1 1 sla p11 << 1 = p12 p12 p11 1 1 高性能コンピューティング論２ ウェイクアップ = = = = ld *($sp) = p11 p11 1 1 = = = = sla p11 << 1 = p12 p12 p11 1 1 = = = = セレクト回路 sla p11 << 2 = p13 p13 p11 1 1 = = = = add p12 = p14 + p13 p14 p13 1 p12 1

セレクト レディな命令の中から発行する命令を選択 選択の戦略 資源制約を満たす命令（must） 一般には，古い命令 高性能コンピューティング論２ セレクト レディな命令の中から発行する命令を選択 選択の戦略 資源制約を満たす命令（must） 例） 整数乗算器を使用中ならば，整数乗算命令は発行不可 一般には，古い命令 ＝ プログラム・オーダ上で上流の命令 命令が古いほど，その命令に依存する命令が命令ウインドウ内に存在する可能性が高い 依存元の命令が発行されないと，依存先の命令はいつまでも発行できない

高性能コンピューティング論２ 正確な例外

割り込み 割り込み 外部から，プログラムとは非同期に 内部から，プログラムの実行によって 高性能コンピューティング論２ 割り込み 割り込み 外部から，プログラムとは非同期に （いわゆる，狭義の）割り込み (interruption) 内部から，プログラムの実行によって 例外 (exception) TLBミス division by zero parity error SEGV etc. トラップ (trap) トラップ命令の実行 システム・コール

正確な割り込み (precise interruption) 高性能コンピューティング論２ 正確な割り込み (precise interruption) 正確な割り込み (precise interruption) 割り込み（exception，trap）に対して，In-Order State を回復 In-Order State： 割り込みを発生させた命令より前の命令の結果はすべて反映されている 割り込みを発生させた命令以降の命令の結果はまったく反映されていない 例） ロード命令が TLB ミスした場合，ロード命令の直前の命令まで In-Order 実行ならば簡単 割り込みが発生した命令以降の命令 ＝ 命令パイプライン上で割り込みを 　　 発生させた命令よりも上流の命令 上記の命令をすべてキャンセル Out-of-Order 実行では？ I0 I1 I2 I3 I4 I5 I6 I7 I8 I9

正確な割り込み と 投機ミス 投機ミス時も In-Order State （とほぼ同じ状態）を回復 高性能コンピューティング論２ 正確な割り込み と 投機ミス 投機ミス時も In-Order State （とほぼ同じ状態）を回復 例） 分岐予測ミスした命令以前の命令の結果をすべて反映 　 分岐予測ミスした命令よりも後の命令の結果をすべて破棄 投機ミスへの対応の応用で正確な割り込みも実現可能 割り込みの頻度は低い 投機ミスの方が高速に処理する必要がある

リオーダ・バッファ 論理レジスタ・ファイル リオーダ・バッファ コミット In-Order State （マシン・ステート）を保持 高性能コンピューティング論２ リオーダ・バッファ 論理レジスタ・ファイル In-Order State （マシン・ステート）を保持 リオーダ・バッファ Out-of-Order State を保持 コミット リオーダ・バッファ内の情報を用いて，論理レジスタ・ファイルを更新 In-Order に更新 不可逆的更新（巻き戻し不可）

リオーダ・バッファ（通常時） 論理 Reg ファイル r1 r2 r3 高性能コンピューティング論２ 論理 Reg ファイル リオーダ・バッファ（通常時） r1 r2 r3 ディスパッチ時にリオーダ・バッファのエントリを In-Order に割り当て Out-of-Order 実行された結果を In-Order に 論理 Reg に反映 論理 Reg に反映されるとエントリを解放 r4 r31 コミット ld r1 = *($sp) 論理Reg Reg値 p11 p11 r1 sla r2 = r1 << 1 p12 r2 p12 p11 p13 r1 sla r1 = r1 << 2 (be) p13 p11 p14 r4 be r1 = r2 , LABEL add r4 = r1 + r2 p14 p13 p12 リオーダ・バッファ

リオーダ・バッファ（投機ミス時） 論理 Reg ファイル r1 r2 r3 投機ミスした命令よりも下流のエントリをすべて解放 r4 r31 高性能コンピューティング論２ 論理 Reg ファイル リオーダ・バッファ（投機ミス時） r1 r2 r3 投機ミスした命令よりも下流のエントリをすべて解放 r4 r31 コミット ld r1 = *($sp) 論理Reg Reg値 p11 sla r2 = r1 << 1 p12 p11 sla r1 = r1 << 2 (be) p13 p11 p14 r4 解放 be r1 = r2 , LABEL add r4 = r1 + r2 p14 p13 p12 リオーダ・バッファ

リオーダ・バッファ（割り込み時） 論理 Reg ファイル r1 r2 r3 割り込みを発生させた命令以降のエントリを解放 r4 r31 高性能コンピューティング論２ 論理 Reg ファイル リオーダ・バッファ（割り込み時） r1 r2 r3 割り込みを発生させた命令以降のエントリを解放 r4 r31 コミット ld r1 = *($sp) 論理Reg Reg値 p11 div r2 = r1 / r31 p12 r2 解放 p12 p11 p13 r1 sla r1 = r1 << 2 (be) p13 p11 p14 r4 be r1 = r2 , LABEL add r4 = r1 + r2 p14 p13 p12 リオーダ・バッファ

高性能コンピューティング論２ 本日のまとめ

まとめ Out-of-Order スーパスカラプロセッサの基本構造の復習 レジスタリネーミングの実際 命令スケジューリングの実際 正確な例外 高性能コンピューティング論２ まとめ Out-of-Order スーパスカラプロセッサの基本構造の復習 レジスタリネーミングの実際 命令スケジューリングの実際 正確な例外

高性能コンピューティング論２ 次回 11/26（木） 10:40～ 19日は調布祭のため休講 「分岐予測，プリフェッチ」について解説