高性能コンピューティング論２ 1 高性能コンピューティング論２ 第5回 Out-of-Order実行機構 高性能コンピューティング学講座 三輪 忍 [email protected] 高性能コンピューティング論２ 2 本日の講義内容 • Out-of-Order スーパスカラプロセッサの基本構造の復習 • レジスタリネーミングの実際 • 命令スケジューリングの実際 • 正確な例外 高性能コンピューティング論２ 3 Out-of-Orderスーパスカラ プロセッサの基本構造の復習 高性能コンピューティング論２ 4 スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 キャッシュ リネーム ロジック 命令キュー フェッチ Fetch リネーム Rename ディスパッチ スケジュール Dispatch Schedule フロントエンド Front-end 演算器 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB バックエンド Back-end ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 5 命令スケジューリング • 命令スケジューリング • 命令キューの中から実行可能な命令を発見 • 実行可能 ＝ 制約（次スライド）を満たす • 実行可能な命令の中から次に実行すべき命令を選択 add r4 = r1 + r2 • バックエンド： add r5 = r4 + r3 • スケジュールされた命令を実際に実行 • 命令ウィンドウ （スケジューリング･ウィンドウ）： • スケジュール対象の命令の集合 • 命令キュー内の全命令 • フロントエンド： • 命令ウィンドウを下流に拡大 命令ウィンドウ add r8 = r6 + r7 add r8 = r8 + 1 sub r5 = r5 – r8 bz r5 高性能コンピューティング論２ 6 命令スケジューリングの制約 • 計算資源 ：「実行するハードウエア側の問題」 • 「演算器など，計算資源が空いていなければ実行できない」 • 命令間の依存：「実行されるプログラム側の問題」 • 先行制約：命令間の先行関係の制約 • 制御依存 (control dependence) • 「分岐命令があると，後の命令は先に実行できない」 • データ依存 (data dependence) • 「2つの命令が同一のロケーションを定義/参照していると， 後の命令は先に実行できない」 • パイプライン･ハザードと同じ だが • 「どの命令にインターロックかけるか？」より，簡潔 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 7 データ依存 後続命令 Read Read Ip Ip Is Is time 先 行 命 令 Write time 入力依存 (input) 逆依存 (anti) Write Ip Ip Is Is time time フロー依存 (flow) 出力依存 (output) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 8 真のデータ依存，偽のデータ依存 • フロー依存：真の (true) データ依存 • データの授受のため • 先行制約を生じる • 入力依存 • 一般に，複数の読み出しがあるため • 先行制約を生じない • 逆依存，出力依存：偽の (false) データ依存 • ロケーションの再利用のため • 原理的には，先行制約を生じない • リネーミングにより解消 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 9 データ依存の具体例 ld r1 = *($sp) フロー依存 sla r2 = r1 << 1 逆依存 sla r1 = r1 << 2 add r4 = r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 10 データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r1 = r1 << 2 add r4 = r1 + r2 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 11 データ依存の具体例 ld r1 = sla r2 = *($sp) r1 << 1 逆依存 sla r1 r3 = r1 << 2 add r4 = r1 + r2 r3 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 12 リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r2 = r1 << 1 sla r1 r3 = r1 << 2 定義 add r4 = r3 r1 + r2 参照 time • 要は，「1つのデータに1つのロケーション」 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 13 リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r2 = r1 << 1 sla r3 = r1 << 2 定義 add r4 = r3 + r2 参照 time • 要は，「1つのデータに1つのロケーション」 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 14 リネーミングの問題 • r1 を r3 にリネーム • コンパイラならできるが， • HW が r3 をどうやって見つけるのか？ • 「1つのデータに1つのロケーション」が理想だが… • ロケーションが無限に必要！ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「Out-of-Order実行機構」より 高性能コンピューティング論２ 15 レジスタリネーミングの実際 高性能コンピューティング論２ 16 論理レジスタと物理レジスタ • 論理レジスタ (logical register) • 命令のフィールドで指定する r0 ～ r31 • 「データ･フロー（命令間のデータ授受関係）を表現するための名前」 • コンパイラが管理 op 31 Rs 25 Rt 20 Rd 15 shamt func 10 0 • 物理レジスタ (physical register) • 「データの物理的な格納場所」 ＝ レジスタ・ファイル • ハードウェアが管理 • レジスタリネーミングを行わないプロセッサは，論理レジスタ ＝ 物理レジスタ レジスタ・ファイル 命令 キャッシュ リネーム ロジック 命令キュー 演算器 高性能コンピューティング論２ 物理レジスタの管理 レジスタマップ表 • • 論理 Reg と物理 Reg の対応を記録 17 論理 Reg マップ 表 r1 r2 P31 フリーリスト • • 空き物理 Reg 番号のプール 1. 割り当て (allocation)： • 空き物理 Reg 番号をプールから取得 • デスティネーションに割り当てる • 論理→物理マッピングを確立 head P31 フリー リスト P5 P62 P18 2. 解決 (resolution)： • マップ表を参照し，ソースの論理 Reg にマップされている物理 Reg を発見 3. 解放 (free)： • 不要になった物理 Reg をプールに返す 高性能コンピューティング論２ 物理レジスタの管理 レジスタマップ表 • • 論理 Reg と物理 Reg の対応を記録 18 論理 Reg マップ 表 r1 r2 P31 P5 フリーリスト • • 空き物理 Reg 番号のプール 1. 割り当て (allocation)： • 空き物理 Reg 番号をプールから取得 • デスティネーションに割り当てる • 論理→物理マッピングを確立 head フリー リスト P5 P62 P18 2. 解決 (resolution)： • マップ表を参照し，ソースの論理 Reg にマップされている物理 Reg を発見 3. 解放 (free)： • 不要になった物理 Reg をプールに返す 高性能コンピューティング論２ 物理レジスタの管理 レジスタマップ表 • • 論理 Reg と物理 Reg の対応を記録 19 論理 Reg マップ 表 r1 r2 P31 P5 フリーリスト • • 空き物理 Reg 番号のプール 1. 割り当て (allocation)： • 空き物理 Reg 番号をプールから取得 • デスティネーションに割り当てる • 論理→物理マッピングを確立 head P62 フリー リスト P5 P18 2. 解決 (resolution)： • マップ表を参照し，ソースの論理 Reg にマップされている物理 Reg を発見 3. 解放 (free)： • 不要になった物理 Reg をプールに返す 高性能コンピューティング論２ 20 スーパスカラ･プロセッサの基本構造 レジスタ・ファイル 命令 キャッシュ リネーム ロジック 命令キュー フェッチ Fetch リネーム Rename ディスパッチ スケジュール Dispatch Schedule フロントエンド Front-end 演算器 発行 Issue レジスタ読出 Reg Read 実行 Exec 書戻 WB バックエンド Back-end ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「スーパスカラ・プロセッサの基礎」より 高性能コンピューティング論２ 21 スーパスカラ･プロセッサの基本構造 物理レジスタ・ファイル 命令 キャッシュ フェッチ Fetch マップ 表 命令キュー 演算器 フリー リスト リネーム Rename フロントエンド Front-end ディスパッチ スケジュール Dispatch Schedule 発行 Issue レジスタ読出 Reg Read 実行 Exec バックエンド Back-end 書戻 WB 高性能コンピューティング論２ 22 レジスタ･リネーミング― 割り当て と 解決 • 命令は，リネーム･ロジックを In-Order に通過する • プログラム・オーダが分かる マップ表 • データ依存が分かる ld r1 p11 = *($sp) sla r2 p12 = r1 << 1 p11 r1 p13 = r4 p14 = sla add r1 << 2 p11 r1 + r2 p13 p12 r1 p11 p13 r2 p12 r3 r4 p14 r31 フリーリスト p11 p12 p13 p14 物理レジスタ ファイル p0 1000 p10 p11 p12 p13 p14 p63 320 (empty) (empty) (empty) (empty) (empty) 高性能コンピューティング論２ 23 レジスタ・リネーミング ― 解放 • 理想的な解放タイミング • 最後のレジスタ参照が完了した時 • 検出が困難 • 普通は保守的に解放 • 同一の論理レジスタを上書きする命令がプロセッサから追い出された時 • この先，当該物理レジスタを参照する命令は絶対に出現しない cycle ld r1 p11 = *($sp) sla r2 p12 = r1 << 1 p11 OR EX MEM WB sla r1 p13 = r1 << 2 p11 OR EX MEM WB OR EX MEM WB 理想的な解放タイミング 保守的な 解放タイミング 高性能コンピューティング論２ 24 レジスタ･リネーミング― 解放 • 物理レジスタ番号をフリーリストに返却 • 物理レジスタを空の状態に変更 ld r1 p11 = *($sp) sla r2 p12 = r1 << 1 p11 r1 p13 = r4 p14 = sla add r1 << 2 p11 r1 + r2 p13 p12 マップ表 r1 p11 p13 r2 p12 r3 r4 p14 r31 フリーリスト p63 p11 物理レジスタ ファイル p0 1000 p10 p11 p12 p13 p14 p63 320 4 (empty) 8 16 24 (empty) 高性能コンピューティング論２ 25 静的命令 と 動的命令 • 静的命令 • メモリ上にある命令 • PCと 1対1 に対応 • 動的命令 • フェッチされて処理中の命令 • In-Flight な命令 • 例えば短いループ • 同じ PC の命令が複数存在 0x00500000: 0x00500004: 0x00500008: set r1 = 0; # set r2 = 1; # set r3 = 11; LOOP: 0x0050000C: beq r2 == r3, 0x00500010: add r1 = r1 + 0x00500014: add r2 = r2 + 0x00500018: b LOOP; EXIT: s = 0; i = 1; EXIT; r2; 1; 高性能コンピューティング論２ 26 タグ • 物理レジスタ：命令ごとに1つずつ割り当てられる • 同一視してよい： • 動的命令 と • それに割り当てられた物理レジスタ • そこに書かれる結果 • 物理レジスタ番号 = タグ • プロセッサ上の，動的命令 = データ（結果）を一意に識別する識別子 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「Out-of-Order実行機構」より 高性能コンピューティング論２ 投機ミス時のレジスタの回復処理 投機的に実行された命令 ex) 予測した分岐命令の，プログラム・オーダ上で下流の命令 • 投機ミスした場合， • 投機的に実行された命令の実行を取り消す • デスティネーション・レジスタ（論理）の内容を元に戻す • レジスタ・マッピングと物理レジスタの内容を元に戻す 27 高性能コンピューティング論２ 28 レジスタの回復処理 • レジスタ・マッピングを投機を行う前の状態に戻す • 投機的に割り当てた物理レジスタを空の状態に戻す マップ表 be r3 = r31, LABEL ld r1 p11 = *($sp) r2 p12 = r1 p13 = r4 p14 = sla sla add r1 << 1 p11 r1 << 2 p11 r1 + r2 p13 p12 r1 r2 r3 r4 r31 p11 p13 p12 p10 p14 p0 フリーリスト p11 p12 p63 p13 p14 物理レジスタ ファイル p0 1000 p10 p11 p12 p13 p14 p63 320 4 (empty) (empty) 8 16 (empty) 24 (empty) (empty) 高性能コンピューティング論２ 29 命令スケジューリングの実際 高性能コンピューティング論２ 命令スケジューリング • ２つのステップ • ウェイクアップ • 命令キューの中から実行可能な命令を発見 • 実行可能な命令 ＝ フロー依存による先行制約を満たす命令 • セレクト • ウェイクアップされた命令の中から次に実行する命令を選択 • 資源制約を考慮 セレクト回路 ウェイク アップ 回路 命令キュー 30 高性能コンピューティング論２ • dtag (destination tag) • デスティネーション・オペランド のタグ • stag (source tag) • ソース・オペランドのタグ = dtag stag = = = = rdy = = = rdy stag = = = = • rdy (ready bit) • タグが利用可能か否か？ = = = = セレクト回路 ウェイクアップ 31 高性能コンピューティング論２ ld p11 = *($sp) = p11 p12 = p11 << 1 p12 p13 = p11 << 2 p13 p14 = p13 + p12 p14 1 = = 1 0 = = p13 = 0 = p11 = add 1 = = p11 = sla = 1 = sla = = 0 p12 = 0 セレクト回路 ウェイクアップ 32 高性能コンピューティング論２ ld p11 = *($sp) = p11 p12 = p11 << 1 p12 p13 = p11 << 2 p13 p14 = p13 + p12 p14 1 = = 1 1 0 = = p13 = 1 0 = p11 = add 1 = = p11 = sla = 1 = sla = = 0 p12 = 0 セレクト回路 ウェイクアップ 33 高性能コンピューティング論２ ld p11 = *($sp) = p11 p12 = p11 << 1 p12 p13 = p11 << 2 p13 p14 = p13 + p12 p14 1 = = 1 1 = = p13 = 1 = p11 = add 1 = = p11 = sla = 1 = sla = = 1 0 p12 = 0 1 セレクト回路 ウェイクアップ 34 高性能コンピューティング論２ 35 セレクト • レディな命令の中から発行する命令を選択 • 選択の戦略 • 資源制約を満たす命令（must） • 例） 整数乗算器を使用中ならば，整数乗算命令は発行不可 • 一般には，古い命令 • ＝ プログラム・オーダ上で上流の命令 • 命令が古いほど，その命令に依存する命令が命令ウインドウ内に存在する 可能性が高い • 依存元の命令が発行されないと，依存先の命令はいつまでも発行できない 高性能コンピューティング論２ 正確な例外 36 高性能コンピューティング論２ 割り込み • 割り込み • 外部から，プログラムとは非同期に • （いわゆる，狭義の）割り込み (interruption) • 内部から，プログラムの実行によって • 例外 (exception) • TLBミス • division by zero • parity error • SEGV • etc. • トラップ (trap) • トラップ命令の実行 • システム・コール 37 高性能コンピューティング論２ 38 正確な割り込み (precise interruption) • 正確な割り込み (precise interruption) • 割り込み（exception，trap）に対して，In-Order State を回復 • In-Order State： • 割り込みを発生させた命令より前の命令の結果はすべて反映されている • 割り込みを発生させた命令以降の命令の結果はまったく反映されていない • 例） ロード命令が TLB ミスした場合，ロード命令の直前の命令まで • In-Order 実行ならば簡単 • 割り込みが発生した命令以降の命令 ＝ 命令パイプライン上で割り込みを 発生させた命令よりも上流の命令 • 上記の命令をすべてキャンセル • Out-of-Order 実行では？ 高性能コンピューティング論２ 39 正確な割り込み と 投機ミス • 投機ミス時も In-Order State （とほぼ同じ状態）を回復 • 例） 分岐予測ミスした命令以前の命令の結果をすべて反映 分岐予測ミスした命令よりも後の命令の結果をすべて破棄 • 投機ミスへの対応の応用で正確な割り込みも実現可能 • 割り込みの頻度は低い • 投機ミスの方が高速に処理する必要がある 高性能コンピューティング論２ 40 リオーダ・バッファ • 論理レジスタ・ファイル • In-Order State （マシン・ステート）を保持 • リオーダ・バッファ • Out-of-Order State を保持 • コミット • リオーダ・バッファ内の情報を用いて，論理レジスタ・ファイルを更新 • In-Order に更新 • 不可逆的更新（巻き戻し不可） 高性能コンピューティング論２ 論理 Reg ファイル r1 r2 r3 r4 リオーダ・バッファ（通常時） • ディスパッチ時にリオーダ・バッファのエントリを In-Order に割り当て • Out-of-Order 実行された結果を In-Order に 論理 Reg に反映 • 論理 Reg に反映されるとエントリを解放 ld r1 p11 = *($sp) sla r2 p12 = r1 << 1 p11 sla r1 p13 = r1 << 2 p11 be r1 = r2, LABEL add r4 p14 = r1 + r2 p13 p12 41 r31 論理Reg p11 p12 p13 (be) p14 Reg値 r1 r2 r1 r4 リオーダ・バッファ コミット 高性能コンピューティング論２ リオーダ・バッファ（投機ミス時） • 投機ミスした命令よりも下流のエントリをすべて解放 42 論理 Reg ファイル r1 r2 r3 r4 r31 ld r1 p11 = *($sp) sla r2 p12 = r1 << 1 p11 sla r1 p13 = r1 << 2 p11 be r1 = r2, LABEL add r4 p14 = r1 + r2 p13 p12 論理Reg Reg値 コミット (be) p14 r4 解放 リオーダ・バッファ 高性能コンピューティング論２ リオーダ・バッファ（割り込み時） • 割り込みを発生させた命令以降のエントリを解放 ld r1 p11 = *($sp) div r2 p12 = sla r1 p13 = r1 << 2 p11 be r1 = r2, LABEL add r4 p14 = r1 + r2 p13 p12 r1 / p11 r31 43 論理 Reg ファイル r1 r2 r3 r4 r31 0 論理Reg Reg値 p12 r2 p13 r1 (be) p14 r4 リオーダ・バッファ コミット 解放 高性能コンピューティング論２ 本日のまとめ 44 高性能コンピューティング論２ 45 まとめ • Out-of-Order スーパスカラプロセッサの基本構造の復習 • レジスタリネーミングの実際 • 命令スケジューリングの実際 • 正確な例外 高性能コンピューティング論２ 次回 • 11/26（木） 10:40～ • 19日は調布祭のため休講 • 「分岐予測，プリフェッチ」について解説 46
© Copyright 2024 ExpyDoc
