電気通信大学 大学院情報システム学研究科
情報ネットワーク学専攻
0351008 石井 良規
指導教官
弓場 敏嗣 本多 弘樹 曽和 将容
2005年1月31日 提出
目次
1 はじめに 2
1.1 背景 2
1.2 研究の目的 2
1.3 本論文の構成 2
2 Autopilot 2
2.1 概要 2
2.2 Decision Procedure 2
2.3 An Adaptive Climate Control System 2
3 SuperLU 2
3.1 概要 2
3.2 スーパーノードアルゴリズム 2
3.3 オーダリングパラメータ 2
4 RAO-SS 2
4.1 概要 2
4.2 設計方針 2
4.3 提案手法の流れ 2
4.4 パラメータ選択手法 2
4.4.1 非疎度 2
4.4.2 対角要素からの距離 2
4.5 実装の詳細 2
5 性能評価 2
5.1 測定環境 2
5.2 テスト行列 2
5.3 最適パラメータの調査 2
5.4 提案手法を組み込んだSuperLUの性能評価 2
5.5 RAO-SSによる性能評価 2
5.6 考察 2
5.6.1 最適OPに対する考察 2
5.6.2 SuperLUに提案手法を組み込んだ場合の考察 2
5.6.3 RAO-SSに対する考察 2
6 おわりに 2
6.1 性能評価のまとめ 2
6.2 今後の課題 2
謝辞 2
参考文献 2
対外発表 2
図目次
図 1 Autopilot Fuzzy Logic Decision Procedure Infrastructure 2
図 2 Fuzzy Logic Rule Base1 2
図 3 スーパーノードの例 2
図 4 スーパーノードのアルゴリズム 2
図 5 RAO-SSのシステム構成図 2
図 6 提案手法のフローチャート 2
図 7 Fuzzy Logic Rule Base2 2
図 8 Fuzzyによる真理値グラフ 2
図 9 入力行列による非疎度の計算とrao_param.txtへの書き込み 2
図 10 非疎度によるオーダリングパラメータ選択 2
図 11 選択されたオーダリングパラメータによるSuperLUの計算 2
表目次
表 1 roomtemp(上)とfurnace(下) 2
表 2 測定に利用した行列のリスト1 2
表 3 測定に利用した行列のリスト2 2
表 4 デフォルトOPに対して最適OPの速度向上比1 2
表 5 デフォルトOPに対して最適OPの速度向上比2 2
表 6 デフォルトOPに対して最適OPの速度向上グラフ1 2
表 7 デフォルトOPに対して最適OPの速度向上グラフ2 2
表 8 デフォルトOPに対するSLU’の速度向上比1 2
表 9 デフォルトOPに対するSLU’の速度向上比2 2
表 10 デフォルトOPに対するSLU’の速度向上比1 2
表 11 デフォルトOPに対するSLU’の速度向上比2 2
表 12 デフォルトOPに対するRAOの速度向上比1 2
表 13 デフォルトOP に対するRAOの速度向上比2 2
表 14 RAOとデフォルトOPの測定時間比較1 2
表 15 RAOとデフォルトOPの測定時間比較2 2
表 16 Autopilotのソフトウェアオーバーヘッド1 2
表 17 Autopilotのソフトウェアオーバーヘッド2 2
表 18 Autopilotのソフトウェアオーバーヘッド3 2
表 19 Autopilotのソフトウェアオーバーヘッド4 2
1 はじめに
1.1 背景
近年,気象シミュレーションやロケットの軌道予測シミュレーションなど様々な分野で行列演算の高速化が必要とされている.この行列計算の高速化のために,高性能な数値計算ライブラリを利用することが多い.行列演算のための数値計算ライブラリとして,密行列ソルバ,および疎行列ソルバがある.密行列ソルバに対して疎行列ソルバが有する特筆すべき特徴は,行列の数値特性,行列の零要素の位置などによって,高速化手法が異なるということである.したがって疎行列ソルバを利用するには,密行列ソルバよりも複雑なパラメータ設定を必要とする.このことからユーザにとって,適するライブラリ選択や実行パラメータ設定に関して大変負担がかかるという問題がある.また,誤ったライブラリ選択,誤った実行パラメータ設定をしてしまうと,計算性能が劣化するとともに計算が終了しないという,密行列ソルバではあまり生じていなかった事態も生じる.また密行列ソルバや疎行列ソルバに関係なく,現在ほとんどの数値計算ライブラリでは,性能パラメータに対して固定値(デフォルト値)が設定されて公開されている.このことから,計算機環境や入力行列特性に応じた最適なパラメータが設定されない問題があることが知られている[18].
これらの問題を考慮し,自動的にライブラリを選択したり,自動的に実行パラメータの設定を行うライブラリ構成法の研究がある.特に,数値計算ライブラリにおける自動チューニング技術が現在,活発に研究されている.
数値計算ライブラリにおける自動チューニングにおいて,その適用タイミングから分類すると,以下の二つの型が知られている.一つは,ライブラリを新しいマシン環境にインストールする時に行うインストール型である.もう一つは,ライブラリを実行する時に行う実行時型である[17].
本論文では,疎行列ソルバの特性を考慮し,実行時型の自動チューニングに焦点を当てる.実行時型のライブラリでは,Autopilot[1],ActiveHarmony[10]という基盤ソフトウェア(ミドルウェア)が知られている.インストール時と実行時型を融合したライブラリとしては,I-Lib[7]が知られている.また片桐らのFIBER[20]では,上記2種のチューニング型に加え,新たにユーザによるパラメータ設定後に自動チューニングを行う実行起動前型を導入している.
1.2 研究の目的
本研究では,ライブラリ実行時に適するパラメータを自動的に選択し,ライブラリを高速化する機構であるRAO-SS(Run-time Auto-tuning Optimizer for Sparse Solvers)を提案する.RAO-SSは,実行時に自動チューニングを行うことを支援する目的で,ミドルウェアのAutopilotを用いて実装されている.我々は,RAO-SSの自動チューニングによる性能向上の効果検証を行うことを本論文の目的とした.
1.3 本論文の構成
本論文の構成を以下に示す.2章で,Autopilotについて説明する.3章では,行列演算に用いるソルバであるSuperLUについて説明する.4章では,提案するRAO-SSの概要,および実装の詳細を述べる.5章では,RAO-SSの自動チューニング効果の評価をする.最後に6章でまとめと今後の課題を述べる.