プログラムの実行経路の偏りに着目した分岐予測法

全文

(1)社団法人情報処理学会研究報告 IPSJSIGTechnicalReports. 2006-ＡＲＣ－１６８（１） 2006／6／８. プログラムの実行経路の偏りに着目した分岐予測法築地孝典↑井上弘士廿村上和彰廿 ↑九州大学システム情報科学府，福岡県廿九州大学システム情報科学研究院，福岡県 E-mail:Itsuiji。c､cscekyushu-u・acjp,廿{inoue,murakami}。i・kyushu-u､ac.jｐあらまし近年多くの高性能プロセッサは分岐予測器を搭載している．分岐予測ミスが発生した場合には誤った命令列が実行されるため，分岐予測精度がプロセッサの性能および消費エネルギーに与える影響は大きい．より高精度な. 分岐予測の実現を目的として，大規模かつ複雑な分岐予測器も提案されている．しかしながら，その結果分岐予測における消費エネルギーが増大し，プロセッサの全消費エネルギーに悪影響を及ぼすようになってきた．前述したように，分岐予測ミス時には将来無効化される命令が実行されるため，プロセッサの消費エネルギーを増加させる．したがって，高い分岐精度を維持しつつ分岐予測器の低消費エネルギー化を達成することが極めて重要となる．そこで本. 研究では，分岐予測精度の向上と消費エネルギーの低減を目的とし，実行経路の偏りに着目した新しい分岐予測法を. 提案する．プログラム中には実行頻度の高い命令列（ホットパス）が存在し，ホットパス中の分岐命令は高確率で決まった方向に分岐する．また，少数のホットパス実行時間が全実行時間の大部分を占める．提案する分岐予測法では，ホットパス中の分岐命令と分岐先を小容量のメモリに保持し，ホットパス実行中はそのメモリを参照することで分岐. 予測を行う．従来のGshare分岐予測器と比較した結果，提案手法の採用により分岐予測ミス率は約２２ポイント増加したが，分岐予測器の消費エネルギーを約40％削減することができた．キーワード分岐予測，低消費エネルギー. ACasefbrHot-Path-basedBranchPrediction. KosukeTSUIJI↑,KojilNOUE↑↑,andKazuakiMURAKAMI廿 ↑GraduateSchooloflnfbrmationScienceandElectricalEngineering，KyushuUniversity，６－１KasugaFkoen， Kasuga，mkuoka，816-8580Japan. 廿GraduateSchooloflnfbrmationScienceandElectricalEngineering，KyushuUniversity，６－１ Kasugakoen，Kasuga，mkuoka，816-8580Japan. E-mail:↑tsuiji。c・cscekyushu-u・ac・jp,↑↑{inoue,murakami}。i・kyushu-u・acjp AbstractModernhighperfbrmanceprocessorsemploybranchpredictors、Theaccuracyofbranchpredictionin-. fluencestheprocessorperfOrmancebecausetheprocessorexecuteswronginstructionswhenamis-predictionoccurs Tbimproveaccuracyofbranchprediction，largescaleandcomplexbranchpredictorshavebeenproposedHow-. ever,theenergyofbranchpredictorshasbeenincreasingAsmentionedabove,whenamis-predictionoccurs,total. chipenergyisincreasedduetｏｔheexecutionofinvalidinstructionsTherefbre,achievinghighaccuracyofbranch predictionandreducingtheenergyconsumptionofthebranchpredictorareveryimportant、Ｗｅｐｒｏｐｏｓｅａｎｅｗ. ｍｅｔｈｏｄｔｏｓｏｌｖｅｔｈｅｉssues、Ｉｔｉｓｗｅｌｌｋｎｏｗｎｔｈａｔｔｈｅｒｅｉｓａｓｍａｌｌnumberofinstructionpathsexecutedfrequently inprogramexecutions・Inthehotpath，branchinstructionstendtobeoutputthesameexecutionresults,Ｌｅ、the samebranchdirectionandthesametargetaddressMoreover,theexecutiontimeofsomehotpathshaveamajority. ofthetotalexecutiontimeAmethodofbranchpredictionweproposepredictsbyaccessingtosmallmemorythat havebranchinstructionaddressandbranchtargetaddressfbrhotpaths・WecomparethismethodwithGshare. predictor，Asaresult，itisobservedthatalthoughthemis-predictionrateincreasesby22points，ｗｅｃａnreduce theenergyconsumptionby40％・ＫｅｙｗｏｒｄｓＢｒanchPrediction，ＬｏｗＰｏｗｅｒ. ｜. ’. ｜『・■■。■｜.

