自動チューニング数理 基盤ライブラリ

自動チューニング数理
基盤ライブラリ
須田礼仁
東京大学/JST
自動チューニングの数理
自動チュ
ニングの数理
もとになる
プログラム
変種の選択
実験計画
プログラムの
性能の測定
高性能な変
種の実現
測定ばらつき
データ解析
プログラムの
性能の分析
高性能な変
種の考案
性能モデル
フィッティング
誤差解析
高性能な
プログラム
変種の選択
最適化
自動チューニング数理の研究
自動チュ
ニング数理の研究
自動チューニングの数理的抽象化
自動チューニングの数理手法の開発
自動チューニングの数理手法の実装
4DAC 階層
C4: 最適化
C3: 実験計画
A4: 目的関数
C2: コスト推定モデル学習
A3: 利用予測
C1: データ解析
デ
A1 測定ばらつき
A1:
A2: コスト推定モデル
デ
D2: チューニング
グ
パラメータ
D3: システム
特徴量
D1: コスト関数
D4: データ
特徴量
自動チューニングの数理手法
自動チュ
ニングの数理手法
ベイズ統計に基づくデータ解析
オンライン自動チューニング
環瀬戸内 2006, HPC 2007/10
iWAPT 2007, HPCS 2008
ワンステップ近似（準最適逐次実験計画）
iWAPT 2007, HPCS 2008
無限希釈
モデル誤差の推定（分散成分）
SWoPP 2008, 計算工学会 2009
S i
Springer
2010
2010, 応用数理 2010
オフライン自動チューニング
ランダマイズ実験計画
最適性を保存した枝刈り
並列処理のための実験計画
RAMP 2010
HPC 2010/6
応用数理年会 2010
応 数 年会 2009
応用数理年会
並列実験（複数候補の並列評価）
その他：チュ ニングメ タ
その他：チューニングメータ
応用数理 2010
iWAPT 2010, PMMA 2010, SWoPP 2010
並列試行（専用プロセッサによる並列試行）
計算工学会 2010
試行
実施
目的関数：試行コスト＋定数×１回あたりの実施コスト
実施
目的関数：合計実施コスト
最適化コストが，オフライン自動チューニングの 1/10 など
ワンステップ近似（準最適実験計画）
• オフライン自動チューニング
オフライン自動チュ
ング
– 次の wt を最小にする候補 t を選択


w t   t   E y min
i  t post ( y ),
)  min'
•
•
•
•
•

t : 候補 t の今の期待コスト
y : 次の実験での候補 t のコスト（変数）
tpost(y) : y を観測後の候補 t の期待コスト
min’ : t 以外で最速の候補
もし min{w
i { t} >  min なら，実験終了
なら 実験終了
• オンライン自動チューニング
オンライン自動チュ
ング


w t   t  ( k  1) E y min  t post ( y ),  min'

確率的候補選択法
残り反復回数を k とすると，ワンステップ近似は
wi
候補
のコスト
の期待値
まとめなおして
min { 候補
候補 } の期待値
× (k – 1)
wi = ai + k bi
既知最速の候補 0 について a0, b0 を求める
for i = 1, 2, 3, …
候補 i について ai, bi を求める
if ai > a0, bi < b0 then
ki = – (ai – a0) / (bi – b0) とする
確率 1 / ki で i を選び，選択終了
推定性能が悪い候補
もある確率で選ばれる
ワンステップ近似より
若干性能が低い
並列実験：同一タスク問題
候補 m の所要時間はプロセッサによらず tm
性能モデル等から事前情報
性能
デ 等
事前情報 tm ~ N((m, m2)
測定ばらつきなし
第 1 反復で試した候補の性能は既知・・・
最速の候補を mopt, その所要時間を topt とする
第 2 反復
選択肢 0 :
第 1 反復で最速だった mopt をずっと使う
W 0  ( K  1) t opt
選択肢 n :
第 2 反復で
反復 n 個を試し，m
個を試し opt も含めて
も含め
最速だったものを，第 3~K 反復で使う
W n  max{ t P  1 ,  , t P  n }  ( K  2 ) min{ t P  1 ,  , t P  n , t opt }
ここは数値計算
自動チューニング数理の課題
自動チュ
ニング数理の課題
並列処理
敵対的コスト
特徴量・相関
自動チューニングの課題
自動チュ
ニングの課題
•
•
•
•
•
•
•
自動チューニング指向プログラミング
自動チュ
ニング指向プログラミング
コ ド変換とコ ド生成
コード変換とコード生成
適応性制御の記述と実装
チューニング機構（数理）
性能測定システム，駆動システム
実行条件（HW/SW/デ タ/環境）
実行条件（HW/SW/データ/環境）
重要な個別課題（アルゴリズム 並列 GPU）
重要な個別課題（アルゴリズム，並列，GPU）