性能パラメタ推定法に関する研究

(1)

数値計算ライブラリを対象としたソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究

田中輝雄

電気通信大学大学院情報システム学研究科博士 ( 工学 ) の学位申請論文

2007 年 3 月

(2)

数値計算ライブラリを対象としたソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究

博士論文審査委員会

主査弓場敏嗣教授

委員伊藤秀一教授

委員曽和将容教授

委員吉永努助教授

委員本多弘樹助教授

(3)

著作権所有者

田中輝雄

2007 年

(4)

An Incremental Performance Parameter Estimation Method Applied to Software Automated Performance Tuning

for Numerical Libraries Teruo Tanaka

Abstract

Software automated performance tuning is an optimization of performance parameters suitable for a certain computational environment in ordinary numerical libraries.

One of the important issues for the automated performance tuning is reduction of execution time required for tuning of performance parameters. In consideration of the issue, this dissertation proposes a new method to estimate optimal performance parameters by incrementing suitable sampling points referring to computational results of a cost definition function. The new method is named Incremental Performance Parameter Estimation method. The method is effectuated by a newly defined cost definition function d-Spline, which has high flexibility to adapt given data and can be easily calculated. The characteristics of the Incremental Performance Parameter Estimation method are:

1) estimates the optimal performance parameters using dynamically incremented sampling points,

2) achieves high accuracy with a relatively small estimation time, otherwise, find the parameter values near optimal performance,

3) makes an efficient combination withd-Spline as well as the complexity of solving d-Spline can be neglected,

4) does not require the user’s knowledge and is applicable to every mathematical library.

(5)

There are two phases to execute automated performance tuning: (a) at install-time and (b) at run-time. For evaluation, the new method is applied to eigenvalue analysis programs at install-time. The results of the evaluation showed that the method achieves to reduce execution time by 49.0% at the best and by 19.0% in average compared with conventional methods. The new method is also evaluated by sparse matrix-vector multiplication at run-time. The results of the evaluation showed that the execution time required for the optimization can be neglected.

(6)

数値計算ライブラリを対象としたソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究田中輝雄

要旨

大規模行列計算等で利用されている数値計算ライブラリを，使用する計算機環境およびユーザが解きたい問題に対して，実行性能が最大になるように自動的に最適化する「ソフトウェア自動チューニング」の研究が進められている．ソフトウェア自動チューニングでは，数値計算ライブラリのループ構造のアンローリング段数などの性能チューニング項目をパラメタ化する．この性能パラメタのとり得る値から複数の値を標本点として選択し，

標本点ごとに数値計算ライブラリの実行時間を測定する．標本点ごとの実行時間(=コスト)をコスト定義関数であらわす．このコスト定義関数を用いて，数値計算ライブラリの実行時間を最小にする性能パラメタの最適値を推定する．この数値計算ライブラリの最適化は，複数の性能パラメタに対して，かつ，多くの問題規模(行列サイズ)に対して，実行する必要があり，性能パラメタ推定の時間短縮が大きな課題となっている．

本論文では，コスト定義関数による推定に必要とする最低限の数の標本点から始めて，

新たに標本点を選択し追加しながらコスト定義関数を順次更新し，最適な性能パラメタの値を推定する「標本点逐次追加型性能パラメタ推定法」を提案する．この新しい性能パラメタ推定法では，標本点を追加するか否かの終了判定条件に，何回連続して同じ性能パラメタ値を選択したかという同一判定連続回数を用いる．また，コスト定義関数として，標本値を追加したときの実測データ間の形状の変化に柔軟に追随し，かつ計算量の少ない d-Splineを適用する．

標本点逐次追加型性能パラメタ推定法は，次のような特徴を持つ．

(7)

a) 事前に与えられた固定数の標本点をもとに推定を行なう従来の方式に対して，必要に応じて使用する標本点の数を調整する柔軟性を実現した．

b) 高い正答率（最適な性能パラメタ値を選択する割合）を実現した．もし正しい最適値を選択できなかった場合も，最適値に近い実行時間の性能パラメタ値を選択する．

c) コスト定義関数d-Splineは，提案する性能パラメタ推定法との整合性が良く，数値計算ライブラリ自体の実行時間に比べて，無視できるほど少ない演算量で実行できる．

d) ユーザからの事前情報は一切使用しないので，ユーザが解きたいどのような問題にも対応することが可能である．また，対象とする数値計算ライブラリに対しても制限はない．

これらの特徴から，提案した性能パラメタ推定法はソフトウェア自動チューニングにおいて実用性の高い方式といえる．

ソフトウェア自動チューニングによる最適化のフェーズとして，次の2つがある．

a) インストール時ソフトウェア自動チューニング：数値計算ライブラリを計算機にインストールする時

b) 実行時ソフトウェア自動チューニング：問題を解くために，数値計算ライブラリを用いてアプリケーションプログラムを実行する時

提案手法の有効性を検証するために，それぞれのフェーズに対して，実証実験を行なった．

インストール時ソフトウェア自動チューニングでは，ユーザプログラムが対象とする行列サイズが特定できないため，多くの行列サイズに対して数値計算ライブラリを実行させる必要がある．ここでは，密行列演算の固有値計算ライブラリを用いた．4種の計算機環境ならびに4種のベンチマークに対して，それぞれ16種の行列サイズで実験を行なった．その結果，全体での平均では，終了判定基準を4回連続同一性能パラメタ値の選択とした場合，性能パラメタのとり得る値全数に対する使用した標本点の割合である利用率

(8)

68.3%で，正答率87.3%を実現した．ランダムに標本点を選択した場合は，同じ正答率を得るためには確率的に利用率が87.3%となるので，利用率に関し19.0ポイントの効果があったと言える．同様に，最大では51.0%の利用率で100%の正答率を得ており，49.0 ポイントの効果を実現した．

実行時ソフトウェア自動チューニングでは，実行時間にほとんど影響を与えないように，性能パラメタ推定時間を抑える必要がある．ここでは，疎行列の行列積を取り上げた．疎行列の非零要素の位置は実行時にしか決まらないため，自動チューニングは実行時にしか行なうことができない．今回の実験では，疎行列の行列積の計算時間の1%以下で性能パラメタ推定処理を実行することができ，自動チューニングに要する時間を無視できることを示した．このとき，インストール時の場合と同様に，ランダムに標本点を選択した場合に比べて，同じ標本点の利用率で正答率を平均で55.0%から75.9%に20.9ポイントの向上を実現した．

