予測 / 投機成功率の評価

発の問題は生じにくい．

本提案手法は，ループ区間の実行終了ごとに，次のループ区間において投機対 象とするパスを決定する．しかし，ごく小数のループイタレーションしか実行さ れないループ区間においては，パスの実行割合に偏りが生じないうちにループ区 間の実行が終了する可能性が高い．そこで，本研究では，パスの動的変更を行う 際の閾値を設定し，実行されたループイタレーション数が閾値を超えたときのみ，

投機対象パスの変更を行う方法を提案する．パスプロファイラによって，ループ の実行回数 (すなわちループイタレーション数)をカウントし，実行回数が閾値未 満であれば動的パス変更は行わない．ループ実行回数はループ区間ごとにリセッ トせず，ループ実行回数の合計が閾値以上となった場合，次のループ区間の実行 開始時に動的パス変更を行い，ループ実行回数をリセットする．

本動的パス変更手法をハードウェアシステム上に実現する場合，パスプロファイ ラの実装が必要となる．パスプロファイラは，ループイタレーションごとに実行 されたパスをカウントし，ループ区間の実行終了後に実行割合上位2本のパスを 出力する．本研究では，増保らが提案したハードウェア・パスプロファイラ[40]を 採用する．このハードウェア・パスプロファイラでは，プログラムカウンタ (PC) と条件分岐命令の実行履歴を基に，実行頻度の高いループおよびパスを見つける ものである．各ループに存在するパスごとに実行回数を記録することができるた め，本提案手法に必要な機能を備えている．

り早く投機の成否が判定できるようにしている．そのため，予測失敗となった場 合でも，もう一方のパスで投機成功となれば，プログラム実行性能の向上は十分 に期待できる．

5.5.1 評価方法

評価には，動的パス変更手法を模擬するシミュレータを用いる．シミュレータへ の入力として，SPEC CINT2000ベンチマークプログラムの実行トレースログを 与える (4.2節で説明)．実行トレースログには，実行されたパスが時系列に記録さ れており，投機対象としたパスと，実行トレースが一致するかをループイタレー ションごとに調べることにより，予測成功回数および投機成功回数を求める．ま た，パス予測機構には，2レベルパス予測器 (3.1.3節で説明) を使用した．動的 パス変更を行った場合でも，パス履歴レジスタおよびパスパターン履歴テーブル の値はリセットしない．

評価対象ループとして，SPEC CINT2000ベンチマークプログラムに含まれる ループのうち，実行頻度が高く，以下の条件を満たすものを選択した．

• 3本以上のパスを含む．

• 最内ループである (ループの内側にさらにループを含んでいない)．

• 関数呼び出しを含まない．

提案手法の性能比較には，静的な2パス限定投機方式による予測/投機成功率と，

理想的な動的パス変更を行ったときの予測/投機成功率の結果を用いる．理想的な 動的パス変更の実現のため，一度すべてのループ区間に対して実行割合上位2本 のパスを求めておき，その2本のパスをそれぞれのループ区間において投機対象 とするシミュレータを作成した．

5.5.2 評価結果

図5.4に，予測成功率および投機成功率の評価結果を示す．また，見やすさと紙 面上のスペースの関係から，付録Bに各プログラムごとの評価結果を記載してい る．図中の方式名の意味は以下のとおりである．

0 10 20 30 40 50 60 70 80 90 100

static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal static dynamic optimal

164.gzip 164.gzip 175.vpr-place

181.mcf 186.crafty 186.crafty 197.parser 254.gap 255.vortex 300.twolf 300.twolf

Accuracy [%]

prediction speculation

longest_match() scan_tree()

get_bb_from_scratch() primal_bea_mpp()

NextMove()

InitialZeroMasks() table_pointer()

ProdFFEVecFFE() Grp_DeleteRgn()

new_dbox_a() add_penal()

図 5.4: 予測/投機成功率の評価

• static: 静的な2パス限定投機方式による評価結果である．プログラム全体を

通して，投機対象パスは2本のみである．

• dynamic: 本研究における提案手法である，動的パス変更方式による評価結

果である．ループ区間における実行割合上位2本のパスを，次のループ区間 における投機対象パスとする．

• optimal: 性能比較のための理想的な動的パス変更方式である．ループ区間ご

との実行割合上位2本のパスをあらかじめ取得し，それらを当該ループ区間 における投機対象パスとする．

動的パス変更を行うためのループイタレーション数の閾値は100とした．パス履 歴レジスタ長は1〜16ビットとし，パスパターン履歴テーブルのカウンタ長は1〜 8ビットとした．図には，パラメータの取り得る値のうち，最も性能の良いものを 載せた．

6つのループにおいて，提案手法である動的パス変更方式が，従来の静的な2パ ス限定投機方式の性能を上回った．186.craftyの関数InitialZeroMasks()のループ では，予測成功率が従来に比べ33%向上した．また，理想的な動的パス変更方式 では，投機成功率が最大で100%を達成した．これは，動的に変更した投機対象パ スのうちどちらかが，各ループイタレーションにおいて必ず実行されたことを意 味している．

いくつかのループにおいて，予測成功率と投機成功率の間に大きな差が現れて いる．この原因として，パス予測器による予測がうまく働かないループである可 能性が考えられる．2レベルパス予測機構では，過去のパスの実行履歴に基づき学 習を行い，次のパスの予測を行う．したがって，パスの出現パターンに規則性が 無い場合には予測が有効に働かない可能性が高くなる．

2パス限定投機方式では，2本のパスが投機対象となるため，1度目の予測が失 敗した場合でも，もう一方のパスの投機が成功する可能性がある．予測成功率に対 して投機成功率が高いループにおいては，この2度目の投機が多く成功しているこ とになる．動的パス変更方式では，実行割合が高くなったパスを投機対象とするた め，従来方式に比べて予測成功率が低下したループにおいても，投機成功率が向上 しているケースが存在している．しかしながら，164.gzipの関数longest match()， および，300.twolfの関数new dbox a()においては，投機成功率が向上していない．

この原因として，連続したループ区間において実行割合の高いパスが頻繁に変わ り，直前のループ区間に基づく動的なパス変更では挙動の変化に対応できていな いことが考えられる．理想的な動的パス変更を行った場合には性能向上を達成で きているため，ループ区間の実行中であっても挙動の変化に追従した動的なパス 変更を実現することで，これらのループに対する投機成功率の向上が可能である と考えられる．