(2) には，式(1)におけるEdjr，E6t6，または，N6pl-edを削減す. 1．まえがき. れば良い．. プロセッサ性能向上手法のひとつに命令パイプラインがある．. 分岐方向予測器とＢＴＢはキャッシュ・メモリと類似した構成. 時間並列性を用いて複数命令を同時実行することでプロセッサ. をとる．そのため，これらへのアクセスにおいて消費されるエ. 性能を向上できる．更なる動作周波数の向上を目的として，高. ネルギーは，キャッシュ・メモリと同様，そのサイズに比例す. 性能プロセッサのパイプライン段数は年々増加傾向にある．一. る[３１したがって，分岐予測器の消費エネルギーを削減するに. 般に，フロントエンド・パイプライン段数の増加は分岐予測ミ. は，分岐方向予測テーブルならびにＢＴＢの容量を小さくすれ. ス・ペナルティを大きくする．そのため，このような高性能プ. ば良い(つまり，ＥｄｊｒとEbtbを削減)．しかしながら，この方. ロセッサでは分岐予測精度の向上が極めて重要となる．. 法では分岐予測精度が低下するといった問題が発生する．そこ. 分岐予測精度を高めるためには，複雑かつ大規模な分岐予測. 器を搭載する必要がある．例えば，分岐予測に使用するテーブ. でChaverらは，分岐方向予測器やＢＴＢのサイズを動的に変. 更する方式を提案している[１１. ルサイズの増加や，トーナメント方式によるハイブリッド分岐. 分岐方向予測精度を高めるため，トーナメント方式に基づく. 方向予測器の採用などが挙げられる．しかしながら，その結果，. ハイブリッド分岐方向予測器が提案されている[5Ⅱ7）この場. 分岐予測における消費エネルギーが増大するといった問題が生. 合，例えばアルゴリズムの異なる２種類の分岐方向予測器を用. じる．例えば，分岐予測器の消費エネルギーはプロセッサ全体. いて分岐方向予測結果を出力する．そして，過去の分岐予測履. の10%以上になるという報告もある[１１したがって，今後よ. 歴等に基づき(信頼カウンタを用いる等)，何れの分岐方向予測. り高性能かつ低消費エネノレギーなプロセッサを実現するために. 結果を用いるか決定する．この場合，常に複数の分岐予測器が. は，高精度かつ低消費エネノレギーな分岐予測器が必要不可欠と. 活性化されるため多くのエネルギーを消費する．そこで，プログラム実行の振舞いに基づき，必要となる分岐予測器の能力を. なる．. そこで本研究では，プログラム実行経路の偏りに着目した新. 調整する．具体的には，分岐予測が容易な場合には従来と同様. しい分岐予測器を提案する．またベンチマーク・プログラムを. に１つの分岐予測器のみを活性化する．分岐の容易性に関して. 用いた定量的評価を行い，その有効性を議論する．多くのプロ. はプログラム実行におけるフェーズの推移を利用している．. グラム実行においては，高頻度で実行される命令列（ホットパ. 通常のスーパスカラ・プロセッサでは同時に複数命令をフェッ. スと呼ぶ)が存在する．例えば，最も頻繁に実行される上位２０. チするため，命令キャッシュへのアクセスはライン単位で行わ. 個のホットパスは，プログラム全実行の約７６％を占める場合も. れる．例えば，１命令が３２ビット，キャッシュライン・サイズが. ある．各ホットパスには多くの分岐命令が存在し，これらの各. 32バイトの場合，１個のキャッシュラインには８命令(32バイ. 分岐命令は高確率で同じ振る舞いをする．提案手法はこの特徴. ト/4バイト）が格納されており，プロセッサは最大で８命令を. を利用する．具体的には，ホットパス中の各分岐命令のアドレ. 同時フェッチ可能である多くの場合，ある分岐命令から次分岐. スならびに分岐先アドレスを小容量メモリに格納する．ホット. 命令の実行までの間に，１０個以上の命令が存在する．これは，. パス実行中にはこの小容量メモリを参照することで分岐予測を. フェッチ対象キャッシュ・ライン内に分岐命令が存在しない場. 行う．. 合がある事を意味する．そこでParikhらは，PPD(Prediction. 以下，第２節では従来の分岐予測器の低消費エネルギー化技. ProbeDetector)を用いて分岐以外の命令フェッチにおける不. 術について説明する．次に，第３節では提案手法の概要と実装. 用な分岐予測を回避(つまりUV6Predを削減)する方法を提案. 方法について述べ，第４節で定量的評価を行う．最後に第５節. した[4｝通常，分岐予測は命令フェッチ時に実施されるため，. でまとめる．. Nbpredの値は命令フェッチ回数と等しくなる(つまり，全ての命令に対して分岐予測を実施する)．これに対し，ＰＰＤを用い. ２．関連研究. た方法では，キャッシュライン内に分岐命令が存在しない場合を. 本節では，これまでに提案された分岐予測器の低消費エネル. 検出して分岐予測を中止する．この方式により，分岐予測器の. ギー化技術に関して説明する．一般に，動的分岐予測を行う. 消費エネルギーを４０％から６０％削減することに成功している．. ためには，分岐成立(Tnken)か不成立(Not-Eken)かを決定. ３．実行経路の偏りに着目した分岐予測法の提案. するための分岐方向予測器と，分岐先アドレスを得るための. ３．１ホツトパス. ＢＴＢ(BranchI泡rgetBuflCr)が必要となる．そして，これ. 本研究で提案する分岐予測法では，プログラム実行における. らは多くの場合ＳＲＡＭによって実装される．分岐予測器で消. ホットパスに着目する．ここで，. 費されるエネルギー(EBPRED)は以下の式で近似できる． EBpRED＝(Edjr＋E6tb)xjVbpred. 分岐命令アドレスー分岐先アドレス＞０. （１）. ここで，ＥｄｊｒならびにEbt6は，それぞれ，分岐方向予測器な. となる分岐命令を後方分岐命令と呼ぶ．バスとは，ある後方. らびにＢＴＢでのアクセス当たりの平均消費エネルギーである．. 分岐(Ｂｉ)の分岐先命令(Bi-tQmet)を先頭とし，次に実行され. また，Ｎ６ｐｒｅｄはプログラム実行において発生する総分岐予測. る後方分岐命令(町)を終端とする静的な命令列である．また，. 回数を表す．分岐予測器の低消費エネルギー化を実現するため. ホットパスとは，高頻度に実行されるパスを示す．なお，本稿. －２－.

(3) ホットパス実行時間が全実行時間に占める割合刑. ００００００００００００９８７６５４３２１. １. ホットバステーブル《ス. ■. 分岐命令アドレス. 分岐先アドレス. Ａ終端. Ｃ先頭. Ｃ終端. Ｅ先頭. Ｅ終端. Ａ先頭. …鐘歳鞠鰯'蛾聯:!！;:::;:竈。ペンチマークプログラム. 図２動作原理. 図１ホットパス実行時間が全実行時間に占める割合. では，プログラムの全実行時間に占める割合が最も多い上位Ｘ. 個(ｘは自然数)のパスをホットパスと見なす．多くのプログラムにはホットパスが存在することが知られている[61．幾つかのＳＰＥＣベンチマーク・プログラムの実行において，ホットパス. 実行が全実行時間に占める割合を図１に示す．なお，実験環境の詳細は第４．１節で説明する．図１より，上位１０本のパスに着目した場合は平均で約６０％，上位２０本のパスに着目した場合は平均で約７６％の実行時間がホットパス実行によることが分かる．. 静的なエントリ登録の場合，プログラム実行の振舞いが入力. データに強く依存するアプリケーションには対応できない、これに対し，動的なエントリ登録の場合はホットパス推定機構が. 必要となる[21[6｝３．３内部構成本節ではＨＰＢＰ予測器の詳細を説明する．図３にＨＰＢＰ予測器の内部構成を示す．ＰＣはプログラムカウンタである．. ＨＰＢＰ予測器は以下のハードウェアで構成される．・ヘッドテーブル：各ホットパスに対応する「ホットパス. テーブル」への参照アドレスを格納するテーブル．各エントリ. ３．２ホットパス分岐予測法. 各ホットパスには多くの分岐命令が存在し，これらの各分岐. 命令は高確率で同じ振る舞いをする．この特長を利用した高精度かつ低消費エネノレギーな分岐予測法としてホットパス分岐. 予測(HPBP:Hot-Path-b懇edBranchPrediction)法を提案する．ここでは，説明を簡単にするため，分岐予測の対象とするホットパスは１本と想定する．複数本のホットパスに対する提案方式の実装方法は次節で説明する．本手法では，あるホット. パス中の各分岐命令に関し,「分岐命令アドレス」と「分岐先アドレス」を小容量メモリに保存する．このメモリを「ホットバス・テーブル」と呼ぶ．そして，ホットパス実行中にはホットパス・テーブルを参照することで分岐予測を行う．図２にその. 概略を示す．左図は実行フローを表す．Ａ～Ｆは基本ブロック. であり，ＡＣＥがホットパスであるとする．したがって，基本ブロックＡ，Ｃ，Ｅ，Ａ，ＯＥ，Ａ・・と連続して実行される可能. は「ホットパスの先頭アドレス」と「ホットパス・テーブルへのポインタ」で構成される．. ・ホットパステーブル：ホットパス中の分岐命令アドレス. と分岐先アドレスを登録するテーブル．各エントリは「分岐命令アドレス」と「その分岐先アドレス」で構成される．本テーブルの読み出しにおいては，先頭エントリから順次行われるためアドレス入力は必要としない．また，本テーブルへのアクセスは前述したヘッドテーブルのポインタを用いて行う．よって，. ヘッドテーブル・エントリ数と同じ数のホットパステーブルが必要となる．. ・ルックアップテーブル：ホットパス・テーブルから読み. 出した分岐命令アドレスならびに分岐先アドレスを格納するレジスタ．ホットパス実行中は本レジスタに格納された値に基づき分岐予測を実施する．３．４動作. 性が高い．よって本手法では，Ａの終端の分岐命令はＣの先頭に，Ｃの終端の分岐命令はＥの先頭に分岐すると予測する．本方式では，ホットパス・テーブルの各エントリに対し，ホッ. トパス中の各分岐命令実行結果（分岐命令アドレスと分岐先アドレス）を設定する必要がある．そして，設定方法としては以下が考えられる．. ・静的なエントリ登録：事前にプロファイル情報を採取し，ホットパス・テーブルに格納すべき内容を決定する．. ・動的なエントリ登録：プログラム実行中にホットパス検. 出と分岐命令抽出を行い，ホットパス・テーブルに格納すべき内容を決定する．. 本節では，ＨＰＢＰ法の動作を説明する．ＨＰＢＰ分岐予測器. では，ホットパスに含まれる分岐命令のみが予測対象となる．. そのため，ホットパス以外の分岐命令実行に関しては分岐予測を実施できない．そこで，ＨＰＢＰ予測器とは別に従来型分岐予測器を搭載する．つまり，ホットパス実行中はＨＰＢＰ予測器を. 使用し，それ以外では従来型の分岐予測器を使用する．ＨＰＢＰ法に基づく分岐予測器は以下２つの動作モードを有する．・通常実行モード：従来の分岐予測器のみを用いて分岐予測を実施．ｏホットパス実行モード：ホットパス・テーブルに格納された分岐予測結果に基づき分岐予測を実施．. －３－.

(4) ミニEi]=芸簔二睾票二言i=彗烹E蕊. Ｆ涌匠素7屏二Wii国. 消費エネルギー削減率. 醜噸噸魍躯繩噸. ﾍｯﾄﾞテーブル. 100％. ルックアップテーブル. 読み出し. 牢獺Ｉ. 脇脇脇２１. ﾋｯﾄしなかった増合従来型分岐予測器を使用. 勺. －－７. ／ﾜ. 〆／▽. ＝〆▽. ／▽. 一忽Ｆ. ＝〆々〆. ／幻｢. ７=三. ＩＩﾛロ. 0％１０％２０％３０％４０％５０％６０冊７０％８０％９脇100％ﾎｯﾄパスの実行時間が全実行時間に占める割合. 図３内部構成と動作. 図４低消費エネルギー削減効果の定性的評価. また，ＨPBF分岐予測法では以下のように動作する．なお，. 初期状態は通常実行モード(つまり，ホットパス以外のコードを実行)とする．（１）通常の分岐予測と同様にＰＣを用いて従来型分岐予測. 器にアクセスする．また，これと並列に，現ＰＣを用いてヘッ. ドテーブル内の対応するエントリを検索する．（２）もし，上記１にてヘッドテーブル内に対応するエントリが存在する場合，これはホットパス実行の開始を意味する．そこで，ホットパス実行モードに状態を遷移する．下記４へ. （３）もし，上記１にてヘッドテーブル内に対応するエントリが存在しない場合は上記１を繰り返す．. （４）ヘッドテーブルのエントリを読み出し，対応するホットパス・テーブルにアクセスする．そして，第１エントリの値. を読み出し，分岐命令アドレスならびに分岐先アドレスをルックアップ・テーブルに格納する．. （５）分岐予測時には,｢現ＰＣの値」と「ルックアップ･テーブルに格納された分岐命令アドレス」を比較する．一致していれば分岐成立と予測して分岐先アドレスをＰＣに設定する．ま. た，ホットパス・テーブルより次エントリを読み出し，ルック. ここで，２ＫエントリのGshare分岐予測器とＨＰＢＰ法を比. 較する．ＨＰＢＰ法に関しては，ヘッドテーブルは３２エントリ，ホットパス・テーブルは５０エントリ，通常モード時に使用する分岐予測器は２ＫエントリのGshare分岐予測器と仮定する．なお，これらの構成は第４節で実施する定量的評価と同じ値である．以下，メモリアクセスの消費エネルギーはアクセスする. メモリサイズにほぼ比例する[3]と仮定し，消費エネルギーを活性化メモリ容量で近似する．. ＨＰＢＰ分岐予測器では，通常実行モードで動作する場合に. は，従来型Gshare分岐予測器における消費エネルギー，ならびに，ヘッドテーブルアクセスによる消費エネルギーが発生す. る．一方，ホットパス実行モードで動作している場合，活性化. されるメモリ容量(テーブルサイズ)は従来型Gshare分岐予測器のそれと比較して約２％程度である．したがって，提案手法の消費エネルギーは，通常実行モードでの分岐予測回数に大き. く依存する．つまり，ホットパス実行モードでの実行割合が大きくなるほど，消費エネルギー削減効果が高くなる．この関係を図４に示す．. アップ・テーブルに保存する．不一致の場合は本ステップを繰. ４．評価. り返す．. ４．１実験方法. （６）ホットパス実行モードにおいて，分岐予測ミスが発生. する，または，ホットパス・テーブルの全エントリを分岐予測に使用した後には，通常モードへと状態を遷移して上記１へ制御を移す．. 第３節で述べたＨＰＢＰ法をマイクロプロセッサ・シミュレー. タであるSimpleScalar[8]に実装し，分岐予測ミス率ならびに消費エネルギー削減率を評価する．プロセッサの構成情報を表１にまとめる．ベンチマークプロ. ３．５定性的評価. ＨＰＢＰ法の消費エネルギーはEhpbpは以下の式で求めることができる．. グラムはSPEC2000smallinput[91を用いる．評価対象モデルは以下４つである．. ・ＢＡＳＥ：Gshare分岐予測器. Ehpbp＝(Ejit×Ｍｔ)＋(Ehp`ｘＭｐｔ）＋(Ｅｌｕｔｘ１ＶＭ＋EBpRED. ●ＨＰＢＰ８,ＨＰＢＰ１６,ＨＰＢＰ３２：５０エントリのホットパ. ステーブルと８/16/32エントリのヘッドテーブルを持つＨＰＢＰ. （２）. 。Ｅ'８t:ヘッドテーブル･アクセス当りの平均消費エネルギー. ・Ehpt：ホットパス・テーブル・アクセス当りの平均消費エネルギー. ・Ｅｊｕｔ：ルックアップ・テーブル・アクセス当りの平均消費エネルギー. ・EBPRED：式(1)で示した従来分岐予測器での消費エネルギー. 分岐予測器．通常実行モードはＢＡＳＥと同じＧshare分岐予測器を使用一. また，本評価ではホットパステーブルの活用による予測ミス率ならびに消費エネルギー削減率の向上効果を明らかすることが目的である．そこで，ホットパス検出ならびにホットパステーブルヘの登録はプログラム実行前に完了していると仮定する．このホットパス事前検出においては，評価実行時と同一入. －４－.

(5) 表１プロセッサ設定０００００７６５４３. （cc：clockcycle(ｓ. 命令発行方式. エネルギー削減率均. ｌアウト・オブ・オーダ. 分岐予測器. ２レベル（Csharc,２Ｋエントリ）. ＴｙｐｅＢＴＢサイＢＴＢサイズ. ５１２エントリ,４ウエイ. ＲＡＳ. ３２. 命令発行幅. ４命令/cｃ４命令/cｃ. 命令デコード幅ＲＵＵサイズ. １２８エントリ. IFＱサイズ LSQサイズ. ８エントリ. ６４エントリ. 2０. キャッシュ・メモリ. Ｌ２共有キャッシュレイテンシＬ１キャノンＬ１キャッシュ. ２ｃｃ. Ｌ２キャノンＬ２キャッシュ. １０ｃｃ. 土、垣土顧憧. ２５０ＣＣ. メモリバンド幅. メモリポート数. ００. Ｌ１命令キャッシュ. 64ＫＢ（32Ｂ/エントリ２ウエイ，１０２４エントリ） 64ＫＢ（32Ｂ/エントリ，２ウエイ，１０２４エントリ） 1ＭＢ（64Ｂ/エントリ，４ウエイ，４０９６エントリ）. １. Ｌ１データキャッシュ. 狗鐙戯鞠鰯'蛾'聯:1$::::ｌｉｌＩＬｏペンチマークプログラム. 図６消費エネルギー削減率. ８Ｂ２. ４．２．２消費エネルギー削減率. ＢＡＳＥモデルに対する消費エネルギー削減率を図６に示す．. く. 予測三一ス率均. １１１１１. ８６４２０８６４２０. ヘッドテープルのエントリ数が８，１６，３２それぞれにおいて，全ベンチマークでの平均消費エネルギー削減率は，３３％，４４％， 49％であった．消費エネルギー削減率が第３．５節で示した定性. 的評価を下回った原因として，予測ミス率の増加によって総実行命令数が増加し，それにより分岐予測回数が増加したことが挙げられる．また，前節で説明したように，先頭アドレスが等しいパスを複数登録できないため，ホットパス実行モードでの実行時間が短くなったことも原因である．４．３考察. 鞄&:1重蕊馬:蝿蝋聯翰.～. 実行頻度の高いパスの先頭アドレスが等しいものが多い場合. ペンチマークプログラム. と少ない場合の二通りで，どのようなパスがホットパスとして. テーブルに登録できたかを表２に示す．表は実行時間が長いパ. 図５予測ミス率. スを順に２０本示している．登録の欄に○が付いているものは. テーブルに登録でき，ＨＰＢＰ法に利用できたパスであり，○が. カデータを用いる．. 付いていないものは先頭アドレスの重複のよりテーブルに登録. ４．２実験結果. できず，ＨＰＢＰ法に利用できなかったパスである．割合Ａは. ４．２．１予測ミス率. 予測ミス率の結果を図５に示す．予測ミス率はGshare予測器のみの場合と比べ，ヘッドテーブルのエントリ数が８の場合. に平均約２０ポイントの増加（性能低下）となり，エントリ数が１６の場合に平均約２５ポイントの増加，エントリ数が３２の. 場合に平均約２．５ポイントの増加となった．予測ミス率が増加した原因として以下のことが考えられる．. 今回実装した手法では，通常実行モードにおいてヘッドテー. プルを検索することでホットパス実行中か否かを判定する．ヘッ. ドテーブルには，複数ホットパスの先頭アドレスが同一の場合，その中から高々１個しか登録できない．実際，先頭アドレスが同一であり，かつ，異なるパスを形成している場合には正しい. 分岐予測を行うことができない(つまり，異なるパスでの分岐情報を用いて予測することになる）よって，実行頻度の高いパスの中に先頭アドレスが等しいパスが複数あった場合，分岐予. そのパスの実行時間が全実行時間に占める割合を，割合Ｂは登録できたパスの実行時間の合計が全実行時間に占める割合を表. す．164gziplgredgraphicは，先頭アドレスの重複により登録できなかったパスが多く存在し，また，登録できたパス上位８本の実行時間は，全実行時間の３８９％しか占めていない．その. ため，gziplgredgraphicは予測ミス率，消費エネルギー削減率の両面であまりよい結果が出ていない－方mcfrefinは，登録できなかったパスが少なく，また，登録できたパス上位８. 本の実行時間は全実行時間の59.2％を占めている．その結果， mcfrefinは予測ミス率，消費エネルギーの両方でよい結果が. 出ている．したがって，実行頻度の高いパスのうち，先頭アドレスが等しいものが少なく，また少ないパスで多くの実行時間. を占める，つまり実行経路の偏りが大きいものがＨＰＢＰ法で予測するのに向いていると考えられる．. 測ミスが頻発することになり，結果予測ミス率が増加したと考える．. －５－.

(6) 表２実行頻度の高いパス l64gzipIgred・graphic. した．しかし，ホットパスを実行中でも，過去のグローバルな. l81mcfrefin. 分岐履歴によってＨＰＢＰ予測器とGshare予測器のどちらを使. 膳罐登録. 割合Ａ. 割合Ｂ. 登録. 割合Ａ. 割合Ｂ. １. ○. 10.3％. 10.3％. １. ○. 29.1％. 29.1％. うか選択する手法や，実行頻度の高いパスに同じ先頭アドレス. ２. ○. 5.5％. 15.8％. ２. ○. 8.1％. 37.3％. を持つパスが複数ある場合の対策として，同じ先頭アドレスを. ３. ○. 8.1％. 45.3％. 複数登録できるようにし，どのホットパスを予測に使用するか. Ｎｏ．. 5.4％. ３. Ｎｏ．. 4.5％. ４. ○. 5.3％. 21.1％. ４. ５. ○. 5.3％. 26.4％. ５. ○. 3.5％. 48.9％. ６. ○. 3.2％. 52.0％. ７. ○. 2.7％. 54.7％. 本論文を執筆するにあたり，多大なるご協力を頂いた九州大. ８. ○. 2.5％. 57.2％. 学大学院システム情報科学府の小宮礼子氏に感謝します．ま. 4.8％. ６. ７. ○. 3.9％. 30.2％. ３１％. ８. を分岐履歴によって選択する手法も考えられる．謝辞. ９. ○. 3.0％. 33.3％. ９. ○. 2.1％. 59.2％. 1０. ○. 2.9％. 36.1％. 1０. ○. 2.1％. 61.3％. 1１. ○. 2.7％. 38.9％. 1１. ○. 1.9％. 632％. テムLSI研究センターならびに安浦・村上・松永・井上研究室. 1２. ○. 1.8％. 650％. の皆様に感謝します．なお，本研究は一部，科学研究費補助金. 2.6％. 1２. 1３. ○. 2.5％. 41.3％. 1.8％. 1３. 1４. 2.2％. 1４. ○. 1.8％. 66.8％. 1５. 2.2％. 1５. ○. 1.8％. 68.6％. 1６. ２２％. 1６. ○. 1.7％. 703％. 1７. 2.2％. 1７. ○. 1.7％. 72.0％. 1８. ○. 2０. ２０％. 43.3％. 1.9％. 1９. ○. 1.7％. 45.1％. た，本研究を進めるにあたり，共にご議論頂いた九州大学シス. (学術創成研究費：課題番号14Ｇs0218,若手研究Ａ：課題番号 17680005）による．. 文献. （l1DanielChaver，LuisPinuel，ManuelPrieto，FYancisco Tirado,MichaelC､Huang，“BranchPredictionOnDemand： anEnergy-EflicientSolution''Pages：３９０－３９５international. 16％. 1８ 1９. ○. 1.3％. 73.3％. 2０. ○. 1.2％. 74.4％. symposiumonLowpowerelectronicsanddesigncitation 2003,Seoul，KoreaAugust２５－２７，２００３. ｛2］EDuestenwaldandVBala,``SoftwareProfilingfbrHotPath Prediction：ＬｅｓｓｉｓＭｏｒｅ,，，Prooofthe9thInternational ConferenceonArchitecturalSupportfbrProgrammingLan-. 5．おわりに. guagesandOperatingSystems（ASPLOS2000),pp202‐. ５．１まとめ. ２１１，Novenber2000. 本稿では実行経路の偏りに着目した分岐予測法を提案し，予. （３１Ｍ.BKamble,andKGhose,"AnalyticalEnergyDissipation. は高頻度で実行される命令列に含まれる分岐命令とその分岐先. ModelsFbrLowPowerCaches，，，Procofl9981ntematilnal SymposiumonLowPowcrElectronicsandDesign,ｐｐ,143１４８，ＡｕｇｕＳｔｌｇ９８. をメモリに格納しておくことで分岐予測器の低消費エネルギー. ｌ４１Ｄ・Parikh，Ｋ・Skadron,YZhang,Ｍ・bardella,andMstan，. 測ミス率と消費エネルギーの観点から評価を行った．提案手法. 化を狙いとした．評価の結果，予測ミス率は平均約２．２ポイン. ト増加したが，消費エネルギーは平均約40％削減することがで. “PoserlssueRelatedtoBranchPrediction''’１nInternaP. tionalSymposiumonHigh-PerfbrmanceComputerArchitecture,pages233-244，Cambridge，ＭＡ，Fbvuruary2002. l5IASeznecandPMichaud,“De-aliasedHybridBranchPre‐. きた．. dictors，，，TbchnicalReportNo3618，InstitutNationalde. ５．２今後の課題５．２．１オンライン・プロファイリングによるホットパス推定. 今回は事前に実行するプログラムのトレース情報を取り，ホットパスを検出した．そのため完全に正しいホットパスを利用することができた．ホットパスを動的に検出する手法を用いた場合のＨＰＢＰ法の予測ミス率，消費エネルギーはこれからの研究課題である．５．２．２Ｇshare予測器の学習. 今回ＨＰＢＰ予測器で予測した場合には，Ｇshare予測器の分. 岐予測テーブルを更新しなかった．これを更新するようにする. ことで，予測ミス率の改善が期待できる．その結果，更新にかかるエネルギーは増加するが，予測ミスによるオーバーヘッドは減少するので，消費エネルギーの改善効果も見込める．５．２．３ホットパス情報の更新. 今回は事前に検出したホットパス情報を，プログラム実行前にテーブルに登録し，またその情報を更新することはなかった．. しかし，ＨＰＢＰ法で予測したもので頻繁に予測ミスを起こすものがある場合に，その予測を変更する手法も考えられる．５．２．４グローバルな分岐履歴の利用今回はホットパス実行中は必ずＨＰＢＰ予測器によって予測. －６－. RechercheenlnfOrmatiqueetenAutomatique(INRIA)，. Fbbruaryl999. ［６１江島和仁,吉松則文,曽我武史,村上和彰,“動的システム最適化技術SysteMorphの性能評価，，，情報処理学会研究報告， 2006-ARC-166,ｐｐ､19-24,2006年１月. ［7］斉藤史子,北村健志,山名早人，“ハイブリッド分岐方向予測機構の性能比較，'，情処研報(ARC),VOL2002,Ｎ0112,ｐｐ8994, 2002年１１月. （８）SimpleScalarLLC， http://wwwsimplescalarcom／（９１StandardPerfbrmanceEvaluationCorporation， http://www・specbench・org／.

(7)