今後は，ソフトウェア自動チューニングのフレームワークの中に，提案した性能パラメタ推定法を組み込み実用化をはかる．それとともに，事前に全数取得することが難しい行列サイズ間の性能パラメタ最適値の補間，複数性能パラメタの同時推定など，提案した性能パラメタ推定法の改善，適用拡大に取り組んでいく．

(9)

図目次

1 ソフトウェア自動チューニングにおけるユーザプログラム，計算機環境と

数値計算ライブラリの関係 . . . 3

2 数値計算ライブラリを用いたユーザプログラムの実行手順とソフトウェア自動チューニングの実行タイミング . . . 11

3 性能パラメタ最適値導出手法による関連研究の分類 . . . 15

4 近似関数f と実測データの集合yの関係 . . . 20

5 行列E，Dの形状 . . . 21

6 QR分解時の行列Z, bの構造 . . . 22

7 標本点追加時の行列Rの構造 . . . 25

8 標本点逐次追加型性能パラメタ推定法の実行手順 . . . 28

9 コスト定義関数d-Splineを用いた近似例 . . . 30

10 標本点逐次追加型性能パラメタ推定法の適用例 . . . 33

11 インストール時ソフトウェア自動チューニング . . . 38

12 標本点逐次追加型性能パラメタ推定法の実行手順(インストール時) . . . . 39

13 実験計算機環境と自動チューニングの対象(インストール時) . . . 41

14 数値計算ライブラリごとの実験結果(インストール時) . . . 45

15 計算機環境ごとの実験結果(インストール時) . . . 47

16 選択を誤ったときの最適値に対する実行時間増加の割合 . . . 48

17 他コスト定義関数との比較 . . . 49

18 他コスト定義関数との比較 - 平均 - . . . 50

19 実行時ソフトウェア自動チューニング . . . 55

20 標本点逐次追加型性能パラメタ推定法の実行手順(実行時) . . . 56

21 CRS形式の構造 . . . 59

22 BCRS形式の構造 . . . 60

23 実験計算機環境と自動チューニングの対象(実行時) . . . 62

(13)

24 疎行列データの非零データ位置パタン(例) . . . 65

25 ブロック化時の非零データ率(例) . . . 66

26 計算機環境ごとの実験結果(実行時) . . . 68

27 標本点逐次追加型性能パラメタ推定法による標本点選択・追加のふるまい 72 28 評価尺度に対する計算機環境ごとのふるまい . . . 74

29 疎行列データの非零データ位置パタン . . . 99

30 ブロック化時の非零データ率 . . . 101

31 実験結果 SR11k . . . 103

32 実験結果 SR8k . . . 105

33 実験結果 Ppower . . . 107

34 実験結果 PCn1 . . . 109

(14)

表目次

1 最適化の観点とそれに対応する性能パラメタ群(例) . . . 5

2 実験結果インストール時自動チューニング . . . 43

3 実験結果インストール時自動チューニング -数値計算ライブラリの平均値- 44 4 3次スプライン補間との比較(選択を誤ったときの最適値に対する実行時間増加の割合) . . . 51

5 実験に用いた疎行列データ一覧 . . . 64

6 すべての性能パラメタがとり得る値を用いたときの実験結果. . . 70

7 ブロック化の効果(CRS=1としたときの倍率) . . . 71

8 ブロック化の効果(CRS=1としたときの倍率) - 母数としてCRSが最適であったケースを除く - . . . 71

9 d-Splineの生成時間 . . . 75

(15)

1 緒言

1.1 本研究の背景と目的

気象，量子力学などの自然現象の解明，大規模LSI，新薬などの製品開発において，大規模数値シミュレーションはなくてはならない存在である[52][63]．航空機を開発するための風洞実験を数値シミュレーションで実現する数値風洞(NWT，Numerical Wind Tunnel)[101]，量子の世界を計算機上で再現するCP-PACS[96]，地球規模の気象計算を行なう地球シミュレータ[95]等，数多くのいわゆるスーパコンピュータが開発されている．

そして，それらの計算機上で，さまざまな大規模かつ複雑なモデルの数値シミュレーションが実行されている．また，プロセッサの高速化により，PCサーバでもかなりの大規模数値シミュレーションの実行が可能となり，さらに，PCサーバのクラスタ化やGRIDコンピューティング技術の実用化により，巨大な計算パワーが身近に手に入るようになってきている[14]．

これまでは，数値シミュレーションを実行する技術者，研究者 (以下，ユーザと呼ぶ) は，数値シミュレーションの利用に関してもスペシャリストであった．しかしながら，数値シミュレーションがより大規模かつ複雑なモデルを扱うようになり，それに伴う数値シミュレーション技術も高度に進化してきた．また，多くのユーザが膨大な計算機パワーを手にできるようになってきたことにより，数値シミュレーションに精通していないユーザの利用も広がりだしてきた．数値シミュレーションを実行するユーザは，それぞれ自らの問題をモデル化(方程式化)し解くことが目的であり，それを効率よく解く数値シミュレーション手法についての知識は直接的には必要ない．そのため，数値シミュレーションの実行環境を提供する側が，数値シミュレーションを，より高度に，かつ，より使いやすくする必要がある．

一方，さまざまな分野の数値シミュレーションを効率よく行なうために，多くの数値計算アルゴリズムが開発されている．筆者等はベクトル型スーパコンピュータあるいは高並列計算機向けに数値計算アルゴリズムを開発してきた[48][84][85][86][87][88][89][90][103]．

(16)

これらの数値計算アルゴリズムの研究開発は，アーキテクチャやハードウェア方式を意識しながらもより広く利用できることを目指してきた．

一般に，開発された数値計算アルゴリズムは，数値計算ライブラリの形式でユーザに提供されることが多い[51]．この数値計算ライブラリはある意味で汎用的に開発されており，多くの計算機でそれなりに高速に動作するように設計されている．数値計算ライブラリの開発者は，特定の計算機向けの最適化までは立ち入ることはしていなかった^*1．また，その計算機に特化した数値計算ライブラリであっても，それはその計算機のある標準構成に対する最適化である．その計算機が構成しうるすべてのパタン（CPU数，

CPU性能，メモリ，キャッシュ容量などの組合せ)をカバーしていることを保障しているわけではなく，さらに，あらゆるユーザの解きたいモデル(方程式)に対して，その数値計算ライブラリが最適に設定されているわけではない．

ユーザの視点で考えれば，数値計算ライブラリは汎用的である必要はなく，ユーザが解きたいモデル(方程式)が速く，確実に，安定して実行されればよいだけである．そのために，汎用的な数値計算ライブラリを，ユーザの使用する計算機環境において，

