d-Splineがより安定した関数であることを示している．
れは，今回の方式が大規模問題に有効である可能性を示している．
今後の課題としては，インストール時ソフトウェア自動チューニングで必要となる行列 サイズ間の補間への提案方式の適用がある．
5 実行時ソフトウェア自動チューニングへの 標本点逐次追加型性能パラメタ推定法の適用 5.1 実行時ソフトウェア自動チューニングの特徴
ユーザが実際に数値計算ライブラリを利用してユーザプログラムを実行する，実行時 フェーズでのソフトウェア自動チューニングの適用について考える．実行時ソフトウェア 自動チューニングでは，より詳細なユーザプログラムに関する情報を用いることができ る．たとえば，プログラム上では変数で与えられている問題のサイズ(一般に行列サイズ) が，ユーザプログラムへの入力等の形により指定され確定する．そのために，インストー ル時ソフトウェア自動チューニングのように，行列サイズを変えながら多くのパタンにつ いて調べる必要はない．しかしながら，実際にユーザプログラムを実行するときの最適化 であるため，ソフトウェア自動チューニングに要する時間はそのままユーザプログラムの 実行時間に反映されてしまう．そのため，ソフトウェア自動チューニングに要する時間を 抑制することは，インストール時自動チューニングに比べて，より重要となる．
図19は図2の実行時ソフトウェア自動チューニングの部分を詳細にした図である．図 19に示したように，ユーザが数値計算ライブラリを呼び出すごとに，毎回ソフトウェア自 動チューニング機構が動き，最適値を決定するまで性能パラメタの探索を行なう．図19 の 4．ユーザプログラムの実行 で示した，実行時ソフトウェア自動チューニングの動 作を以下に述べる．
1. 条件分岐(A)において，すでに最適値が探し出されているかどうかを調べる．
2. もし，最適値がすでに探し出されているのであれば，数値計算ライブラリは通常の 処理を実施するのみである．したがって，左側のライン上の処理を実行する．すな わち， 推定した最適値を用いて数値計算ライブラリを実行 し， その結果をユー ザプログラムに返す ことを実施する．
3. 一方，まだ，最適値が決まっていない場合は，右側のライン上の処理を実行し， 実
!"#$&%'( )*+
&,
)-.0/1 2 3
45687
99 99:<;:<;:<;:<;
=
450>@?
23
10ACB
*+
=&D
)E F
!"#!$&%'G(0H,IJ
*+LK!MNPO,QSR0TUV,WG!X,%
)*+
99 99YZ;
YP;
YZ;
YP;
=S[ \0]
^_S`'a bL>@B
*+
=&D
)!E0F !"#!$&%'G(0H,IJ
=
23
4 5
=dcfeCg
5
h i'jlk
)mnolprqts0uSo jrv
qtw,xy
z{r| }~
P !"#!$&%'(0)
GGS)!
!"#$&%'( )d G
図19 実行時ソフトウェア自動チューニング
行時ソフトウェア自動チューニングの実行(B) を実施する．ここで， 実行時ソ フトウェア自動チューニングの実行(B) 自体は内部にループ構造を持たないこ とに注意．この 実行時ソフトウェア自動チューニングの実行(B) では，標本点 をひとつ選択して追加し，その標本点の値を用いて数値計算ライブラリを実行す る．ユーザプログラムから繰返し呼び出されるたびに， 実行時ソフトウェア自動 チューニングの実行(B) が実行されることにより，最終的に数値計算ライブラリ が最適化される．
1. if ( xopt ) then 2.
xopt
!"#$&%'
()+*,
3. else
4. case ( iter_count ) of 5. 1: xps = xp1 6. 2: xps = xpN
7. 3: xps = (2xp1+xpN)/3) -8. 4: xps = (2xp1+xpN)/3)
-9. 5././././ : xps =xpnew_sp (01234 )
10. end case
11. 5
6879&
xps
+
+
!"#$%'
()+*
,:;:=<)
>?
@
12. A sp = A spB {xps}
A nonsp = A nonspB {xps} 13. if ( iter_countC 4 ) then
14.
@DE;FHGI
JK
d-Spline f
15. d-Spline f
DE
+=9
>?
L:8,M
xpopt
N A
16. if ( (A nonsp = O P ) or (
xopt
Q
pRSTUV ) ) then
W XZY[
\]^
17.
_8`
xopt
9
>?Q
L:8,M
5
6879:=a
18. else
19. if ( not (xpoptinA sp) ) then
20. xpnew_sp= xpopt
W bc
\]
1
^
21. else
22. j = maxj|| f(xpj-1)-2f(xpj)+f(xpj+1) || | (xpjinA nonsp)
23. xpnew_sp= xpj
W bc
\]
2
^
24. end if
25. end if
26. end if
27. end if
de
-;fA
9g&DhE
Uij
kl bc
m nopq+rs=tvu8w+xy{z}|
N~&&
(n = {xp1, xp2, …, xpN} xp1 xp2 … xpN )
m n
spo + +
m n
nonspo &+
pq+rs=tvu w+x&yzv|
&++ (n -n sp)
mp N H+ )o8}+&}
図20 標本点逐次追加型性能パラメタ推定法の実行手順(実行時)
4. ユーザプログラムから呼び出された数値計算ライブラリで性能パラメタ推定を実行 する手順を図20 を用いて説明する．図20中の記号については，基本的な性能パ ラメタ推定手順を説明した図8と同一である．ユーザプログラムから呼び出された 自動的チューニング付数値計算ライブラリにおいて，ユーザから自動チューニング の実施が指定された場合，次のように動作する．
（a）手順4から手順10により，数値計算ライブラリを実行するための性能パラメ タの値を設定する．ここで，iter countはユーザプログラムからこの数値計算 ライブラリが呼び出された回数を示す．ケース1からケース4までは，1回か ら4 回までの呼び出しで，それぞれ初期値となる4つの性能パラメタの値を 設定する．4回目にコスト定義関数d-Splineを構成する4つの初期値が揃う．
ケース5以降は，手順19から手順24の選択基準で選び出した標本点を，性能 パラメタの値として設定する．
（b）手順11にて，性能パラメタの値(標本点)を用いて数値計算ライブラリを実行 し，その計算結果をユーザプログラムに返すとともに，標本点における数値計 算ライブラリの実行時間を計測する．
（c）手順13以降において，4点以上の標本点に対する実行時間が求まっている場 合，以下のように最適値の選択を行なう．
i. 手順14および手順15にて，ここまでに実施したすべての数値計算ライ ブラリの実行時間の実測値を用いて，コスト定義関数d-Splineを計算し，
最小となる最適値を推定する．
ii. 手順16において，終了判定基準では，すべての性能パラメタのとり得る 値を実測した，あるいは，最適値があらかじめ指定した回数p回連続し て判定されている場合は，推定した最適値を数値計算ライブラリの実行時 間を最小とする性能パラメタの値であると決定する．最適値が決定した あとは，この数値計算ライブラリがユーザプログラムから呼び出される ときは，つねにこの最適値が用いられ，以後，実行時自ソフトウェア自動 チューニングは行なわれない．
iii. もし，手順16の条件が満たされないときは，手順19から手順24までの 処理が行なわれる．ここでもあらかじめ決めてある選択基準1，2を用い て，次の標本点xpnewspを決定する．
このときの手順4から手順26までの計算量についてみると，数値計算ライブラリ自体 は，ユーザプログラムの反復計算処理のなかで実行されることであり，特に，新規に必要 になるわけではない．新規に発生するのは，d-Splineの生成時間とxpnewsp の探索時間 であるが，これらは前述したように，数値計算ライブラリに対して無視できるオーバヘッ ドである．このときの実測時間については，5.3.4節に示す．
ここで，d-Splineの生成時間が無視できるのであれば，すべての性能パラメタのとり得
る値を調査すればよいと考えられる．しかし，最悪値に近い値を用いた場合，最良値よ り，はるかに実行時間が大きくなる可能性があり，できるだけ少ない標本点で最適値ある いはその近傍の値を見つけることが有効である．