Advanced Computer Architecture 04. レジスタ・リネーミング 五島 正裕 2015/9/30 Advanced Computer Architecture 内容 1. レジスタ・リネーミングの復習 2. レジスタ・リネーミングの実際 3. 分岐予測の復習 4. レジスタ・リネーミングと分岐予測 2 Advanced Computer Architecture 1. レジスタ・リネーミングの復習 2015/9/30 Advanced Computer Architecture 4 スーパースカラ･プロセッサの基本構造 フェッチ幅 命令 キャッシュ フェッチ Fetch ディスパッチ幅 リネーム 命令 ウィンドウ ロジック リネーム Rename フロントエンド front-end 発行幅 ディスパッチ Dispatch スケジュール Schedule RFRF 演算器 発行 Issue 実行 Exec バックエンド back-end 書戻 WB Advanced Computer Architecture 命令スケジューリングの制約 計算資源 ：「実行するハードウエア側の問題」 「演算器など，計算資源が空いていなければ実行できない」 命令間の依存：「実行されるプログラム側の問題」 先行制約：命令間の先行関係の制約 制御依存 (control dependence) 「分岐命令があると，後の命令は先に実行できない」 データ依存 (data dependence) 「2つの命令が同一のロケーションを定義/参照していると， 後の命令は先に実行できない」 パイプライン･ハザードと同じ だが 「どの命令にインターロックかけるか？」より，簡潔 5 Advanced Computer Architecture 6 データ依存 後続命令 Read Read 先 行 命 令 Write Ip Ip Is Is time time 入力依存 (input) Write time 逆依存 (anti) Ip Ip Is Is フロー依存 (flow) time 出力依存 (output) Advanced Computer Architecture 真のデータ依存，偽のデータ依存 フロー依存：真の (true) データ依存 データの授受のため 先行制約を生じる 入力依存 一般に，複数の読み出しがあるため 先行制約を生じない 逆依存，出力依存：偽の (false) データ依存 ロケーションの再利用のため 原理的には，先行制約を生じない リネーミングにより解消可能 7 Advanced Computer Architecture 8 データ依存の具体例 ld r1 = *($sp) フロー依存 sla r2 = r1 << 1 逆依存 sla r1 = r1 << 2 add r4 = r1 + r2 Advanced Computer Architecture 9 データ依存の具体例 ld r1 = *($sp) sla r2 = r1 << 1 sla r1 = r1 << 2 add r4 = r1 + r2 Advanced Computer Architecture 10 データ依存の具体例 ld r1 = sla r2 = *($sp) r1 << 1 逆依存 sla r1 r3 = r1 << 2 add r4 = r1 + r2 r3 Advanced Computer Architecture 11 リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r2 = r1 << 1 sla r3 r1 = r1 << 2 定義 add r4 = r1 + r2 r3 参照 cycle 要は，「1つのデータに1つのロケーション」 Advanced Computer Architecture 12 リネーミングの真髄 データの寿命 r1 r2 r3 r4 ロケーション （レジスタ番号） ld r1 = *($sp) sla r2 = r1 << 1 sla r3 = r1 << 2 定義 add r4 = r3 + r2 参照 cycle 要は，「1つのデータに1つのロケーション」 Advanced Computer Architecture レジスタ･リネーミングとフロー依存 各命令のデスティネーションに割り当てるとき， レジスタは「空 (empty)」にしておく 命令が実行され，結果が書かれたら， レジスタは「一杯 (full)」 になる フロー依存による先行制約を満たす ＝ 依存元の命令が実行されたら，依存先の命令を実行する ソースが full になったら，実行する 13 Advanced Computer Architecture 14 レジスタ･リネーミングとフロー依存 ld r1 = *($sp) sla r2 = r1 << 1 sla r3 = r1 << 2 add r4 = r3 + r2 r1 r2 r3 r4 r31 Advanced Computer Architecture リネーミングの問題 r1 を r3 にリネーム コンパイラならできるが， HW が r3 をどうやって見つけるのか？ 「1つのデータに1つのロケーション」が理想だが… ロケーションが無限に必要！ 15 Advanced Computer Architecture 1. レジスタ･リネーミングの実際 2015/9/30 Advanced Computer Architecture 17 論理レジスタ，物理レジスタ 論理レジスタ (logical register) 命令のフィールドで指定する r0 ～ r31 「データ･フローを表現するための名前」 必ずしも，物理的に存在している必要はない 高級言語で言えば「変数」 物理レジスタ (physical register) 「データの物理的な格納場所」 高級言語で言えば「物理メモリ（のロケーション）」 op 31 Rs 25 Rt 20 Rd 15 shamt func 10 0 Advanced Computer Architecture 18 データ依存の具体例 ld r1 = *($sp) フロー依存 sla r2 = r1 << 1 逆依存 sla r1 = r1 << 2 add r4 = r1 + r2 Advanced Computer Architecture 物理レジスタの管理 空き物理 Reg のプール 1. 割り当て (allocation)： 空き物理 Reg をプールから取得 デスティネーションに割り当てる 論理→物理マッピングを確立 2. 解決 (resolution)： ソースの論理 Reg にマップされている物理 Reg を見つける 3. 解放 (free)： 不要になった物理 Reg をプールに返す 19 Advanced Computer Architecture 20 レジスタ･リネーミング ― 割り当て と 解決 RFRF 命令 キャッシュ フェッチ Fetch リネーム 命令 ウィンドウ ロジック リネーム Rename ディスパッチ Dispatch スケジュール Schedule 演算器 発行 Issue 実行 Exec 書戻 WB Advanced Computer Architecture 21 レジスタ･リネーミング― 割り当て と 解決 命令は，リネーム･ロジックを In-Order に通過する プログラム・オーダが分かる ld 物理 Reg プール データ依存が分かる r1 p11 = *($sp) sla r2 p12 = r1 << 1 p11 sla r3 p13 = r1 << 2 p11 add r4 p14 = r3 + r2 p13 p12 Reg マップ テーブル p0 p11 p12 p13 p14 p10 p11 p12 p13 p14 r1 r2 r3 r4 r31 p63 Advanced Computer Architecture 22 マシン・ステート 論理→物理の変換： プロセッサの HW が透過的に行う プログラム（命令）から観測できるのは，論理 Reg のみ 物理 Reg を（指定して）アクセスすることは（通常の方法では） できない 「計算機の状態 (machine state)」は，論理 Reg の集合 （＋α） Advanced Computer Architecture レジスタ・リネーミング ― 解放 後で… 23 Advanced Computer Architecture 1. 前回までの復習 分岐予測 2015/9/30 Advanced Computer Architecture 25 投機のフェーズ 1. 予測 (prediction) 2. 実行 (execution) 3. 確認 (verification, confirmation) 4. キャンセル，回復，再実行 (cancellation, recovery, re-execution) cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 Advanced Computer Architecture 26 分岐予測 cycle 3. 確認 add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2 add r8 = r6 + r7 IF OR EX MEM WB PC 予測 add r8 = r8 1. + 1 IF OR EX MEM WB 2. フェッチ sub r9 = r6 - r7 IF OR EX MEM WB ld IF OR EX MEM WB r8 = *(r9) Advanced Computer Architecture 27 分岐予測 cycle 3. 確認 add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2, L0 L0: ld add r8 = *(r6) r6 + r7 PC add r9 r8 = r8 1. + 1 sla << 1 予測 IF OR IF OR EX MEM WB IF OR IF OR EX MEM WB 2. フェッチ add sub r9 = r9 r6 + - 1 r7 ld r8 = r9 *(r9) sub - 1 4. 再フェッチ IF IF OR EX M IF IF OR EX M Advanced Computer Architecture 28 分岐予測 cycle add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB L0: ld r1 == r2, L0 r8 = *(r6) sla r9 = r8 << 1 IF OR IF OR EX MEM WB IF OR IF OR EX MEM WB add r9 = r9 + 1 IF IF OR EX M sub r8 = r9 - 1 IF IF OR EX M ミス･ペナルティ (= H, M = 0) Advanced Computer Architecture 投機の効果 「毎回かかるレイテンシを，ミス時のペナルティに」 （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） 予測ミス率が十分小さければ (ex. 1%)， ミス･ペナルティは1～２サイクル長くなってもよい 29 Advanced Computer Architecture 30 分岐予測とフロントエンド/バックエンド RFRF 命令 キャッシュ フェッチ Fetch リネーム 命令 ウィンドウ ロジック リネーム Rename フロントエンド front-end ディスパッチ Dispatch スケジュール Schedule 演算器 発行 Issue 実行 Exec バックエンド back-end 書戻 WB Advanced Computer Architecture 分岐予測とフロントエンド/バックエンド フロントエンド 分岐予測に基づいて自律的に，命令を命令ウィンドウに詰める バックエンド 命令ウィンドウ内から発行された命令を，実際に実行する 分岐予測の結果を確かめる BE ⇒ FE のインタラクション 分岐予測ミスのみ 31 Advanced Computer Architecture 4.レジスタ・リネーミングと分岐予測 2015/9/30 Advanced Computer Architecture 分岐予測ミス時の回復 予測した分岐命令の，プログラム・オーダ上で下流の命令： 投機的に実行された命令 予測がミスであった場合， 投機的に実行された命令の実行を取り消す，具体的には， デスティネーション・レジスタ（論理）の内容を元に戻す 書き潰すと OUT！ 投機的に実行した命令は， マシン・ステートを不可逆的に更新してはいけない 33 Advanced Computer Architecture 34 分岐予測 cycle ld r1 = *(r2) IF N D bz r1, L0 IF N D li r1 = 0 add r9 = r6 + 1 S I R EX S MEM I R W EX IF N D S I R EX W IF N D S I R EX W W sub r9 = r6 - r7 IF N D S I R EX W ld IF N D S I R EX W r8 = *(r9) Advanced Computer Architecture 論理 Reg の可逆的な更新 Reg リネーミング 各命令のデスティネーションに1つずつ物理 Reg を割り当てる すべての命令の結果が保存してある 書き潰される心配はない 問題は，物理 Reg プールの構造 通常時： 必要な物理 Reg をどうやってとっておくか 必要なくなった物理 Reg をどう解放するか 要/不要をどうやって判断するか ミス時： どうやって元に戻すか 35 Advanced Computer Architecture 36 論理 Reg の可逆的な更新 DB，FS のリカバリに類似 基本は，チェックポインティング（に類似） チェックポイント (CP) ＝ 分岐命令 分岐命令の実行 ＝ 予測の確認 ヒット ⇒ コミットメント (commitment) ミス ⇒ 回復 ただし，対象は fault ではなく，予測ミス Advanced Computer Architecture 37 チェックポインティング exec CP CP CP CP CP program order commit cycle Advanced Computer Architecture 2つの方法 1. ロギング 論理 Reg の更新ログを保存 2. バックアップ 分岐命令 (= CP) ごとに，論理 Reg のイメージをバックアップ 38 Advanced Computer Architecture 論理 Reg ファイル 1. ロギング r1 r2 r3 r4 r31 ld sla sla add r1 r2 r3 r4 = = = = *($sp) r1 << 1 r1 << 2 r3 + r2 r1 r2 r1 r4 リオーダ・バッファ 39 Advanced Computer Architecture 40 2. バックアップ p0 r1 r2 r3 r4 p11 p12 p13 p14 p11 p12 p13 p14 r31 Reg マップ･テーブル p63 物理 Reg ファイル Advanced Computer Architecture 正確な割り込み 例外 (exception) トラップ (trap) 割り込み (interruption) 正確な割り込み (precise interruption) 41
© Copyright 2024 ExpyDoc