ユーザの解くべきモデル（方程式）に自動的に最適化する，いわゆるソフトウェア自動チューニングの研究開発が進められている[7][10][32][55]．

ソフトウェア自動チューニングは，実用化に向けてワーキンググループあるいはプロジェクトとして，各大学，研究機関で研究開発が進められている．代表的なプロジェクトとして，California大のPHiPAC[5][67]，BeBOP[4]，Sparsity[24][75]，OSKI[65][99]，Illinois 大のAutopilot[71][72]，Maryland大のActive Harmony[15][80]，MITのFFTW[13]， Tennessee大のATLAS[2][100]，SANS[74]，SALSA[73]，東大のI-LIB[22][31]，電通大のFIBER[11][33][35]などがある．

ソフトウェア自動チューニングの目的は，ユーザプログラムの実行時間を短縮することにある^*2．そのために，汎用に作られた数値計算ライブラリをユーザが使用する計算機環

*1計算機ベンダやソフトウェアベンダでも，特定の計算機向けにターゲットを絞りながらも，できるかぎり汎用性を持たせた数値計算ライブラリを開発している．

*2ソフトウェア自動チューニングは，性能だけでなく，メモリ容量の削減，ユーザの求める精度の保証など，最適化の目的としていろいろな視点が考えられる[38]．しかしながら，本論文では，まず性能向上と

(17)

!#"$%#&('*)&+

/

