現実的な動的パス変更手法の提案

1 1.2 1.4 1.6 1.8 2 try_swap()

price_out_impl() primal_bea_mpp() table_pointer() DiffVecFFEVecFFE() Grp_DeleteRgn() sortIt()

speed-up ratio

図 5.2: 性能見積もり結果

関数price out impl()，関数primal bea mpp()，および，関数DiffVecFFEVecFFE() では性能向上比は約1.05倍から約1.1倍にとどまった．これらのループでは，ルー プ区間での実行割合上位2本のパスと，プログラム全体の実行を通した実行割合上 位2本のパスが一致していないループ区間は50%から70%程度存在していた．し かしながら，ループ区間での実行割合上位2本のパスのうちどちらかが，プログ ラム全体での実行割合上位2本のパスのどちらかと一致していることが多かった．

このため，従来の静的な2パス限定投機方式であっても，投機対象とする2本のパ スのうちのどちらかのパスの投機が成功する確率が高くなり，動的パス変更によ る性能向上の余地が少なかったものと考えられる．

 に再度着目する．ループ区間ごとに挙動の解析を行ったプログラムでは，連続し たループ区間において実行割合の高いパスが同一であることが多い．そして，実 行割合の高いパスが入れ替わった場合には，続くループ区間においても順位は入 れ替わったままであることが多い．

このプログラムの特徴から，本研究では直前のループ区間におけるパスの実行 割合に基づいた，動的パス変更手法を提案する．ループ区間の実行ごとにパスの 実行割合を求め，実行割合上位2本のパスを次のループ区間における投機対象パ スとする方法である．本提案手法により，プログラムの実行挙動の変化に追随し た投機的並列実行を実現することができる．また，ループ区間とループ区間の間 に行われる逐次実行時に動的パス変更を行うことにより，投機対象パスを変更す る処理にかかるオーバヘッドを隠蔽することができる．

図5.3に，本提案手法の実行例を示す．図において，2つの縦線に囲まれた範囲 はループ区間を表す．図中には，4つのループ区間が存在している．図中上段は，

実際のプログラム実行における，ループ区間ごとの実行割合上位2本となるパス の組み合わせを示している．また，図中中段および下段は，ループ区間における2 本の投機対象パスを示している．中段は本提案手法であり，直前のループ区間に おける実行割合上位2本となるパスの組み合わせを，次のループ区間における投 機対象パスとする．プログラムの実行開始時の投機対象パスには，プログラム全 体の実行を通した実行割合上位2本のパスを選択する(図の場合パスAとパスB)． 下段は2パス限定投機方式における投機対象パスであり，すべてのループ区間に おいてプログラム全体の実行を通した実行割合上位2本のパスを投機対象パスと する．

プログラム実行がループに到達すると，プロセッサコアは投機対象パスの並列 スレッドコードを読み込み，投機的並列実行を開始する．その間，ハードウェア パスプロファイラによって，ループイタレーションごとに実行されたパスをカウ ントする．ループ区間の実行が終了すると，プロセッサは並列動作を終了し，逐 次実行を開始する．そして，パスプロファイラの集計結果から，パスの実行回数 の多い2本のパスを次の投機対象パスとして決定する．実行がループ処理に再度 到達すると，プロセッサは変更後の投機対象パスの並列スレッドコードを用いて，

投機的並列実行を開始する．

図5.3では，実行が進むとともにループ区間における実行割合上位2本のパスの

(A, B) the most two frequent

paths combination of

loop-period (B, C) (B, C)

time

loop-period 1

(C, D)

(A,B) selected two paths

combination for speculative execution (dynamic)

(A,B) (B,C) (B,C)

(A,B) two paths combination

of two-path limited speculation method (static)

(A,B) (A, B) (A, B)

loop-period 2 loop-period 3 loop-period 4

図 5.3: 直前のループ区間におけるパスの実行割合に基づく動的パス変更手法

組み合わせが変化している．ループ区間4において，パスの組み合わせは (C, D) となり，2パス限定投機方式の投機対象パスである(A, B)と異なる．この場合，2 パス限定投機方式でのパスの予測の失敗回数が多くなることが予想され，このルー プ区間4での大幅な性能向上は期待できない．本提案手法では，ループ区間4に

おいて (B, C) を投機対象パスとしており，実行割合の高いCを予測できるため，

予測成功率によっては高い性能向上を期待することができる．

2パス限定投機方式では，1つのループに対して1つの並列スレッドコードを用 意していた．本提案手法の実現にあたっては，ループにおけるパスの全組み合わ せパターンに対応した数の並列スレッドコードが必要となる．並列スレッドコー ドはプログラム実行前にあらかじめ作成し，コード最適化を適用しておくことに より，実行時のオーバヘッドは生じず，投機対象に選択したパスの組み合わせに 最適なコードを実行することができる．動的パス変更時には，メインメモリ上に 読み込んだプログラムのうち，投機対象パスに対応した並列スレッドコードの開 始アドレスを指定して実行する．すべてのパスの組み合わせについて並列スレッ ドコードを作成するため，パスの本数が非常に多い場合には組み合わせ爆発とな る可能性がある．しかし，SPEC CINT2000ベンチマークプログラムにおける最 内ループでは，パスが多いものでも10本程度のループが多いため，組み合わせ爆

発の問題は生じにくい．

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

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

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