プログラムの実行経路の偏りに 着目した分岐予測法 ○築地 孝典，井上 弘士，村上 和彰 九州大学 大学院 システム情報科学府 発表手順 • 従来の分岐予測器 – 分岐予測の目的と動作 – 消費エネルギーモデル • ホットパス分岐予測法（HPBP法） – 動作原理 – 消費エネルギーモデル • 評価 – 結果 – 考察 • 関連研究 • おわりに – まとめ – 今後の課題 2 分岐予測とは • 分岐予測とは – 分岐命令の分岐成立/不成立を命令フェッチ時に予測 – 命令パイプライン処理における分岐ハザードの解決 • 分岐予測の実現法 分岐方向予測 分岐成立か不成立か 分岐命令 アドレス 過去の 分岐結果 分岐先予測(Branch Target Buffer) 分岐成立時の分岐先はどこか 分岐命令 アドレス 分岐先 アドレス 3 大規模化・複雑化する分岐予測器 • 分岐予測の重要性 – 予測ミスペナルティ大 – 予測精度がプロセッサの性能に与える影響大 • 分岐予測器の現状 – 分岐予測精度向上を目指した大規模化・複雑化 例1:2レベル分岐予測器(Gshare) 例2:トーナメント分岐予測器 PC グローバル 分岐履歴 XOR 分岐履歴 Selector BP１ BP２ 4 分岐予測における 消費エネルギーの増大 • 分岐予測器の消費エネルギーモデル EBPRED = (Edir + Ebtb) × Nbpred EBPRED：分岐予測器の消費エネルギー Edir：分岐方向予測器の消費エネルギー Ebtb：Branch Target Bufferの消費エネルギー Nbranch：分岐予測回数（通常、全命令） • 分岐予測はテーブルアクセス – 消費エネルギーはテーブルサイズに依存 • 分岐予測器の消費エネルギーの増大 – 大規模化・複雑化によるテーブルサイズの増大 ※参考論文：[Chaver 2003] – チップ全体の10%以上※ 「毎命令」「大きなテーブル」にアクセスしていることが問題！ 5 分岐予測器の低消費エネルギー化に 向けたアプローチ • 基本的な考え方 – 予測が容易な分岐命令にはエネルギーをかけない • 予測が容易な分岐命令とは？ – ホットパスに着目 パス A B D C E F G 上から下へ流れる命令列 左図中のパス ABDF ABDFG ホットパス ACEF CEF ACEFG CEFG パスの中で全実行時間に 占める割合が多いもの 6 ホットパスに着目した 低消費エネルギー化 • ホットパスの特徴を利用 – ホットパス中の分岐命令が高確率 で決まった方向に分岐 A • ホットパス分岐予測法(HPBP法) – ホットパス専用の分岐予測器 – 少数の分岐命令情報のみ必要なた め、エネルギーは少ない • ホットパス実行中 – ホットパス分岐予測法を使用 B C D E • ホットパス以外を実行中 – 従来型分岐予測器を使用 F （ エ従 ネ来 ル型 ギ分 ー岐 大予 ）測 器 （ エホ ネッ ト ルパ ギス ー分 小岐 ）予 測 法 ホットパス 7 ホットパス実行時間の割合 ホ 100 ッ 90 ト パ 80 ス 実 70 行 時 60 間 が 50 全 40 実 行 30 時 間 20 に 占 10 め 0 る 割 合 (%) 上位10本 上位20本 1 64 g zi p 1 64 1 64 1 64 1 81 1 81 g zi p mc f mc f l re f . lg r e lg r e r g e r ed f. gr a d .g r d .l o .i n ph i c l o g g ap h ic g zi p g zi p 2 56 r ef . bz i p in 2 56 AV G 2 2 lg r e f. r ed so u .g r a r ce ph i c bz i p ベンチマークプログラム 8 ホットパス分岐予測法(HPBP法) PC Z HPBP法 ホットパス テーブル ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ 分岐命令 分岐先 アドレス アドレス A先頭 A終端 C先頭 C終端 E先頭 E終端 A先頭 A終端 C先頭 ルックアップテーブル F 分岐不成立 9 HPBP法の内部構成 • ホットパスを実行中 か否かの判定機構 – ヘッドテーブル ヘッドテーブル パスの先頭 アドレス ポインタ ルックアップテーブル • ホットパスの先頭アドレ スを格納 • 各ホットパステーブルへ の参照アドレスを格納 • ホットパス中の予測 機構 分岐命令 分岐先 アドレス アドレス 分岐命令 分岐先 アドレス アドレス 読 み 出 し – ホットパステーブル • ホットパス中の分岐命令 と分岐先アドレスを登録 – ルックアップテーブル • ホットパステーブルから 読み出した分岐命令と 分岐先アドレスを格納 ホットパス テーブルA ホットパス テーブルB 10 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 A先頭 ポインタ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 ルックアップテーブル F 11 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ A先頭 ヒット！ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 A終端 C先頭 ルックアップテーブル F 12 HPBP法の動作 PC Z HPBP法 ホットパス テーブル ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ 分岐命令 分岐先 アドレス アドレス A先頭 A終端 C先頭 C終端 E先頭 E終端 A先頭 A終端 C先頭 ルックアップテーブル F 分岐不成立 13 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A B パスの先頭 アドレス C D E 従来型 分岐予測器 ポインタ A先頭 ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 一致！ A終端 C先頭 ルックアップテーブル F C先頭 14 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 A先頭 ポインタ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 C終端 E先頭 ルックアップテーブル F 15 HPBP法の動作 PC Z HPBP法 ホットパス テーブル ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ 分岐命令 分岐先 アドレス アドレス A先頭 A終端 C先頭 C終端 E先頭 E終端 A先頭 C終端 E先頭 ルックアップテーブル F 分岐不成立 16 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A B パスの先頭 アドレス C D E 従来型 分岐予測器 ポインタ A先頭 ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 一致！ C終端 E先頭 ルックアップテーブル F E先頭 17 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 A先頭 ポインタ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 E終端 A先頭 ルックアップテーブル F 18 HPBP法の動作 PC Z HPBP法 ホットパス テーブル ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ 分岐命令 分岐先 アドレス アドレス A先頭 A終端 C先頭 C終端 E先頭 E終端 A先頭 E終端 A先頭 ルックアップテーブル F 分岐不成立 19 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A B パスの先頭 アドレス C D E 従来型 分岐予測器 ポインタ A先頭 ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 一致！ E終端 A先頭 ルックアップテーブル F A先頭 20 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 A先頭 ポインタ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 ホットパス E終端 A先頭 が終了 ルックアップテーブル F 21 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ A先頭 ヒット！ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 A終端 C先頭 ルックアップテーブル F 22 HPBP法の動作 PC Z HPBP法 ホットパス テーブル ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 ポインタ 分岐命令 分岐先 アドレス アドレス A先頭 A終端 C先頭 C終端 E先頭 E終端 A先頭 A終端 C先頭 ルックアップテーブル F 分岐不成立 23 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A B パスの先頭 アドレス C D E 従来型 分岐予測器 ポインタ A先頭 ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 一致！ A終端 C先頭 ルックアップテーブル F C先頭 24 HPBP法の動作 PC Z HPBP法 ヘッドテーブル A パスの先頭 アドレス B C D E 従来型 分岐予測器 A先頭 ポインタ ホットパス テーブル 分岐命令 分岐先 アドレス アドレス A終端 C先頭 C終端 E先頭 E終端 A先頭 C終端 E先頭 ルックアップテーブル F 25 HPBP法の動作 PC Z HPBP法 A B ホットパス テーブル ヘッドテーブル パスの先頭 アドレス C 従来型 分岐予測器 ポインタ 分岐命令 分岐先 アドレス アドレス A先頭 A終端 C先頭 C終端 E先頭 E終端 A先頭 ホットパス Dから離脱 E C終端 E先頭 ルックアップテーブル F 予測ミス！ 26 HPBP法の消費エネルギーモデル (1/2) • HPBP法の消費エネルギーEHPBP EHPBP = (Eht × Nht) + (Ehpt × Nhpt) + (Elut × Nlut) + (Ebpred ×Nbpred) Eht，Nht ：ヘッドテーブル・アクセスの消費エネルギー，アクセス回数 Ehpt ，Nhpt ：ホットパステーブル・アクセスの消費エネルギー，アクセス回数 Elut ，Nlut：ルックアップテーブル・アクセスの消費エネルギー，アクセス回数 Ebpred，Nbpred ：従来型分岐予測器の消費エネルギー，アクセス回数 Nht，Nbpred：ホットパス以外の実行命令数 Nlut，Nhpt ：ホットパス中の実行命令数 27 消費エネルギーの定性的評価(2/2) • Eht，Ehpt，Elut，Ebpredの比較(テーブルサイズ による比較) – ヘッドテーブル：３２エントリ(1Kbit) – ホットパステーブル：５０エントリ(3Kbit) – ルックアップテーブル：１エントリ(60bit) – 従来型分岐予測器：２KエントリGshare(64Kbit) 従来型分岐予測器のサイズ >> HPBP法のサイズ 消費エネルギー削減率は ホットパス実行の割合に依存 28 評価実験 • 評価対象 – BASE：従来方式、分岐予測器はGshareを使用 – HPBP8,16,32： • ヘッドテーブルエントリ数8,16,32のHPBP法 • ホットパステーブルのエントリ数は50 • ホットパス外命令はGshareを使用 • 評価項目 – 分岐予測ミス率 – 分岐予測器の消費エネルギー • 実験環境 – プロセッサ･シミュレータ：SimpleScalar • プロセッサ構成：８ウェイ・スーパスカラ – ベンチマークプログラム • SPEC2000：整数３個 • 入力：smallinput 29 予測ミス率 予 測 ミ ス 率 (%) 18 16 14 12 10 8 6 4 2 0 BASE HPBP8 HPBP1 6 HPBP3 2 1 64 g zi p 1 64 2 56 1 64 1 1 81 1 81 2 56 A g zi p 6 4 g zi bz i p V G g zi p m m b z c c i p p f f 2 re 2 lg lgr e re f . lg r e lg r e r ef . r g r a r e f .l o g f. s o d d .g r d .l o e . i d i n n ph i c .g r a ur c g ap h e ph i c ic ベンチマークプログラム 30 消費エネルギー削減率 70 HPBP8 HPBP16 HPBP32 消 費 60 エ ネ ル 50 ギ ー 削 40 減 率 30 (%) 20 10 0 1 64 g zi p 1 64 lg r e g zi p d .g r 1 64 lg r e ap h ic g zi p d .l o g 1 64 1 81 1 81 g zi p mc f mc f re f . lgr e r e f gr a . d .i n ph i c l o g ベンチマークプログラム 2 56 r ef . bz i p in 2 56 AV G 2 2 lg r e f. r ed so u .g r a r ce ph i c bz i p 31 考察 • ヘッドテーブル・エントリ数による影響 – エントリ数を多くしてもエネルギー削減効果は上 がらない場合もある(むしろ下がる場合もある) • エントリ数を増やしてもホットパス実行時間が増えない パスの実行時間が全実行時間に占める割合が ○%以下のものは登録しないようにする 32 関連研究 • 分岐予測器の消費エネルギーモデル(再掲) EBPRED = (Edir + Ebtb) × Nbpred • Edir,Ebtbの削減(※) ※参考論文：[Chaver 2003] – 予測が容易な分岐命令に対し、使用するテーブルを制限 – フェイズごとのプロファイル情報から予測が容易な分岐命 令を発見 • 関連研究と提案手法の違い – 予測が容易な分岐命令の発見法 • ホットパスに着目 – ホットパス専用の分岐予測機構を追加 • ホットパス中の分岐命令情報のみ必要なため、テーブルサイズ が小さい • テーブル検索ではなく、FIFO(First In First Out) 33 おわりに • まとめ – ホットパスを利用した分岐予測法の提案・評価 • 予測ミス率は平均約2.2ポイントの増大（性能低下） • 消費エネルギーは最大68%、平均約40%削減 • 今後の課題 – 予測精度の向上 • ホットパステーブルの更新 – プロセッサ全体での消費エネルギーを評価 34 ご清聴ありがとうございました 考察 • HPBP法の問題点 – 先頭アドレスが等しいパスを複数登録できない ABD・・がホットパス表に登録されている場合 ACD・・もHPBP法で予測し、予測が外れる A B C D ACD・・の実行頻度が高いと・・・ 予測ミスが頻発 ホットパス実行モードでの実行時間の短縮 （消費エネルギーの増大） 36 予測ミス率と消費エネルギー削減率 BASE予測ミス率 HPBP32予測ミス率 HPBP32消費エネルギー削減率 18 予 16 測 14 80 消 70 費 60 エ ミ ス 12 率 10 (%) 8 ネ ル ギ ー 削 減 率 (%) 50 40 30 6 20 4 2 0 10 0 164 gzi p 164 1 1 2 A gzi p 164gzi p 64gzi p 181mcf 81mcf 56bzip 256bzip VG 2 lg 2 re l r l lgre r ref.i r e d .gr gred .log ef.grap ef.log gred.i n d n .gra f.sourc ap h h i c p hic e ic ベンチマークプログラム 37 考察 実行時間の長いパス上位10本 良かった例 悪かった例 181mcf ref.in 164gzip lgred.graphic 1本 3本 登録できなかったパスの合計実行時間 が全実行時間に占める割合 4.5% 13.3% 登録できたパスの合計実行時間 が全実行時間に占める割合 61.3% 36.1% 先頭アドレスの重複により 登録できなかったパス 良かった例では登録できなかったパスが少なく また登録できたパスの合計実行時間は全実行時間の多くを占める 38 予測ミス率と消費エネルギー削減率 BASE予測ミス率 HPBP32予測ミス率 HPBP32消費エネルギー削減率 18 予 16 測 14 80 消 70 費 60 エ ミ ス 12 率 10 (%) 8 ネ ル ギ ー 削 減 率 (%) 50 40 30 6 20 4 2 0 10 0 164 gzi p 164 1 1 2 A gzi p 164gzi p 64gzi p 181mcf 81mcf 56bzip 256bzip VG 2 lg 2 re l r l lgre r ref.i r e d .gr gred .log ef.grap ef.log gred.i n d n .gra f.sourc ap h h i c p hic e ic ベンチマークプログラム 39 実行時間の長いパス上位10本 181mcf ref.in 164gzip lgred.graphic NO 登録 1 ○ 10.3% 2 ○ 5.5% 3 割合A NO 登録 10.3% 1 ○ 29.1% 29.1% 15.8% 2 ○ 8.1% 37.3% 3 ○ 8.1% 45.3% 割合B 5.4% 割合A 割合B 4 ○ 5.3% 21.1% 4 5 ○ 5.3% 26.4% 5 ○ 3.5% 48.9% 6 ○ 3.2% 52.0% 7 ○ 2.7% 54.7% 8 ○ 2.5% 57.2% 6 7 4.8% ○ 8 3.9% 30.2% 3.1% 4.5% 9 ○ 3.0% 33.3% 9 ○ 2.1% 59.2% 10 ○ 2.9% 36.1% 10 ○ 2.1% 61.3% 割合A：そのパスの実行時間が全実行時間に占める割合 割合B：登録できたパスの実行時間の合計が全実行時間に占める割合 先頭アドレスの重複により、ホットパステーブルに登録できなかったもの 40 消費エネルギーモデル E1：ホットパスヘッドテーブル E2：ホットパステーブル E3：ルックアップテーブル E0：従来型分岐予測器 E1 phase1 PC Etotal = E1 × ホットパス以外の実行命令数 + E2 × ホットパス中の実行分岐命令数 + E3 × ホットパス中の実行命令数 + E0 × ホットパス以外の実行命令数 検 索 ホットパスヘッド テーブル パ ス の 先 頭 ア ド レ ス ヒットしなかった 場合従来の分岐 予測器を使用 E０ PC phase2 比較 ホットパス テーブル 分岐命令 分岐先 アドレス アドレス E2 順 番 に 取 り ルックアップテーブル 出 す E3 41 ホットパス検出・登録 • ホットパス検出法 – オンライン・プロファイリング • プログラム実行中にホットパスを推定する • ホットパス推定用のエネルギーがかかる • 正しいホットパスを検出できるかわからない – 実行トレースの解析 • プログラムを一度実行し、そのトレース情報から ホットパスを検出する • ホットパスを検出した入力と異なった入力がきたときに ホットパスが誤っている可能性がある 42
© Copyright 2024 ExpyDoc