132 &(4356 $%#,56

789#&*:<; 789&*:<;

78

=3>

/

#0?@

A#BDC3EF3GHJI

KMLNPORQ

S#TU

HWV3X

図1 ソフトウェア自動チューニングにおけるユーザプログラム，計算機環境と数値計算ライブラリの関係

境で実行するユーザプログラムに合わせ，数値計算ライブラリの中に準備されている複数の性能パラメタ群を自動的に最適化する．数値計算ライブラリを対象とするソフトウェア自動チューニングにおけるユーザプログラムと計算機環境との関係を図1に示す^*3．ここで，計算機環境とは，ユーザプログラムを実行する計算機のハードウェア構成とその上で実行されるコンパイラ等のソフトウェア群全体を示す^*4．計算機としては，スーパコンピュータ，高並列計算機，ベクトル計算機，ＰＣサーバ，クラスタなどのさまざまなアーキテクチャおよびハードウェア構成[16][18][19][54][69]があり，また，近年では，既存の計算機資源を有効利用するために生じる非均質なクラスタ環境や，GRIDコンピューティング環境も実用化されつつある[14]．

いう視点に特化し，ユーザプログラムの実行時間を短縮することを目的に議論を進める．それ以外の目的については，今後の課題で言及する．

*3ソフトウェア自動チューニングを効率よく行なうためには，性能チューニングに関するユーザ情報を用いることが有効である．しかしながら，本論文では，提案する性能パラメタ推定法の汎用性を示すために，

ユーザ情報は一切用いないこととする．

*4場合によっては，マルチユーザ環境などの運用形態も考慮する必要がある．しかしながら，本論文では計算機あるいは計算機の一部を占有して用いると仮定する．

(18)

これらの計算機環境上で実行する数値計算ライブラリの性能チューニング対象について述べる．数値計算ライブラリの高速化のために，さまざまなプログラミング技法が研究開発されている．そのプログラミング技法をユーザプログラムそれぞれに最適化できるように，数値計算ライブラリの中に性能パラメタの形で埋め込んでおく．

たとえば，計算機の中のパイプライン演算器のハードウェア構成（パイプラインの段数，種類，数等）は性能に大きく影響する．このパイプライン演算器群を有効に用いるために，プログラミング技法として，ループアンローリングが用いられる[53]．ループアンローリングの深さを決めるループアンローリング段数は，ユーザプログラムの演算内容ならびに配列サイズに依存する．このループアンローリング段数を性能パラメタとする．多重パイプライン演算器を限りなく効率よく動作させることを目的に開発されたベクトル型スーパコンピュータでは，このループアンローリングの効果は大きい[17][42]．現在の計算機はさまざまなハードウェア構成の多重パイプライン演算器を装備しており，それぞれ効果を最大に発揮するループアンローリング段数は異なる．

また，パイプライン演算器の高速化により，演算性能とメモリとパイプライン演算器間のアクセス速度との乖離が広がり，現在の計算機は階層型キャッシュ構造をとることが一般的である．この多階層キャッシュを有効に利用するために，行列データを小行列(この行列単位をブロックと呼ぶ)に分け，そのブロックの単位で演算を実行する手法，いわゆるキャッシュブロッキングが行なわれている[61]．この場合，小行列の大きさ(ブロックサイズ)が性能パラメタとなる．これは，SMP ^*5 型並列計算機のように，メモリを共有するタイプの並列計算機では特に効果が大きい．今後，ひとつのLSI上に複数のCPUコアを持つマルチコア・アーキテクチャが主流になりつつあり[29][78]，この傾向はさらに強まると考える．

分散記憶型並列計算機環境においては，データの分割の形態，計算機ノード^*6間のデータ通信の性能（スループット，レイテンシなど）および計算機ノード間の同期処理(順序制御処理)の手法が全体の性能に大きく影響する[94]．データの分割としては，取り扱う

*5SMP：Symmetric Multi-Processor

*6分散記憶型並列計算機あるいはクラスタを構成するメモリ，演算器およびI/Oからなる計算機単位を計算機ノードと呼ぶことにする．

(19)

表1 最適化の観点とそれに対応する性能パラメタ群(例)

最適化の対象対応する性能パラメタ群

・演算器の構成・ループアンローリング段数（パイプラインの段数，種類，数等）

・階層型キャッシュ構造，サイズ・ブロックサイズ

・ループアンローリング段数

・計算機ノード間のデータ分割・データ分割の形態

・計算機ノード間データ転送・転送回数，ブロックサイズレイテンシ，スループット

・計算機ノード間同期処理・同期処理手順

行列データを行あるいは列方向に分割するか，あるいは，矩形に分割するかは，計算機ノード間で必要となるデータ転送パタンおよびデータ転送量，あるいは，データ転送量と各計算機ノードで行なわれる演算処理のバランスで決まる．また，通信性能特性により，

計算機ノード間で送受信するデータをまとめる単位が変わってくる．同期処理についても１対１の計算機ノード間で行なう場合と全体で一括して同期を取る場合なども並列計算機のアーキテクチャおよびハードウェア構成方式に合わせる必要がある．それぞれ，データ分割する際のデータの形状，計算機ノード間データ転送時のデータブロックサイズ，同期処理の手法が性能パラメタとなる．さまざまなアーキテクチャおよびハードウェア構成方式において，この性能パラメタの特性は大きく異なる[66][102]．

数値計算ライブラリに関連する性能パラメタを最適化することにより，ユーザの使用する計算機環境において，数値計算ライブラリを用いたユーザプログラムの実行時間を短縮できる．そのために，性能パラメタのとり得る値を探索し，その中から性能パラメタの最適値を選択する必要がある．

性能パラメタのとり得る値は，その最適化の対象を実現するアーキテクチャあるいはハードウェア構成方式に依存する．たとえば，ループアンローリングの段数はパイプライン演算器の深さ(パイプラインの段数)やパイプライン演算器の数に関連する．これらは，

計算機が進化するほど，周波数向上によりパイプライン段数が増え，集積度向上により演

(20)

算器の数が増える．これらに伴い，最適なループアンローリング段数は増える方向になる．また，ブロックサイズにおいても，キャッシュの容量が増加したり，演算性能と演算器とメモリとの間のデータ転送のスループットやレイテンシが大きくなることは，ブロックサイズも大きくなる方向に働く．そのため，性能パラメタの最適値を選択するために探索する性能パラメタのとり得る値の範囲は広がる方向になっている．

もうひとつ，考慮する必要があるのは，ユーザにソフトウェア自動チューニングを意識させるかどうかである．前述したように，数値計算ライブラリの高速化はユーザ視点からすれば二次的な技術である．したがって，ソフトウェア自動チューニングは，できるかぎりユーザから直接操作させなくてすむようにしたい．本論文では，ユーザからの直接操作は仮定しない．つまり，ユーザの持つ知識は利用しない^*7．そうすることにより，

1. ユーザがソフトウェア自動チューニングに関する知識を持たなくても済む，

2. 前提条件をつけないことにより，適用先の計算機環境あるいは数値計算ライブラリに制約がつかない．

そのためには，ソフトウェア自動チューニング自体を，ユーザに影響ないように実行する必要がある．また，性能パラメタの最適値を決定するための処理時間を，可能なかぎり短くする必要がある．

本論文の目的は，ソフトウェア自動チューニングにおける性能パラメタ推定を効率よく行なう方式を提案し，その有効性を提示することにある．ソフトウェア自動チューニングには多くの研究課題がある．それらの課題について2.2節で整理し，その中での性能パラメタ推定の効率化の位置づけを明確にする．

*7ユーザの知識を利用して，さらにソフトウェア自動チューニングの効率および精度を上げることについては，今後の課題として，6.2節で言及する．

本論文でのユーザはいわゆるエンドユーザである．ソフトウェア自動チューニングを利用するユーザには，数値計算ライブラリの開発者もいる．ただし，この開発者は積極的に開発者の持つ知識を駆使して，

数値計算ライブラリを開発する．本論文で提案する新しい性能パラメタ推定法は，開発者としてのユーザが作成した数値計算ライブラリでも用いることができる．

(21)

1.2 コンパイラとの関係

ユーザプログラムの最適化を行なうという点では，従来からコンパイラが主導的役割を持つ．ここではソフトウェア自動チューニングとコンパイラとの関係を考察する．

コンパイラは，ユーザプログラムの制御フロー解析およびデータフロー解析を行なうことにより，動作する計算機環境に合うようにユーザプログラムを最適化する[53]．ここでコンパイラが使えるのは，ユーザプログラムのソースコード上の情報のみである．

ユーザプログラムでは多くの情報が変数の形で記述される．たとえば，問題サイズ (行列サイズ)や反復解法における終了条件としての反復回数などである．これらは，プログラム実行時にユーザから入力情報で与えられる．これらの変数で与えられた情報に対して，個別の最適化はできない．一般に，コンパイラが作成するのはひとつのオブジェクトコードである^*8．

一方，ソフトウェア自動チューニングでは，性能パラメタを用いて複数のパタンのソースコードを準備する．複数のパタンのうち，どのパタンがよいかは，事前に数値計算ライブラリを実行することにより決定する．行列サイズなどのユーザプログラムに関する情報が変数となり不明のときは，できるだけパタンを絞り込んでおいて変数が確定したときに，絞り込んだパタンの中から，あるいは，数値計算ライブラリを再実行することにより，

最適なパタンを選択する．このとき，ソフトウェア自動チューニングで用いた複数パタン自体は，コンパイラにより最適化される．

このように，ソフトウェア自動チューニングはコンパイラで対応が難しいところを補う形で実行される．

さらに，コンパイラにもコンパイラ・ディレクティブという (性能)パラメタがある．

これらは，ユーザが指定することになるが，このコンパイラ・ディレクティブ自体をソフ

*8たとえば，コンパイラでもループアンローリングを行なうオブジェクトコードを生成する[53]．ただし，

ソースコードからわかる範囲(ループ構造内の演算量など)で判断したある意味で汎用の最適化オブジェクトコードである．変数で指定されている行列サイズはわからないままなので，個別のユーザプログラムにとって最適なループアンローリング段数となっている保証はない．

(22)

トウェア自動チューニングの性能パラメタと考え，最適化の対象とすることも考えられる^*9．

1.3 本論文の構成

本論文は7つの章から構成される．

第１章は本章であり，本研究の背景，目的および意義について述べた．また，コンパイラとの関係について考察した．

第2章では，ソフトウェア自動チューニングにおける性能パラメタ推定の位置付けについて述べる．まず，ユーザが数値計算ライブラリを用いるときにソフトウェア自動チューニングを実行するタイミングを示し，それぞれのタイミングでのソフトウェア自動チューニングの役割を示す．次に，ソフトウェア自動チューニングにおける研究課題を整理し，

その中で，本論文で取り上げた性能パラメタ推定法について説明する．さらに，性能パラメタ推定法の研究動向を示し，本研究の位置付けを明確にする．

第3章では，新しい性能パラメタ推定法として，性能パラメタのとり得る値の中から標本点を逐次に選択し追加しながら性能パラメタ推定を行なう，標本点逐次追加型性能パラメタ推定法を提案する．この新しい性能パラメタ推定法の検討方針として2つの着眼点を示す．(a) 複数の標本点ごとの数値計算ライブラリの実行時間をコストとするコスト定義

関数d-Splineを定義し，その導出方法および計算量などの特徴について述べる．(b) 標本

点を逐次追加するための基準として，標本点選択基準と終了判定基準を示す．さらに，標本点逐次追加型性能パラメタ推定法の適用事例を示す．

第4章では，インストール時ソフトウェア自動チューニングへの標本点逐次追加型性能パラメタ推定法の適用について実機を用いた実験を行ない，その結果を考察する．まず，

実験に用いた計算機環境およびソフトウェア自動チューニングの対象となる性能パラメタ

*9ただし，コンパイラ・ディレクティブはコンパイラで解析しきれない情報をユーザに要求している．たとえば，プログラムのソースコード上からはデータの依存関係が不明なときにでも，アルゴリズム上からデータの依存関係はないことが明らかなことを，コンパイラ・ディレクティブにより，ユーザが強制ベクトル化や強制並列化を指定する．このような可否のレベルをソフトウェア自動チューニングで最適化対象とすることは難しい．

(23)

について述べる．計算機環境として，スーパコンピュータならびにPCクラスタを用いる．対象数値計算ライブラリとして，代表的な密行列計算である固有値計算ライブラリの主要ルーチンを用いる．その主要ルーチンでの性能パラメタとして，ループアンローリング段数，キャッシュブロッキングでのブロックサイズを取り上げる．次に，その実験結果をもとにした標本点逐次追加型性能パラメタ推定法についての考察を行なう．また，コスト定義関数として他の関数を用いた場合との比較を行なう．

第5章では，実行時ソフトウェア自動チューニングへの標本点逐次追加型性能パラメタ推定法の適用について述べる．ソフトウェア自動チューニングの対象として，疎行列の行列ベクトル積計算を用いる．疎行列を構成する非零要素の位置は実行時にしか決まらないため，疎行列を対象とする自動チューニングは実行時にしか行なうことができない．ここでは，疎行列の行列ベクトル積計算の性能向上のために，行列構造のブロック化を行ない，そのときのブロックサイズを性能パラメタとする．実用水準の疎行列ベンチマークデータを用いて実測を行ない，提案した性能パラメタ推定法を適用し，その効果を考察する．さらに，性能パラメタ推定法を用いたソフトウェア自動チューニングに要する時間が無視できる範囲であることを実測により確認する．

第6章では，今後取り組むべき課題について整理する．さらに，本論文では扱わなかったユーザ知識の活用についても，今後の課題のひとつとして触れる．

第7章では，本研究の結言として，研究結果についてまとめる．

(24)

2 ソフトウェア自動チューニングにおける性能パラメタ推定の位置付け

2.1 ソフトウェア自動チューニングを実行するタイミング

ユーザが作成したユーザプログラムを実行する計算機環境上で，数値計算ライブラリを用いる手順を図2 に示す．

1. ユーザプログラムを実行する計算機環境に，ソフトウェア自動チューニング機構を組み込んだ数値計算ライブラリをインストールする．

2. ユーザプログラムの中に数値計算ライブラリを呼ぶインタフェースを組み込む．

3. ユーザプログラムをコンパイルし，数値計算ライブラリと結合する．

4. ユーザプログラムを実行する．このとき，数値計算ライブラリはユーザプログラムから繰り返し呼び出される．

この一連の手順の中で，数値計算ライブラリに対して，ソフトウェア自動チューニングを実行するタイミングとして，本研究ではつぎの２つのフェーズに対して検討した．

1. インストール時ソフトウェア自動チューニング −数値計算ライブラリを計算機環境にインストールする時：

ここでは，計算機環境の情報がわかるので，計算機環境に対して数値計算ライブラリが最適になるように，性能パラメタを自動チューニングする．ただし，ユーザプログラムに関する情報はわからない．たとえば，対象とするユーザプログラム上での問題サイズ(行列サイズ)が特定できない．そのため，複数の行列サイズに対する数値計算ライブラリの実行時間の実測結果を用意しておく必要がある．その結果，自動チューニングの実行に1日単位の時間を要するのが現状である[2]．それでもすべての行列サイズを実行することは不可能であり，複数の行列サイズを選択して実測する．選択されなかった行列サイズについては，選択された行列サイズの実行結果を用いて性能パラメタの最適値を推定する．

(25)

!"#%$'&

!(#)*+,

-.

!"#%$./01

!"##$

2345

!(6)*7,98:<;%*>=%?A@9B#CDE<F(#

GB%CDE<FH(%

IKJLMNO

PQ!RS

I

UT#VW

X8YZ[\

98:;#*]=%?^@9B%CDHEF(%

98_`&#45Xab9B%CDHEF(%

JLMNO

PQ!<RScde9f

JL

dg9de

I

dehAibHj9klm98YneZ[\

o p

(%q!,

図2 数値計算ライブラリを用いたユーザプログラムの実行手順とソフトウェア自動チューニングの実行タイミング

なお，インストール時ソフトウェア自動チューニングは，計算機環境が変わらなければ(メモリの増強，CPUの交換，あるいは，関連ソフトウェアの更新など)，数値計算ライブラリのインストール時に１度行なうだけで十分である．それ以降は，

インストールされた結果を用いればよい．

2. 実行時ソフトウェア自動チューニング −数値計算ライブラリを組み込んだユーザプログラムを実行する時：

実行時にしかわからない情報を取り込んで，性能パラメタを自動チューニングする^*10．実行時にしかわからない情報としては，行列サイズ，あるいは，5章で評価

*10ユーザプログラムの実行時にしかわからない情報のうち，ユーザプログラムの実行前に必要な情報が提供されれば，その時点でソフトウェア自動チューニングが可能となる．たとえば，事前に行列サイズが明示されれば，この情報をもとに性能パラメタを最適化することができる．これは，実行起動前ソフトウェア自動チューニングとして，インストール時ソフトウェア自動チューニングおよび実行時ソフトウェア自動チューニングと区別されている[34]．しかしながら，本論文では，後述するように性能パラメタ推定法に

(26)

実験に用いる疎行列データの非零データの位置情報などがある．実行時ソフトウェア自動チューニングでは，数値計算ライブラリがユーザプログラムから呼び出されるたびに，数値計算ライブラリに付随する自動チューニング機構が動作する．したがって，性能パラメタの最適値を推定し決定するまでは，性能パラメタのとり得る値を変えることにより，いろいろなチューニングパタンが実行される．ただ，どのパタンでもユーザプログラムに戻す数値計算ライブラリでの計算結果の値は一致する^*11．この性能パラメタの最適値が決定したあとは，数値計算ライブラリはその最適値をつねに用いることになり，その後，実行時ソフトウェア自動チューニングは実行しない．

2.2 ソフトウェア自動チューニングの研究課題

ソフトウェア自動チューニングは，まだ研究の歴史が浅い分野である [59][60]．主な研究課題を以下に列挙する．

1. 対象とする計算機環境の拡大への対応：

当初のソフトウェア自動チューニングは(特にスーパスカラ型の)シングルプロセサを対象としていた[100]．さらに，SMP型並列計算機，クラスタ，さらには，既存の計算機資源を有効利用するための非均質なクラスタ環境やGRIDコンピューティング環境へと適用対象を広げている．これらにどのように対応するかを考えなくてはならない．

2. 新規の数値計算アルゴリズム開発に伴う性能パラメタの抽出：

ソフトウェア自動チューニングの研究は新規アルゴリズム開発と密接に結びついている．新規アルゴリズムを開発する際に，どのような性能パラメタがそのアルゴ

関する研究である．性能パラメタ推定法の手順からすれば，実行起動前ソフトウェア自動チューニングは，インストール時ソフトウェア自動チューニングと同じと考えられるので，区別はしない．

*11演算順序が異なる可能性があるので厳密には一致しない．演算順序の問題は並列化した場合の逐次プログラムとの差，あるいは，コンパイラにより計算順序が入れ替えられるなどにより起こりうることであり，

本論文では，問題としないことにする．

(27)

リズムを組み込んだライブラリに影響を与えるかを知るための感度解析が必要になる．

3. 性能パラメタの最適値の導出：

ソフトウェア自動チューニング自体の実行は，ユーザからはその実行時間の隠蔽をはかる必要があり，そのため，効率のよい導出方法の開発が必要となる．

4. 推定した最適値の数値計算ライブラリへの組み込み：

推定した最適値をどのように数値計算ライブラリに組み込み，ユーザに提供するかを検討する必要がある．

5. ユーザプログラムの精度，実行時間を保証するための性能パラメタの設定基準 [25][26][27][28][56][57][58]：

ユーザの求める精度あるいは実行時間に対して，実行したソフトウェア自動チューニング機構がどこまで保証できるのか，検討する必要がある．

2.3 性能パラメタ推定の関連研究

本研究では，第 1章で述べたように，ソフトウェア自動チューニングの実用化に向けて，重要な課題である性能パラメタのとり得る値から最適値を選択する性能パラメタの最適値の導出について検討を行なう．性能パラメタの最適値を導出する方法について，

現在の研究状況を整理し，本研究の位置付けを明らかにする．

まず，代表的なソフトウェア自動チューニングについて概観し，それぞれの性能パラメタの最適値を導出する方法を調査する．

1. PHiPAC(Portable, High-Performance, ANSI, C Coding)

PHiPACは，Cで書かれたループレベルを対象としている．評価する性能パラメ

タは，レジスタブロッキング，L1キャッシュ対応ブロッキング，L2キャッシュ対応ブロッキングなどである．

【性能パラメタの最適値の導出】まず，レジスタブロッキングについて全数探索して，そこで選択された最適値を固定して，L1キャッシュ対応ブロッキングにつ

(28)

いて探索，さらに，L2キャッシュ対応ブロッキングについて探索する．各段階では全数探索を実施する．探索の順番により結果が異なる可能性がある．

2. ATLAS(Automatically Tuned Linear Algebra Subprograms)

ATLASは，密行列向けのBLAS関数を対象とし，評価する性能パラメタはループ

アンローリング，ブロッキングおよび数値計算ライブラリ選択などである．

【性能パラメタの最適値の導出】数値計算ライブラリをインストールするときに，

全関数をBLASレベルでその計算機環境に対して最適化する．そのため，１日単位の実行時間を必要とする[2]．

3. I-LIB(A Parallel Automatically Tuned Intelligent Library)

I-LIBは，疎行列ベクトル積のループアンローリング，反復法アルゴリズムの選択，

反復法における前処理アルゴリズムの選択などを行なう．

【性能パラメタの最適値の導出】ループアンローリング段数などにおいて，あらかじめ，1，2，4，8などの値を決め，その中から最適値を探索する．

4. 東大小谷，須田グループ[46]

行列積を対象とし，評価する性能パラメタはループアンローリング(3重ループのすべてのループ)である．

【性能パラメタの最適値の導出】ループアンローリングについては，2重から5 重までのすべての値について実測の対象とする．行列サイズについては事前に標本点を設定し，それらの組合せで実測を行なう．これらの実測値をもとに，実験計画法を用いて行列サイズ方向の特性を調べる．

5. FIBER/ABC-Lib (Framework of Installation, Before Execution-invocation and Run-time optimization Layers/Automatically Blocking and Communication- adjustment Library)

FIBERは，3つのソフトウェア自動チューニングのフェーズ(インストール時，実

行起動前，実行時)で実施するフレームワークを提供する．ABC-LibはFIBERを実現するためのコンポーネントで，ABCLibScriptと呼ぶスクリプト言語を準備しており，ソフトウェア自動チューニング付きライブラリを設計できる環境を提供し

(29)

ている．FIBER/ABC-Libでは，密行列計算を対象とし，評価する性能パラメタは，ループアンローリング，ブロッキング，並列計算機での計算機ノード間の通信プロトコル選択などである．

【性能パラメタの最適値の導出】あらかじめ選択した性能パラメタのとり得る値について，対象とする数値計算ライブラリの実測を行ない，それを多項式近似による推定を実施する．多項式の中でも経験的に5次多項式がよいとしている．

以上のソフトウェア自動チューニングに対して，性能パラメタの導出法の分類を図3のように整理する．

1. すべての性能パラメタがとり得るすべての値を調べつくす全数探索を実施：

すべての性能パラメタがとり得るすべての値を対象に，その値に対する数値計算

! "$#

%&$')($*,+

.-/

'!021

3 45

-/67

8:9

;=<?>@;BA

3

<DCFEFE@CFGHGHCFCFI

7

JHKKL MON?PMQ;SR

3T

R=U

7

JHKKFV

U=>H;SAOW

$')XY +

Z

[\^]

._`

ab[cedf\

ghij 2k$#

lmno!p

qr st > sU 3 u I 7

JHKKFK

vwyx{z}|~B 3u I 7

@FF

e].

_ l$o

!

o

ab[ced\

e)

ab )_

) Y +

s UO

3

I 7

@F

Z ¡¢£¤

')021

8¦¥ ].

9§¥ _

p qr

'!021

¨ ©ª}«

