第 5 章 投機対象パスの動的変更
ケース 1 ケース 2 ケース 3 プログラム名 種類数
5.3 動的な投機対象パスの変更
本研究では，パスの本数が多いループにおいてパスの実行割合の変化が生じて いることから，プログラム実行中に動的に投機対象パスを変更する手法について 検討を行う．本節では，プログラムの実行トレース情報に基づく理想的な動的パ ス変更を行った場合の性能見積もりを行い，動的なパスの変更によりどの程度2パ ス限定投機方式の性能を向上できるかを明らかにする．
5.3.1 理想的な動的パス変更を行った場合の性能見積もり
5.2節では，SPEC CINT2000ベンチマークプログラムにおいて，動的なパス変更
が有効に働くと考えられるループについて検討を行った．文献[38][46]では，これ らのループに対して，理想的な動的パス変更を行った場合の性能見積もりを行った．
図5.1に，プログラムを理想的に動的に変更したときの性能見積もり方法を示 す．図では，プログラム実行の全体を通したパスの実行割合順に，パスA，パス
B，パスCとしている．3本のパスが存在する場合，投機対象とすることのできる パスの組み合わせは，(A, B)，(A, C)，(B, C)の3パターンである．本論文におけ る性能見積もりは，以下の手順で行う．
1. パスに含まれる命令数に基づき，パスの実行サイクル数を概算する．
2. 並列実行した場合の同期待ちサイクル数，および，投機失敗時のペナルティ となるサイクル数について，パスの組み合わせパターンそれぞれについて概 算する．
3. プログラムをSimpleScalar上で実行し，パスの実行トレースログを取得する．
4. 求めたサイクル数，および，実行トレースログを2レベルパス予測機構を実 現するシミュレータに入力し，並列実行時のサイクル数をループ区間ごとに 取得する．
図5.1の例では，パスの組み合わせは3パターン存在するため，4.のシミュレータ による実行を3回行うこととなる．
すべてのパスの組み合わせについてシミュレーションを行った後，すべてのルー プ区間について最小である実行サイクル数を求める．図5.1では，最小の実行サイ クル数となるパスの組み合わせに丸印をつけている．この最小実行サイクル数を 合計することで，理想的な動的パス変更を行った場合の実行サイクル数 (Topt) を 見積もることができる．また，パスAとパスBの組み合わせによって得られた実 行サイクル数 (Tstatic) は，従来の静的な2パス限定投機方式の実行サイクル数の 見積もりとなる．TstaticとToptの比によって，理想的な動的パス変更手法の性能向 上比を計算する．
5.3.2 性能見積もり評価
性能見積もりに用いた実行サイクル数は，以下のルールを定め計算した．
• 1命令の実行には1サイクルかかる．
• 投機スレッドの起動には2サイクルかかる．
• 投機スレッド間でのレジスタ通信には1サイクルかかる．
(A, B) a1 a2 a3 a4 a5 an
(A, C) b1 b2 b3 b4 b5 bn
(B, C) c1 c2 c3 c4 c5 cn
TAB (=Tstatic)
TAC TBC
c5 cn
Topt
a1 a2 b3 b4
. . .
. . .
. . .
. . .
optimal execution
図 5.1: 理想的な動的パス変更を行った場合の性能見積もり方法
• 投機失敗によりペナルティとなるサイクル数は，投機判定命令 (assert命令) がパスの先頭命令から何命令分離れているかによって計算する．複数の投機 判定命令が存在する場合，その平均値とする．
• 投機失敗時の回復処理には1サイクルかかる．
これらのパラメータは，3章で述べたPALSのパラメータ設定に基づいている．
見積もり評価には，SPEC CINT2000ベンチマークプログラムより，3本以上の 実行パスを含むループを持つ関数を選択した．プログラムのコンパイルには，PISA 命令セットをサポートしたGCCベースのクロスコンパイラを使用し，最適化オプ ションは−O3とした．
図5.2に，プロセッサを4台としたときの性能見積もり結果を示す．図では，従来 の静的な2パス限定投機方式による実行に対する，理想的な動的パス変更方式の性能 向上比を示している．関数try swap()，関数table pointer()，関数Grp DeleteRgn()， および，関数sortIt()では，約1.3倍から約1.8倍の性能向上を達成することがで きた．これらのループでは，ループ区間における実行割合上位2本のパスが，プ ログラム全体の実行を通した実行割合上位2本のパスと一致していないループ区 間が多く，その割合は50%から80%であった．したがって，ループ区間ごとに求 めた並列実行サイクル数が，従来の静的な2パス限定投機方式の並列実行サイク ル数より小さくなることが多くなり，性能向上を達成することができたものと考 えられる．
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本のパ スのうちのどちらかのパスの投機が成功する確率が高くなり，動的パス変更によ る性能向上の余地が少なかったものと考えられる．