A Performance Prediction Framework for Grid-Based Data Mining Applications

My Reserches

INDEX †

目的、問題 †

• Data-Intensive/Data-Mining Application実行環境の最適化

動機、背景 †

• 計算資源を割り当てるミドルウェアでは、最適な資源選択にアプリケーションの実行時間を予測するための性能モデルが必要
  • これにより最適な割り当てが行える

貢献 †

• 性能モデル構築によりアプリケーションの実行時間を正確に予測
  • ミドルウェア(FREERIDE-G)の一部(Resource Selection Component)として実装
• これにより最適な資源選択が可能になる
  • どのマシン上のレプリカからデータをもらい、どのマシン上で処理するかを決定

提案手法、アイディア、システム †

• ミドルウェア(FREERIDE-G)の一部(Resource Selection Component)として実装
• Resource Selection Componentの役割
  • サンプリングデータ(Summary Information)を元に資源選択を行う
    • データのどのマシン上のレプリカを使用するかを決定
    • それらのデータをどのマシン上で計算するかを決定
  • Summary Informationは事前にサンプリング(Profile Run)されている
• Summary Informationの内容
  • ストレージ・ノードの数(n)、計算ノードの数(c)とそれらを結ぶネットワークのバンド幅(b)
  • データ検索時間(td)、データ転送時間(tn)、データ処理時間(tc)
  • データセットサイズ(s):検索、転送、処理されるデータのサイズ
  • データセット上のReduction objectの最大サイズ
  • Reduction objectのための最大通信時間
  • global reduction時間
  • ヘテロ環境に対応するために以下の情報も含まれる
    • CPU(sc)、Disk(sd)、Network(sn)の性能

Simpleモデリング手法 †

• アプリケーションの実行時間を３つに分割
  • Tdisk: データ検索時間
  • Tnetwork： データ通信時間
  • Tcompute： データ処理時間

Texec=Tdisk+Tnetwork+Tcompute

データ検索時間(Tdisk) †

Tdisk=(sx/s)*(n/nx)*td

• s、n、tdはSummary Informationの情報
• 予測したいアプリケーションの実行環境
  • sx： データサイズ
  • nx： ストレージ・ノードの数
• 各ノードの性能が同じ場合を仮定しているので、後に述べるScaling Factorを付加する必要がある

データ通信時間(Tnetwork) †

Tnetwork=(sx/s)*(n/nx)*(b/bx)tn

• bはSummary Informationの情報
• 予測したいアプリケーションの実行環境
  • bx： ネットワークのバンド幅
• ストレージ・ノードの数にしたがってスループットが増加数と仮定
  • そうでなければ(n/nx)を取り除く
• ストレージ・ノードと計算ノードのバンド幅はどのような構成においても一定であると仮定
  • Siteされている論文からこの仮定は妥当であると言っている

データ処理時間(Tdisk) †

Tcompute=(sx/s)*(c/cx)*tc

• 並列度にしたがって線形に性能が上がると言っている

Sophisticated モデリング手法 †

• より洗練されたモデルを構築するためにはさらに以下のことについて考える必要がある
  • Reduction、Global Reductionをともなう計算
  • ヘテロなクラスタ環境

「Reduction、Global Reductionを考慮した」データ処理時間(Tdisk) †

Tcompute=(sx/s)*(c/cx)*(tc-Tro-Tg)+Tro+Tg

■Tro=Aro*r+Bro

• Tro：Reductionに費やす時間
  • r：Reduction通信のデータ・サイズ(Reduction Object Size)
  • Aro、Bro：バンド幅や遅延から実験的に得られる値
  • アプリケーションのタイプを実験的に2つに分類
    • linear object sizeクラス：計算ノード数やデータセットサイズによって線形に"Reduction Object Sizeが"増加するタイプ
    • constant reduction object sizeクラス：アプリケーションのパラメータによって"Reduction Object Sizeが"増加するタイプ
  • Reduction Object Sizeはどうやって得るのか？
    • これらをユーザが実行時にクラスを指定もしくはSummary Informationから見積もることによってどちらのタイプか？を判断できると言っている。

■Tg

• Tg：Global Reducitonに費やす時間
  • アプリケーションのタイプを実験的に2つに分類
    • linear-constant global reductionクラス：（データセットサイズに非依存で）計算ノード数によって線形に"Tgが"増加するタイプ
    • constant-linear global reductionクラス：（計算ノード数に非依存で）データセットサイズによって線形に"Tgが"増加するタイプ
  • Tgはどうやって得るのか？
    • これらをユーザが実行時にクラスを指定もしくはSummary Informationから見積もることによってどちらのタイプか？を判断できると言っている。

「ヘテロ環境を考慮した」アプリケーション実行時間(Texec) †

Texec_b=sd*Tdisk_a+sn*Tnetwork_a+sc*Tcompute_a

■sd=( (Tdisk_b_1/Tdisk_a_1) + ... + (Tdisk_b_n/Tdisk_a_n) ) / n

■sn=( (Tnetwork_b_1/Tnetwork_a_1) + ... + (Tnetwork_b_n/Tnetwork_a_n) ) / n

■sc=( (Tcompute_b_1/Tcompute_a_1) + ... + (Tcompute_b_n/Tcompute_a_n) ) / n

• Profile runとしてクラスタ環境a採用されたSummary Informationからクラスタ環境bでの実行時間を予測するときの例
• sd：Tdiskのscaling factor
  • Tdisk_x_y：クラスタ環境xでアプリケーションyを実行したときのTdiskの時間
• sn、scもsdと同様の解釈

提案したものの評価 †

使用するアプリケーション †

• k-means Clustering(k-means法を用いたクラスタ分析)
• Expectation Maximization Clustering(EMアルゴリズムを用いたクラスタ分析)
• k-Nearest Neighbor Search(k近傍探索)
• Vortex Detection Algorithm(乱気流検出アルゴリズム)
• Molecular Defect Detection Algorithm

評価 †

• さまざまな環境下でPrediction Error(E)の値を評価している E=|Texact-Tpredicted|/Texact

ストレージ・ノードと計算ノードを変化させた評価 †

• 凡例
  • no communication：
    • Reduction、Global Reductionを考慮しない場合
  • reduction communication：
    • Global Reductionを考慮しない場合
  • global reduciton
    • 提案手法：Reduction、Global Reductionの両方を考慮

著者 †

• Leonid Glimcher
• Gagan Agrawal

出典 †

• IPDPS2007

その他 †

• このモデリング手法のいいところだけパクろ。