6¬

88

8:9

89

8

¯®B°12±

²³

#´ p

qr

qrµ¶

©ª ' «

qrµ¶·

¸¹

')º»

図3 性能パラメタ最適値導出手法による関連研究の分類

(30)

ライブラリを実行する．そのため，性能パラメタの最適値の導出に時間がかかる．

例：PHiPAC，ATLAS．

2. 性能パラメタの値を絞り込んでから全数探索を実施：

性能パラメタのとり得る値からあらかじめ最適値となる候補を絞って探索する．最適値はこのあらかじめ絞った候補の中から選ばれる．したがって，最適値を最初からはずしてしまう可能性がある．例：I-LIB．

3. 事前に与えられた複数の値(標本点)を選択し最適値推定を実施：

あらかじめ選択した性能パラメタのとり得る値を用いることは項番2 と同じである．その選択した値に対する数値計算ライブラリの実測値をもとに，関数近似などを用いて最適値を推定する．この場合は，関数近似による推定の時間と精度に課題がある．例：FIBER/ABC-Lib，東大小谷・須田グループ.

これらの方式に対し，本論文では，第4の方式として標本点を逐次に追加する新しい性能パラメタ推定方式を提案する．この方式のこれまでの3つの方式との根本的な違いは，

探索範囲を事前に固定して決めてしまうか，あるいは，探索範囲を柔軟に可変にするかにある．あらかじめ，標本点をすべて決めておくのではなく，必要に応じて標本点を逐次的に追加することにより，柔軟性を持ち，効率のよい性能パラメタ推定を実現することができることを3章以下で明らかにする．

