細粒度のプログラム実行挙動解析

2パス限定投機方式は，ループ中の2本のパスが実行割合の大半を占めるという 性質を利用した手法である．一方，プログラム全体の実行では実行割合の低いパ スであっても，頻繁に実行されるループにおいてはプログラム全体における実行 割合が高くなる．さらに，プログラム全体を通して実行割合が低い場合でも，プ ログラム実行のあるフェーズにおいて頻繁に実行されるのであれば，当該パスを 予測の対象としたときに予測が成功する可能性が高くなる．逆に言えば，従来の 2パス限定投機方式において投機対象としていないパスが頻繁に実行されている 間は，同方式による予測は必ず成功しないということになる．そこで，本節では，

SPEC CINT2000ベンチマークプログラム中の，頻繁に実行されるループにおけ

るパスの実行割合の変動に着目する．

本研究では，プログラムのあるフェーズを解析する単位として，ループ実行が開 始されてから終了するまでの区間 (以下，ループ区間と呼ぶ)について，パスの実 行割合の変動を観察する．図4.1にループ区間の定義を示す．図中には，loop Aお

よびloop Bの2種類のループが存在する．ループはプログラムの実行挙動の遷移に

伴い，異なるイタレーション数となる場合がある．ループ区間は図中のloop-period であり，ループが実行されるたびに異なる区間として区別する．

図4.2，図4.3に，SPEC CINT2000ベンチマークプログラムのループにおける，

パスの実行割合が変化する様子を示す．図4.2は，プログラム197.parserの関

0 20 40 60 80 100

0 200000 400000 600000 800000 1e+06 1.2e+06 1.4e+06

execution ratio [%]

the number of loop iterations path A ratio path B ratio path C ratio path D ratio

図 4.2: 関数table pointer()のループ区間ごとのパス実行割合

表 4.1: プログラム全体の実行を通したパスの実行割合 関数名 path A path B path C path D table pointer() 49.7% 24.1% 20.2% 6.0%

Grp DeleteRgn() 67.9% 22.0% 10.1%

-数table pointer()に存在するループの様子を示しており，図4.3は，プログラム

255.vortexの関数Grp DeleteRgn()に存在するループの様子を示している．X軸 はループの実行イタレーション数であり，Y軸はパスの実行割合である．プログラ ムをパスプロファイラ上で実行し，ループ区間ごとにパスの実行割合を求めてい る．図では，プログラム全体の実行を通したパスの実行割合の順にしたがい，そ れぞれのパスに名前を付けている．実行割合1位のパスを‘path A’とし，2位を

‘path B’，以降，C，Dと続く．グラフでは，ループ区間の実行ごとに実行割合を

プロットしているため，各ループ区間におけるループイタレーション数の違いが X軸のプロット点の間隔として表れる．また，表4.1に対象としたループのプログ ラム全体を通したパスの実行割合を示す．

図4.2では，プログラム実行直後からパスAが多くのループ区間において実行 割合が第1位となっている．しかしながら，ループ区間において第2位のパスは全

0 20 40 60 80 100

0 200000 400000 600000 800000 1e+06

execution ratio [%]

the number of loop iterations path A ratio

path B ratio path C ratio

図 4.3: 関数Grp DeleteRgn()のループ区間ごとのパス実行割合

体での実行割合第2位のパスBではなく，第3位のパスCであることが多い．ま た，100,000イタレーション付近では，パスCが第1位となっているループ区間も 存在している．900,000イタレーション付近においては，パスBとパスCの実行割 合がともに高くなり，2本のパスの実行割合の合計は90%程度にまで達している．

その後，またパスAの実行割合が高くなり，第1位のパスとなっている．

図4.3では，プログラム実行直後からパスAの実行割合が非常に高く60%から

90%程度実行されている．一方，ループ区間において第2位のパスはパスCであ

り，パスBは実行されていない．ループの実行が進み，600,000イタレーション付 近では，急激にパスBの実行割合が上昇し，90%に達している．逆に，パスAの 実行割合は急激に変化し，実行割合は0%にまで下がっている．その後も，ある程 度ループの実行が進むにつれ，この急激なパス実行割合の変化が起こっている．

図4.2，図4.3から，プログラム全体の実行を通したパスの実行割合の順位は，多

くのループ区間におけるパスの実行割合と一致していないことが明らかになった．

特に，今回観察を行ったループにおいては，従来の2パス限定投機方式において 投機対象としている2本のパス (図におけるパスA，パスB) の組み合わせが，そ のままループ区間における実行割合上位2本のパスとして現れているループ区間 はごくわずかだった．したがって，従来方式における投機対象としていた#1パス

および#2パス以外のパスを予測の対象とすることは，予測成功率を向上させるに あたって非常に有望であると言える．