高性能コンピューティング論２ 1 高性能コンピューティング論２ 第6回 分岐予測とプリフェッチ 高性能コンピューティング学講座 三輪 忍 [email protected] 高性能コンピューティング論２ 本日の講義内容 • 分岐予測とプリフェッチの復習 • 分岐予測 • プリフェッチ 2 高性能コンピューティング論２ 3 分岐予測とプリフェッチの復習 高性能コンピューティング論２ 4 投機のフェーズ 予測 (prediction) 2. 実行 (execution) 3. 確認 (verification, confirmation) 4. キャンセル，回復，再実行 (cancellation, recovery, re-execution) 1. cycle A 1. 予測 3. 確認 2. 実行 B 4. 再実行 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 5 分岐予測 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) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 6 分岐予測 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 IF OR EX MEM WB PC 予測 add r8 = r8 1. + 1 IF OR IF OR EX MEM WB 2. フェッチ sub r9 = r6 - r7 ld r8 = *(r9) 4. 再フェッチ IF IF OR EX M IF IF OR EX M ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 7 分岐予測 cycle add r5 = r4 + r3 IF OR EX MEM WB be IF OR EX MEM WB r1 == r2 add r8 = r6 + r7 IF OR IF OR EX MEM WB add r8 = r8 + 1 IF OR IF OR EX MEM WB sub r9 = r6 - r7 IF IF OR EX M ld IF IF OR EX M r8 = *(r9) ミス･ペナルティ (= H, M = 0) ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 8 投機の効果 • 「毎回かかるレイテンシを，ミス時のペナルティに」 • （予測ミスによるレイテンシの増加）＝ （予測率） ×（予測ミス率） ×（ミス･ペナルティ） • 予測ミス率が十分小さければ (ex. 1%)， • ミス･ペナルティは1～２サイクル長くなってもよい ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「投機」より 高性能コンピューティング論２ 9 投機 と キャッシュ・アクセス • キャッシュ・アクセスも投機の一種 • 「キャッシュにある」と予測してアクセス • キャッシュ・アクセスを行い，データがキャッシュにあるか否かを確認 • キャッシュになければ諸々の処理をやり直す 高性能コンピューティング論２ 10 プリフェッチ（通常アクセスの場合） ④ データ取得 • 近い将来にアクセスされると 予測したデータをあらかじめ キャッシュに移動 演算 ユニット ① アクセス ② ミス *(r4) L1D キャッシュ • ロード命令に依存する命令 の先行制約を緩和 *(r4) ③ アクセス L2 キャッシュ *(r4) cycle 高性能コンピューティング論２ 11 プリフェッチ（プリフェッチを行った場合） ⑤ データ取得 • 近い将来にアクセスされると 予測したデータをあらかじめ キャッシュに移動 演算 ユニット ④ アクセス ① 予測 *(r4) ③ 移動 L1D キャッシュ • ロード命令に依存する命令 の先行制約を緩和 *(r4) ② アクセス L2 キャッシュ *(r4) cycle 高性能コンピューティング論２ 分岐予測 12 高性能コンピューティング論２ 13 分岐命令の出現頻度 • Run Length : • 分岐から次の分岐までの命令数 • 3～5命令 • フェッチ幅 2～4 だと… • ほとんど毎サイクル，分岐命令をフェッチ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 14 分岐予測の効果 (1/3) • プログラム • n ：プログラムの命令数 • b ：そのうち，分岐命令の割合 • プロセッサ： • p ：分岐予測ミス・ペナルティ • プログラム on プロセッサ • i0 ：分岐予測ミス率 0% の時の IPC • β ：分岐予測ミス率 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 15 分岐予測の効果 (2/3) 分岐予測ミス率 0% の時のプログラムの実行サイクル数： n / i0 • プログラム • n • b ：プログラムの命令数 ：そのうち，分岐命令の割合 • プロセッサ： • p ：分岐予測ミス・ペナルティ 分岐予測ミス数： nbβ • プログラム on プロセッサ • i0 ：分岐予測ミス率 0% の時の IPC • β ：分岐予測ミス率 分岐予測ミスによる実行サイクル数の増加： {n b β} p 分岐予測ミス率 β の時の IPC： n / {n / i0 + {n b β} p} = 1/ {1 / i0 + b p β} ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 16 分岐予測の効果 (3/3) • プログラム • b ：そのうち，分岐命令の割合 分岐予測ミス率 β の時の IPC： 1/ {1 / i0 + b p β} • プロセッサ： • p ：分岐予測ミス・ペナルティ • プログラム on プロセッサ • i0 ：分岐予測ミス率 0% の時の IPC • β ：分岐予測ミス率 i0 = 2，b = 0.2，p = 10 とすると， 1/ {1 / i0 + b p β} = 1 / { 0.5 + 0.2 ×10× β} = 1 / (0.5 + 2β) [ 各分岐予測ミス率における IPC 低下率 ] i0 = 2 0.4 O 1.0 [ IPC と分岐予測ミス率の関係 ] β 0% 1% 3% 5% 10% 50% 100% IPC 2.0 1.92 1.79 1.67 1.43 0.67 0.4 IPC 低下率 −0% −4% −11% −16% −29% −66% −80% β わずかな分岐予測ミス率の改善が性能に大きく影響 いまだに分岐予測の研究が続いている理由 高性能コンピューティング論２ 17 分岐予測に使える/使えない情報 • 分岐予測に使用できる情報 • フェッチした命令のアドレス（fetch PC） • 過去の出来事（分岐命令の実行履歴等） • 分岐予測に使用できない情報 • （フェッチした）分岐命令が成立した場合の分岐先アドレス • 毎サイクル，フェッチするためには，命令をフェッチしてから next PC を 求めるのでは遅い 高性能コンピューティング論２ 18 分岐予測 • 分岐予測： • 分岐方向予測 • 分岐先予測 • 予測処理の流れ bool pred_taken = branch_dir_pred(fetch_PC); addr_t taken_PC = btb_lookup(fetch_PC); /* BTB ミスなら 0 */ addr_t untaken_PC = fetch_PC + INSN_SIZE * FETCH_WIDTH; addr_t next_PC = (taken_PC && pred_taken) ? taken_PC : untaken_PC; 分岐成立 • Untaken:分岐不成立 • Taken: ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 19 分岐先予測 • 役割 • 分岐成立の場合の分岐先アドレスを予測 • 不成立の場合のアドレスは常に計算しているため （分岐以外の命令と同様） • 基本方針 • 過去に出現した分岐命令の分岐先アドレスを記録しておき，次に同じ分岐 命令が出現したら，（成立時には）同じアドレスに分岐すると予測 • ほとんどの分岐命令は，（成立時の）分岐先アドレスが１つ • 例外： レジスタ間接分岐 • 実装（BTB: Branch Target Buffer） • 過去に出現した分岐命令の PC と分岐先アドレスを記録する表を用意 • フェッチした PC が記録表にヒットしたら，表から読み出すことで分岐先アド レスを取得 高性能コンピューティング論２ 20 BTB : Branch Target Buffer fetch PC tag valid taken PC selector taken PC ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 21 BTB の動作 tag fetch PC 400 2 valid taken PC 0 0 400 1 400 32 selector taken PC 40032 高性能コンピューティング論２ 22 レジスタ間接分岐の分岐先予測 • RAS: Return Address Stack • Return 命令の戻り先アドレスを予測 • Call 命令の出現時に戻り先アドレスを スタックに push • Return 命令の出現時にスタックを pop して戻り先アドレスを取得 func A func B func C 200 call B RAS 204 push 804 204 push 800 call C 400 return 204 pop 804 xx 204 xx 900 return • Indirect Predictor • Return 以外のレジスタ間接分岐の分岐先アドレスを予測 • PC と分岐履歴の XOR でインデクシングした表を用いて分岐先予測 • 同一分岐命令の複数の分岐先アドレスを記録可能 • 一部の ARM プロセッサで採用 pop 高性能コンピューティング論２ 23 分岐方向予測の原理 その1 • ローカル分岐履歴 (local branch history) • 基本的には，前回と同じだろう • ヒステリシスを持たせ，発振を防ぐ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 24 2-bit 飽和形カウンタ (2-bit saturating counter) fetch PC PHT (Pattern History Table) 10 taken 11 strongly taken 10 weakly taken 01 weakly untaken 00 strongly untaken untaken ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 25 PHT (Pattern History Table) • タグ，有効ビットがない • 「ミス」がない • コンフリクト（衝突）が起こる • あまり気にしなくてもよい • どうせ，そこそこ外れるものだから • エントリ数が十分多ければ（数K），確率は低い • タグの分だけ PHT のエントリを増やしたほうが得 • PHT: 2b • タグ： 10～30ｂ ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 26 分岐方向予測の原理 その2 • グローバル分岐履歴 (global branch history) • ローカルは，自身の履歴 • グローバルは，すべての分岐 • 最近実行された分岐，12回程度の結果を記録 • たとえば： for (int i = 0; i < N; ++i) if (i % 2) even(); else odd(); • NNNTNNNT… ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 27 gshare (McFarling ‘93) fetch PC • 同じ分岐でも， 0001 PHT 00 XOR 0010 0 0 1 1 Global History Register 01 11 01 01 グローバル履歴が異なれば， 別のカウンタを使用． • ただし，コンフリクトが多発 • 数十パタン／分岐 • コンフリクトを軽減する研究 • 「要は，圧縮」 01 01 01 ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 28 分岐命令のプロファイル • 分岐の方向には，偏りがある • 利用して，テーブルを圧縮 taken 率 taken 率 1.0 1.0 0.0 0.0 分岐命令 （taken 率でソート） always untaken always taken ※ 五島正裕，「アドバンストコンピュータアーキテクチャ」，講義資料「分岐予測器とトレース・キャッシュ」より 高性能コンピューティング論２ 29 最近の分岐予測器 • 「長い分岐履歴をどのように扱うか？」が議論の中心 • 長い分岐履歴 ＝ 過去 数百個の分岐命令の履歴 • 長い分岐履歴を利用しなければ予測がヒットしない分岐命令もある • 分岐履歴が長くなると，テーブルの学習に時間がかかるようになる • TAGE: TAgged GEometric history length branch predictor† • 分岐命令毎に適切な長さの分岐履歴を用いて予測 • 容量効率に優れる • 基本，1エントリ/分岐命令 • タグを用いることでコンフリクトを（なるべく）回避 • 長い履歴を必要としない分岐は，短い履歴の予測器を使用 （学習時間の短縮） • 2000年代に起こった分岐予測の議論に終止符 † A. Seznec and P. Michaud, A case for (partially) tagged Geometric History Length Branch Prediction, JILP, 2006 高性能コンピューティング論２ プリフェッチ 30 高性能コンピューティング論２ 31 キャッシュとプリフェッチ • キャッシュの中身 • 命令 • データ • プリフェッチの対象 • 命令： 近々フェッチされる命令を上位キャッシュに移動 • データ： 近々ロードされるデータを上位キャッシュに移動 • プリフェッチの階層 • 原理的にはあらゆる階層に適用可能 • 最も旨みがあるのは，メモリ⇒最下位キャッシュ 間 1～3 cycle 演算ユニット 10～ cycle L1Dキャッシュ 100～ cycle L2キャッシュ メイン・メモリ 高性能コンピューティング論２ 32 キャッシュ・ミスが性能に与える影響 • 命令キャッシュ・ミスの方が性能への被害が甚大 • キャッシュ・ミスが解決するまでフロントエンドを停止 • データ・キャッシュ・ミスの被害を受けるのは，ミスを起こしたロード命令 に依存する命令のみ • 命令キャッシュ・ミスの方が発生頻度は低い • ほとんどのプログラムは1%以下 • 時間的局所性： 最近フェッチした命令を再びフェッチ ループ • 空間的局所性： 最近フェッチしたPCの次のPCをフェッチ 分岐成立以外 • データ・キャッシュ・ミスの方が発生しやすい • ほとんどのプログラムが2-3% • 多いプログラムでは10%を超えることもある • 以下ではロード・データのプリフェッチについて説明 高性能コンピューティング論２ 33 プリフェッチの基本戦略 • What： どのデータを移動するか？ • 近々，ロードされるデータ • 間違ったデータをプリフェッチした場合は，資源とエネルギーの無駄 • When： いつデータを移動するか？ • 早すぎると，参照前にデータがキャッシュから追い出される可能性がある • ロード命令の実行ぎりぎりで上位キャッシュにデータが届くのが理想 • 普通は，キャッシュに対する規則的なアクセス・パターンを検出した時 • Where： どこにデータを格納するか？ • 普通はキャッシュ • 間違ったデータをプリフェッチするとキャッシュが汚れる 高性能コンピューティング論２ 34 プリフェッチに使える/使えない情報 • プリフェッチに使用できる情報 • データ・アクセス（ロード命令のPCやデータ・アドレスの）履歴 • 分岐履歴 などの過去の情報 • プリフェッチに使用できない情報 • （キャッシュ・ミスする予定の）ロード命令の PC，データ・アドレス等 • ロード命令のフェッチ後にプリフェッチしたのでは，間に合わない 高性能コンピューティング論２ 代表的なプリフェッチャ • ストリーム/ストライド・プリフェッチャ • マルコフ・プリフェッチャ 35 高性能コンピューティング論２ 36 ストライドとストリーム • ストライド • メモリ・アドレスの間隔 • ストライド・アクセス： 一定のストライドで繰り返されるメモリ・アクセス • 例） アドレス 4, 8, 12, 16, … へのアクセス（ストライドは4） • ストリーム • ストライド ＝ 1 のケース • ストライド・プリフェッチャでストリーム・アクセスに対するプリフェッチも可能 高性能コンピューティング論２ 37 ストライド・プリフェッチャ (= Reference Prediction Table) x x 0x104 0x100 0x100 0x108 0x104 0x108 0x100 0x104 4 stable init 0x10b 0x108 • キャッシュ・ミス時に当該命令がストライド・ アクセスを行っているか否かを検出 • ストライド・アクセスを行っていた場合は表 の情報を元にデータをプリフェッチ H. Kim, The lecture material of CS4290/CS6290 in Georgia Tech 高性能コンピューティング論２ 38 マルコフ・プリフェッチャ • キャッシュ・ミスするアドレス の系列はマルコフ・モデル に従うと仮定 • プリフェッチャがキャッシュ・ ミスしたアドレスを観測し， アドレスを状態とみなして 状態遷移確率表を生成 • キャッシュ・ミス時に上記の 表を参照し，次にミスする アドレスを予測 • 不規則なメモリ・アクセス・ パターンも予測可能 H. Kim, The lecture material of CS4290/CS6290 in Georgia Tech 高性能コンピューティング論２ 39 その他のプリフェッチ方式 • 事前実行方式 • メモリ・アクセスに関係する部分のみからなる事前実行用コードを作成 • 本実行に先行して事前実行用コードを実行することでプリフェッチ • 任意のメモリ・アクセス・パターンに対応可能 • 事前実行のためのハードウェア資源が必要 • ソフトウェア・プリフェッチ • 一部の ISA はプリフェッチ用の命令をサポート • ユーザまたはコンパイラが上記の命令を使用してデータをプリフェッチ • メモリ・アクセス・パターンにある程度の規則性がないと使いづらい • プリフェッチ・タイミングを制御しづらい 高性能コンピューティング論２ 40 プリフェッチと投機 • 一般的な投機（e.g., 分岐予測） • 予測 ⇒ 実行 ⇒ 確認 ⇒ キャンセル，回復，再実行 • キャンセル，回復，再実行を行わないと「正しい実行」にならない • プリフェッチの場合はミス時の（特別な）処理が不要 • 間違ったデータをプリフェッチしても致命的なエラーは発生しない • キャッシュが汚れるだけ • キャンセル/回復のコストを考えると，そのままにしておくのが無難 • 再実行は通常のキャッシュ・ミスと同様の処理を行えばよい 高性能コンピューティング論２ 本日のまとめ 41 高性能コンピューティング論２ まとめ • 分岐予測とプリフェッチの復習 • 分岐予測 • プリフェッチ 42 高性能コンピューティング論２ 次回 • 12/3（木） 10:40～ • 「メモリ非曖昧化」について解説 43
© Copyright 2024 ExpyDoc