2.4 本章のまとめ

本章では，ソフトウェア自動チューニングにおける性能パラメタ推定の位置付けについて述べた．

1. ユーザが数値計算ライブラリのソフトウェア自動チューニングを行なうタイミングには，(a)数値計算ライブラリをユーザの計算機環境にインストールするときのインストール時ソフトウェア自動チューニングと，ユーザプログラムを実際に実行するときの実行時ソフトウェア自動チューニングの2つがあることを示した．

2. それぞれのタイミングでのソフトウェア自動チューニングの役割として，

(31)

（a）インストール時ソフトウェア自動チューニングでは，計算機環境に対するチューニングを行なうこと，ユーザプログラムに関する情報がないので，行列サイズなどについては多くのパタンを調べる必要があることを示した．

（b）実行時ソフトウェア自動チューニングでは，ユーザプログラムに関する情報として，行列サイズなどを特定することができるので，範囲を絞った性能パラメタ推定ができること，ユーザプログラムの実行中にソフトウェア自動チューニングを行なうので，その時間を限りなくユーザに見せないようにする必要があることを示した．

3. ソフトウェア自動チューニングにおける研究課題を整理し，研究課題として，(a) 対象とする計算機環境の拡大，(b)新規の数値計算アルゴリズム開発に伴う性能パラメタの抽出，(c)性能パラメタの最適値の導出，(d)推定した最適値の数値計算ライブラリへの組み込み，(e)ユーザプログラムの精度，実行時間の保証について，

