第 5 章 枝刈り機構のオーバヘッドの削減 41
5.4 実験
5.4 実験 51
52 第5章 枝刈り機構のオーバヘッドの削減 計測結果を図 5.5 と図 5.6 に示す．グラフの横軸はプログラムに与えた個々の入力で あり，BASE に対する SPEC の実行時間の比率が昇順になるよう整列している．また，
両グラフの代表的な入力 A ∼ H における計測結果の詳細を表 5.1 と表 5.2 に示す．
5.4.1 実行時間
図5.5 a と図 5.6 a はBASE の実行時間に対する SPEC の実行時間の比率を示すグラ
フである．ここでは CPU 時間と GC 時間の合計を実行時間とした．SPEC の実行時間 は概ね BASE の60∼70%以下であった．いくつかの入力では BASE の10%以下にな るという大きな改善が得られた．改悪した入力は ks において一つだけあったが，その超 過時間は BASE の 3% だけであった．この結果により，粒度調節により実行時間を安定 的に短縮できることが示された．
5.4.2 max
B， min
Bの適用回数
図5.5 bと図5.6 bは，BASE のmaxB，minB の適用回数に対する，SPECのmaxB， minB の適用回数の比率を示すグラフである．maxB，minB の適用回数は実行時間にほ ぼ比例している．この結果は maxB，minB の関数適用という，細分化された要求駆動に おけるオーバヘッドを安定的に削減できたことが，実行時間の安定的な短縮をもたらした ことを示している．
SPEC で間引いた近似値の個数と，削減された maxB，minB の適用回数を調べると，
近似値を一つ間引くごとに，平均的に，ks では 8 回の maxB の適用を削減でき，pz で は 3 回弱の minB の適用を削減できたことが分かった．このように，近似値の間引きが 関数適用回数の削減に役立ち，結果として実行時間の削減に寄与することが示された．
5.4.3 ks ， pz の適用回数
図 5.5 c と図 5.6 c は，BASE のks，pz の適用回数に対する，SPEC の ks，pz の適 用回数の比率を示すグラフである．BASE は必要最小限の回数しか ks，pz を呼んでいな いので，SPEC とBASE の差は，間引きにより進めてしまった不要計算の回数である．
ks で，間引きによる不要計算の増大がない場合には，実行時間が 2% 未満と，間引き の効果が高い場合があった．また，多くの場合は不要計算の増大が 5∼15%程度であり，
実行時間は 50% 以下と効果が出ている．また，不要計算が大幅に増大しても実行時間と しては一定の効果があることが示された．ks における不要計算の増大の最大値は 316%
であったが，実行時間の改悪が 3% で済んでいるのは注目に値する．
pz では，多くの入力でSPEC の適用回数が BASEを下回った．その理由は，8 パズル
5.4 実験 53
0.0 0.5 1.0
D C
B A
入力 a. 実行時間の比率
実行時間比(SPEC/BASE)
0.0 0.5 1.0
D C
B A
入力
b. maxB の適用回数の比率
適用回数比(SPEC/BASE)
0.0 1.0 2.0 3.0 4.0
D C
B A
入力
c. ks の適用回数の比率
適用回数比(SPEC/BASE)
図5.5 ks の計測結果
54 第5章 枝刈り機構のオーバヘッドの削減
0.0 0.5 1.0
H G
F E
入力 a. 実行時間の比率
実行時間比(SPEC/BASE)
0.0 0.5 1.0
H G
F E
入力
b. minB の適用回数の比率
適用回数比(SPEC/BASE)
0.0 0.5 1.0
H G
F E
入力 c. pzの適用回数の比率
適用回数比(SPEC/BASE)
図5.6 pz の計測結果