Out-of-orderスーパースカラプロセッサ 4 instructions Instruction flow Instruction Instruction cache cache 計算機アーキテクチャ特論 (Advanced Computer Architectures) Branch Branch handler handler Fetch Fetch Decode Decode Rename Rename Register Register file file RS ６．先端の分岐予測 吉瀬 謙二 計算工学専攻 kise _at_ cs.titech.ac.jp www.arch.cs.titech.ac.jp W611講義室 木曜日 15:00 – 16:30 Store queue Data Data cache cache Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 分岐方向の予測（分岐予測） 分岐成立の場合にのみ，分岐先アドレスを登録する． 通常は valid bit は利用しない． Byte 31 30 Tag Hit ... 13 12 11 ... 20 2 1 0 offset Target Address 10 Index Index Valid Tag プログラムカウンタ Branch Target 0 1 2 . . . 1021 1022 1023 分岐予測 32 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Bimodal (ISCA 1981) シンプルな分岐予測 ２ビットカウンタ方式 Taken(1), Not Taken(0) トレースデータ （分岐アドレス，分岐結果） 0040d89c 0040d89c 0040d89c 0040d89c 0040d89c 0040d89c 0040d89c 0040d8a2 0040d8c0 0040d8c4 0040d8cd 0040d8c0 0040d8c4 0040d8cd 0040d8c0 0040d8c4 0040d8cd 0040d8e7 0040d923 0040d7ab 0040d7cd 0040d7f9 1 1 1 1 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 0 0 B1 ２ビットカウンタ方式 大域的な偏り，局所性の利用 ２ビットカウンタの状態に応じて予測 予測のためのメモリは２ビット 状態の更新 Taken 2 bit Strongly Taken (11) Taken Untaken Taken Prediction Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Weakly Untaken (01) B3 B3 0 Untaken Strongly Untaken (00) Untaken 1 BE B2 BE B2 BE B2 0 BE: 0 B2: 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 B3 分岐アドレス（プログラムカウンタ）毎に履歴を切り替える パターン履歴表は２ビットカウンタの配列． 分岐アドレスによりパターン履歴表（ＰＨＴ）のインデックスを作成 Pattern History Table (PHT) Program Counter 2n entry Taken Strongly Taken (11) Untaken Taken B2 0 B2 Weakly Taken (10) B3 0 BE Taken Untaken Taken n … 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 分岐方向 （成立／不成立） 分岐履歴など の情報 20 0040d6c5 0040d6b8 0040d6bc 0040d6c5 0040d6df 0040d71f 0040d736 0040d7ab 0040d7cd 0040d7f9 0040d81e 0040d7f9 0040d81e 0040d7f9 0040d81e 0040d83d 0040d86d 0040d86d 0040d86d 0040d86d 0040d86d 0040d86d Memory dataflow Memory Register dataflow 分岐先アドレスの予測, Branch Target Buffer (BTB) Operand Operand Fetch Fetch Floating-point Reorder buffer 1 Integer Prediction Weakly Untaken (01) 2 bit Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Weakly Taken (10) Untaken Taken Untaken Strongly Untaken (00) Untaken Gshare (TR-DEC 1993) 分岐履歴 B3 B3 Not Taken (0) B2 Not Taken (0) Taken (1) B2 B2 B2 B2 1 1 1 0 グローバル分岐履歴と分岐アドレスとの排他的論理和によりパターン履歴表 へのインデックスを作成 パターン履歴表は２ビット飽和型カウンタの配列で，選択された２ビットカウンタの 値により分岐方向を予測（bimodalと同じ） B3 分岐結果を用いて，予測に利用したカウンタを更新 010101000 （シフトレジスタ） B2の分岐履歴 B1 B2 *C = *C + (*A + *B) i++ A++ B++ C++ i<4 False, not taken B3 Branch History Register (BHR) return Weakly Untaken (01) 分岐不成立に偏っているものをUntaken PHTに格納 Prediction Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 予測精度（予測ミス率） 2 bit Pattern History Table 40 8KB hardware budget Prediction SERV-3 SERV-2 Benchmark for CBP(2004) by Intel MRL and IEEE TC uARCH. Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 MM-5 MM-4 MM-3 MM-2 MM-1 INT-5 INT-4 INT-3 0 INT-2 Untaken PHT 5 SERV-1 (d) Bimode Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Choice PHT 10 FP-5 … Taken PHT Prediction … … XOR 15 INT-1 … Pattern History Table 20 FP-4 XOR Branch History Register Bimode 25 FP-3 (b) Bimodal Gshare 30 FP-1 Branch History Program Counter Register Mispredictions Rate (%) … Prediction Bimodal 35 Prediction (a) ２ビットカウンタ方式 (c) Gshare Untaken PHT Taken PHT Not Taken(0) ここまでの分岐予測器 Choice PHT … … Choice PHT は命令アドレス Taken PHT, Untaken PHT は命令アドレスと分岐履歴 Prediction Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Program Counter Program Counter XOR インデックスを工夫 Gshare Program Counter Branch History Choice PHT の内容で， どちらのテーブルを利用 するか選択 Taken(1) XOR n 分岐成立に偏っているものをTaken PHTに格納 m n 2n entry … XOR Branch History Register (BHR) Program Counter 偏りを利用して競合の悪影響を緩和 Average PHT Branch History Register (BHR) m Untaken … n Strongly Untaken (00) Untaken Bimode (MICRO 1997) 分岐成立に偏っているもの 分岐不成立に偏っているもの Program Counter Untaken Taken 2 bit FP-2 Prediction Weakly Taken (10) Untaken Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 PHTの競合が発生して性能が低下 PCとBHRによって特定される予測（成立，不成立）には偏りが存在する ので，これらを別のテーブルに格納することで競合の悪影響を緩和 Taken Strongly Taken (11) Taken n True, taken Gshare の改良 Pattern History Table (PHT) 2n entry XOR Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Taken m n … 1110 ? 11101 ? 111011 ? 1110111 ? 11101110 ? Program Counter i=0 SERV-5 B1 B3 Not Taken (0) SERV-4 Taken(1), Not Taken(0) Benchmark for CBP(2004) by Intel MRL and IEEE TC uARCH 5.5 算術演算などの分岐命令以外の命令を含む数で ある． 5.0 表の3列目(静的分岐)には，各ベンチマークプロ グラムの実行における静的な条件分岐命令の 数を示す． SpecFPでは条件分岐命令の数が1000以下と少 ない，一方，サーバ系のベンチマークでは，静的 な条件分岐命令の数が1万以上と多い． 表の4列目(All-taken)に，全ての条件分岐命令 の実行回数に占める，極端な偏りのある成立分 岐命令の動的な割合を示す． 6.0 表の2列目に，各ベンチマークプログラムの実行 命令数(単位は百万命令)を示す． コンテキストスイッチの影響 表の1列目にベンチマークの名前を示す． Mispredictions Per Kilo Instructions MM-3 の値が最も高く，その割合は35%に達する． また，サーバ系の全てのベンチマークで9%以上と 高い． Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 FP-1の場合には65%，サーバ系の全てのベンチ マークで44%以上と非常に高い． 4.0 3.5 3.0 2.5 1.5 0.5 0.0 8KB Bimode-Plus, WIDE Mispredictions/KI Bimode, WIDE 3.0 2.5 2.0 1.5 1.0 0.5 Hmean twolf bzip2 vortex gap eon parser crafty mcf gcc 0.0 gzip IPC (Retired Instructions Per Cycle) 4.0 Gshare, WIDE 8.0 7.8 7.6 7.4 7.2 7.0 6.8 6.6 6.4 6.2 6.0 5.8 5.6 5.4 5.2 5.0 4.8 SPEC CINT95 Average Gshare.best Bimode.best Bimode-Plus.best 1 10 Hardware budget in kilobytes IPSJ Journal 20005, Kise Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 ２レベル分岐予測 他の分岐（ローカルあるいはグローバル）の振る舞いを 利用する分岐予測を２レベル分岐予測，相関を利用する 分岐予測と呼ぶ． Correlating predictor BHR Pattern History Table Pattern History Table XOR XOR BHRs … Two-level predictor PC Program Counter … Prediction Gshare ２レベル分岐予測の構成 100 SWoPP-2003 Kise Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 ２レベル分岐予測 64KB IPSJ Journal 20005, Kise 分岐予測精度 (SPEC CINT95の平均） 深い命令パイプライン，大規模な投機処理プロセッサ 3.5 16KB 32KB Hardware Budget Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 分岐予測精度とプロセッサ性能 Gshare, 8M Bimode, 8M Bimode-Plus(Untaken), BHR_NOB, 8M Gshare Bimode Bimode-Plus(Untaken), BHR_NOB 2.0 1.0 表の5列目(All-untkn)に，全ての条件分岐命令 の実行回数に占める，極端な偏りのある不成立 分岐命令全の動的な割合を示す． 4.5 BHR Prediction Pshare Program Counter PC PC Pattern History Table XOR … Gshare Prediction BHRs BHR GAs Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Prediction Prediction Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 PAs ハイブリッド方式 Alpha 21264 (1998 DEC) 複数の分岐予測の利点 （トーナメント予測） Alpha 21264 多数決（Majority vote）により最終予測を決定 Program Counter Global History Choice Prediction (4,096 x 2 bit) Program Counter ハイブリッド方式 E-gskew (ISCA 1997) BIM … Local Prediction (1,024 x 3 bit) G0 … … … Prediction F2 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 研究レベルの分岐予測 ここまでの話は商用化されている．または，商用化しよう として設計された例がある． ハードウェア量と分岐履歴の長さ パターン履歴表のハードウェアが支配的 ２ビットカウンタのNエントリのテーブル 分岐履歴レジスタのとりうる最大長を n bit とすると G1 Gshare-base Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 ここからは研究レベルの話 … Global Prediction (4,096 x 2 bit) Pshare-base Prediction … F1 Majority vote BHR Program Counter … Local History Table (1,024 x 10bit) N × 2 bit （例えば，３２Kエントリで８ＫＢ） 2n × 2 bit （例えば，n = 15 で８ＫＢ） すぐには実現できないかもしれないが Program Counter Branch History Register Pattern History Table XOR … Prediction (c) Gshare Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Perceptron (HPCA 2001) パーセプトロン パーセプロロンモデル x1からxnまでのnビットの分岐履歴を入力とする． y を計算する． w は符号付きの整数で表現 y の値がある閾値より高い場合に成立と予測する． 分岐アドレスによりパーセプトロンを選択 グローバル分岐履歴を用いて予測 分岐ミス，|y| < θ の時にトレーニング ８ＫＢのハードウェア量で，３４ビットの分岐履歴 Program Counter 1 w0 x1 w1 x2 w2 ... Branch History (x) xn wn … Selected Perceptron y Perceptron Model Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 y Compute y Prediction Table of Perceptrons (w) 計算と更新の作業が複雑 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 パターンマッチングを用いた分岐予測 パターンマッチングの可能性 マッチングの対象となる分岐履歴の長さ N 予測: 0 or 1? 分岐履歴 1 0 最長一致長 M 最長一致パターン N = 1024 x 1024 (one million) に設定 0 1 M = 16, 32, 64, 128, 256, 512, 1024 に設定 0 最長一致パターン 0 1 0 過去の履歴との最長一致のパターンを見つける． それぞれの最長一致パターンの次に出現する０と１の回数を数え，多い方 を予測値とする． Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 テーブルのエントリ数を非常に大きく設定した Gshare の予測ミス率は4.71 信学会ソサイエティ大会，２００５, Kise, Iwata Partial Pattern Matching (CBP 2004) 予測精度（予測ミス率） Table 4 Table 3 Table 2 Table 1 Table 0 20 pc pc h[0:9] pc h[0:19] pc h[0:39] pc h[0:79] 18 8KB hardware budget hash u 3b ctr 8 8 8 bit tag 10 3b ctr u 8 =? 1 8 8 bit tag 10 3b ctr u 8 =? Gshare 1 u 8 =? 1 8 8 bit tag =? 1 1 Bimode hash 1 1 14 PPM 12 10 8 6 4 2 1 Bimodal ISCA 1981 branch history, hash function Gshare TR-DEC 1993 Agree ISCA 1997 Gskew, E-gskew ISCA 1997 Bimodal Gshare Bimode ハイブリッド方式 パーセプトロン パターンマッチング （ＰＰＭ） PPM CBP 2004 2Bc-gskew TR-INRIA 1999 Bimode YAGS MICRO 1997 MICRO 1998 de-alias Perceptron Fast-Neural HPCA 2001 MICRO 2003 Variable Length Path ASPLOS 1998 table element history length optimization ISCA (International Symposium on Computer Architecture) MICRO (International Symposium on Microarchitecture) PACT (International Conference on Parallel Architectures and Compilation Techniques) ASPLOS (International Conference on Architectural Support for Programming Languages and Operating Systems) Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 ２ビットカウンタの配列，プログラムカウンタ グローバル分岐履歴の利用 偏りを用いて表を分離，メタな予測器 複数の予測方式の利用，多数決 パーセプトロンモデル，長い分岐履歴の利用 最長一致パターンの利用 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 Average SERV-5 SERV-4 SERV-3 SERV-2 MM-5 SERV-1 分岐予測のまとめ hybrid Two-level adaptive MICRO 1991 MM-4 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 分岐予測のまとめ hash function, hybrid MM-3 Benchmark for CBP(2004) by Intel MRL and IEEE TC uARCH. prediction 0/1 重要な分岐予測の根底にあるアイデアとその構成を解説 Filter BTB, de-alias PACT 1996 MM-2 パターンマッチングを利用する現実的な分岐予測 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 INT-5 1 MM-1 FP-1 CBP2004プレゼンテーションスライド INT-4 0 1 INT-3 1 hash INT-2 1 hash FP-5 8 bit tag 10 hash INT-1 3b ctr 8 hash FP-4 10 hash Mispredictions Rate (%) hash Bimodal 16 12 3b m ctr 計算時間が莫大 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 FP-3 FP-2 Prediction 参考書（１），教科書 分岐予測に関する今後の展望 新しい予測方式の開発 参考書 分岐予測の精度の計算機性能 予測精度の向上 投機的な更新 パーセプトロンの実現 高い予測精度，複雑なハードウェア 分岐予測の精度と計算機アーキテクチャ 他の予測への適用 コンピュータアーキテクチャ， 村岡 洋一 著， 近代科学社，1989 計算機システム工学， 富田 真治，村上 和彰 著，昭晃堂，1988 コンピュータハードウヱア， 富田 真治，中島 浩 著，昭晃堂，1995 計算機アーキテクチャ， 橋本 昭洋 著，昭晃堂，1995 教科書 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 コンピュータの構成と設計 第３版、 パターソン＆ヘネシー（成田光彰 訳）、 日経ＢＰ社、2006 命令レベル並列処理， 安藤秀樹 コロナ社 Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 参考書（２） アナウンス Computer Architecture, Fourth Edition: A Quantitative Approach, Fourth Edition ISBN-10: 0123704901 ISBN-13: 978-0123704900 １１月２２日（木）は金曜日授業のため講義はありません． 第 ７回 １１月２９日（木） １２月６日（木）は休講予定 第 ８回 １２月１３日（木） 第 ９回 １２月２０日（木） 第１０回 １月１０日（木） 講義スライド Publisher: Morgan Kaufmann; 4 edition (September 13, 2006) Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 32 33 www.arch.cs.titech.ac.jp Adapted from Computer Organization and Design, Patterson & Hennessy, © 2005 34
© Copyright 2024 ExpyDoc