述べた．その中で本論文では，(c)性能パラメタ最適値の導出のための性能パラメタ推定法を対象とする．

4. 性能パラメタ推定法について，関連研究の分類を行なった．(a) 全数探索：すべての性能パラメタの組み合わせパタンについて，数値計算ライブラリを実測，(b) 選択した値の中で全数探索：性能パラメタのとり得る値の中で事前に複数の値を選択し，その中から，最適な値を決定，(c) 標本点を用いた推定：性能パラメタのとり得る値の中から，複数の標本点を選択し数値ライブラリを実行．その実測値から推定を実施し，標本点でない値も含めて最適値を推定する．これらの方式に対し，第4 の方式として標本点を逐次に追加する新しい性能パラメタ推定方式を提案する．この方式のこれまでの3つの方式との根本的な違いは，探索範囲を事前に固定して決めてしまうか，あるいは，探索範囲を柔軟に可変にするかにある．この柔軟性により，効率のよい性能パラメタ推定を実現することができることを3章以下で示す．

(32)

3 標本点逐次追加型性能パラメタ推定法の提案 3.1 新しい性能パラメタ推定法の検討方針

数値計算ライブラリに組み込まれている性能パラメタを，ユーザの持つ計算機環境で実行するユーザプログラムに最適に設定するのが自動チューニングである．そのために，性能パラメタのとり得る値を変えながら数値計算ライブラリを繰り返し実行し，その実行時間を測定する．数値計算ライブラリの性能は主要な複数のループ構造の性能で決まる [97]．それぞれのループ構造の中に，パラメタ化された性能チューニング項目を設定する．

しかしながら，各々のループ構造の最適な性能パラメタ値の組合せを調べつくすには，膨大な時間がかかる．さらに，インストール時自動チューニングの段階では，ユーザプログラムを実際に実行する時に必要とする問題サイズが不明なので，問題サイズを変えながら，数値計算ライブラリを繰り返し実行する必要がある．しかしながら，すべての問題サイズを用いてあらかじめ実行することは不可能である．そのため，性能パラメタのとり得る値からいくつかの点を選択し標本点とし，その標本点を用いて性能パラメタ推定を行なうことにより，自動チューニングを行なう．

実測データをもとに，実測していないパラメタのとり得る値を含めて，コスト定義関数を用いてデータフィッティングによる最適なパラメタ値の推定を行なう．ここで，コスト定義関数とは，評価の基準となる関数であり，最適化問題のコストを定義する．自動チューニングにおいては数値計算ライブラリの性能として実行時間をコストとする^*12．

通常，実測結果に基づくパラメタ推定は，事前に与えられた標本点における実測データだけを用いて行なわれる．標本点が適切に選択されているかどうかが，パラメタ推定の精度，つまり，最適なパラメタ値を推定できるかどうかの条件になる．この標本点の選択は一般に難しい．数値計算ライブラリの性能パラメタの自動チューニングにおいても，実行時間をコストとしたコスト定義関数が，さまざまの計算機環境およびユーザプログラムに

*12本来，コストとしては，性能以外に，使用するメモリ量，精度，使用量などが考えられるが，本論文では，

性能(=実行時間)に特化して扱う

(33)

おいて，どのような特徴を持っているかはわからない．

ソフトウェア自動チューニングにおける標本点の選択について考察する．ここでは，対象とする計算機環境があり，(時間が許せば)どの性能パラメタのとり得る値についてでも数値計算ライブラリを実測することができる．実測済みの標本点だけでは結果が不十分となれば，必要とする標本点をさらに追加して実測することも可能である．したがって，最初から実測データを揃えるのではなく，まず，コスト定義関数の形状を表現するのに必要な最低限の数の実測データを用いた推定から開始し，推定結果が十分であるか否かを判定する．もし十分でなければ，実測すべき標本点を逐次追加する．このことより，推定の効率と精度を向上できる可能性がある．この場合，推定結果が十分であるか，そうでないかをどのように判断するかの基準や，標本点を逐次追加するときに，どのような基準で選択するかを決める必要がある．

一方，コスト定義関数については，一般に，多項式近似などの関数近似法などが用いられる．関数近似法では，その関数をあらわす係数パラメタを最小二乗法などで決定する．

しかし，この方法では関数形そのものの特性が出てくるために，よりよい近似を求めることが難しい．さらに，今回提案する標本点を逐次追加する推定法では，繰り返しコスト定義関数を計算するので計算量を抑えること，および少ない標本点でも安定した結果が得られることが必要となる．したがって，コスト定義関数として，最初から多くの標本点を必要とする関数（たとえば，区分多項式のB-Splineなど）を用いることも難しい．

以上をまとめると，新しい性能パラメタのチューニング方式では，次の２点について検討をする必要がある．

1. コスト定義関数の選択

（a）少ない標本点から計算できること

（b）再計算のための計算量(=実行時間)が小さいこと 2. 標本点を動的に追加する方法を用いる時の２つの基準

（a）標本点を追加するか否かの終了判定基準

（b）標本点を追加すると判定したときの選択基準

(34)

!"

!

!"#

!$

s s s s

%&('*),+,-(.0/213,4576,8:9<;>=?&

s

'*@,A,9CB E FGH

IJ

HK

L

M

NO

P

図4 近似関数f と実測データの集合yの関係

本論文では，各々について提案を行ない，それらを組み合わせることにより，「標本点逐次追加型性能パラメタ推定手法」を実現する[91][92][93]．

3.2 コスト定義関数 d-Spline

3.2.1 コスト定義関数d-Splineの導入

性能パラメタのとり得る値ごとの数値計算ライブラリの実行時間で構成される関数形は，滑らかさとか凸性は保証されない．また，標本点を追加するたびにコスト定義関数を再計算する必要がある．そこで，データの動きに柔軟に追随する柔らかさを持ち，さらに，標本点が少なくても安定に解が得られ，かつ，計算量の少ないコスト定義関数として，近似関数f(x)を次のように定義する．

近似関数 f(x) をn個の離散点上の値 f_j =f(x_j)，1≦ｊ≦ｎで表現する．つまり，

f ＝(f1, f2, f3, . . . , fj, . . . , fn)^t，tは転置を示す．

ここでx_j，1≦ｊ≦ｎは等間隔とする．滑らかさを出すために，ｎは性能パラメタのと

(35)

1-2 1 1 -2 1

1 -2 1

1 -2 1 1 -2 1

1 1

0 1

0 0 1

0 1

1-2 1 1 -2 1

1 -2 1

1 -2 1 1 -2 1

1 1

0 1

0 0 1

0 1

図5 行列E，Dの形状

り得る値の数Nより十分大きくとる^*13．いまN個の中からｋ個の標本点の実測データがとられているとする(ｋ≦Ｎ)．この実測データをyi (１≦i≦k)とする．

y= (y₁, y₂, y₃, . . . , y_i, . . . , y_k)^t，tは転置を示す．

近似関数f とｋ個の実測データの集合ｙおよび性能パラメタのとり得る値との関係を図4に示す．xj(1≦ｊ≦ｎ)の一部が性能パラメタをとり得るN個の値であり，図中の

□で囲んだxj となる．□のうちのｋ個の □S で示したxj が標本点であり，その標本点に対する実測データがyi となる．すべての□が標本点となるわけではない(図4ではx9

に対してyi が存在していないことに注意)．

yだけではyi よりfj の数の方が多いので，f を確定するために，f の滑らかさを式(1) であらわす．

|fj−1−2fj+fj+1|²,1≤j ≤n−1. (1)

この近似関数f を評価関数

minf (ky−Ef k²+α²kDf k²) (2) を最小にするように選ぶ．ここで，E，D は図 5 に示すような行列であり，それぞれ k×n，(n−2)×nのサイズである．式(2)の第1項はデータyと近似関数f との距離で

*13後で述べるように2階差分でf の滑らかさを表現しているので，fjの場所は各性能パラメタのとり得る値の間に最低2点，また両端に2点を配置する．したがって， N個の性能パラメタのとりうる値が等間隔ならば，n=N×3 + 2 となる．

性能パラメタ推定法に関する研究

数値計算ライブラリを対象とした ソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究

田 中 輝 雄

電気通信大学 大学院情報システム学研究科 博士 ( 工学 ) の学位申請論文

2007 年 3 月

数値計算ライブラリを対象とした ソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究

博士論文審査委員会

主査 弓 場 敏 嗣 教授

委員 伊 藤 秀 一 教授

委員 曽 和 将 容 教授

委員 吉 永 努 助教授

委員 本 多 弘 樹 助教授

著作権所有者

田 中 輝 雄

2007 年

An Incremental Performance Parameter Estimation Method Applied to Software Automated Performance Tuning

for Numerical Libraries Teruo Tanaka

Abstract

数値計算ライブラリを対象とした ソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究 田 中 輝 雄

要 旨

目次

図目次

表目次

1 緒 言

1.1 本研究の背景と目的

1.2 コンパイラとの関係

1.3 本論文の構成

2 ソフトウェア自動チューニングにおける性能パラメタ推定 の位置付け

2.1 ソフトウェア自動チューニングを実行するタイミング

2.2 ソフトウェア自動チューニングの研究課題

2.3 性能パラメタ推定の関連研究

2.4 本章のまとめ

3 標本点逐次追加型性能パラメタ推定法の提案 3.1 新しい性能パラメタ推定法の検討方針

s

3.2 コスト定義関数 d-Spline

1-2 1 1 -2 1

1 -2 1

1 -2 1 1 -2 1

1 1

0 1

0 0 1

0 1

1-2 1 1 -2 1

1 -2 1

1 -2 1 1 -2 1

1 1

0 1

0 0 1

0 1

数値計算ライブラリを対象としたソフトウェア自動チューニングにおける

田中輝雄

電気通信大学大学院情報システム学研究科博士 ( 工学 ) の学位申請論文

数値計算ライブラリを対象としたソフトウェア自動チューニングにおける

主査弓場敏嗣教授

委員伊藤秀一教授

委員曽和将容教授

委員吉永努助教授

委員本多弘樹助教授

田中輝雄

数値計算ライブラリを対象としたソフトウェア自動チューニングにおける

性能パラメタ推定法に関する研究田中輝雄

要旨

1 緒言

2 ソフトウェア自動チューニングにおける性能パラメタ推定の位置付け