Dynamic Function Placement for Data-intensive Cluster Computing サーベイ 2001/10/16 話者: 坂本

分散データ intensive な計算 ネットワーク上に散在した多量のデータにアクセスする計算 フィルタリング, ソート, マイニング 情報検索, 科学技術計算, 生物情報学 ホスト 処理オブジェクト データオブジェクト 2001/10/16

分散データ intensive な計算 計算効率を上げるためには… not only CPU の負荷分散 but also 通信量の削減 ネットワーク構成 プロセッサパワー アプリケーション動作の特徴 … → 最適な計算の配置を予測することは困難 2001/10/16

目次 What’s ABACUS? プログラミングモデル リソースモニタリング 計算の動的再配置 実験 2001/10/16

What’s ABACUS? クラスタにおけるデータ intensive な計算のための支援システム オブジェクトベースのプログラミングモデル 細粒度な移動可能オブジェクト設計をさせ、 実行時システムによる計算の再配置 モニタ履歴から計算の特徴を推測して行う。 プロトタイプ実装が存在 (written in C++) 2001/10/16

プログラミングモデル (記述編) Mobile Objects Iterative Processing 以下をプログラマが実装すること。 Checkpoint() …状態をメモリ/ファイルに保存 Restore() …状態を復帰し再開する → 移動可能にするため (後述: binding manager) Iterative Processing 一定量の処理(アプリケーション依存) をこなすごとに実行権を実行時システムに返すこと。 → 移動タイミングの獲得のため 2001/10/16

プログラミングモデル (実行系) Binding Manager Resource Manager オブジェクトの移動および場所に依存しないメソッド呼び出しを提供する。 Resource Manager メソッド呼び出しにおけるデータ移動量、メモリ使用量、ストール時間などをモニタする。 2001/10/16

プログラミングモデル 固定オブジェクト オブジェクト呼出は必ず bind. mgr. を経由する ストレージサーバや UI オブジェクト等は移動しないオブジェクトとして設計する オブジェクト呼出は必ず bind. mgr. を経由する 実行時システムイメージ図 ストレージサーバ オブジェクト RPC bind bind アプリケーション オブジェクト resource resource 2001/10/16

アプリケーション例 Object-base File-system 2001/10/16

リソースモニタリング (1/2) Data Flow Graph オブジェクトごとのメモリ使用量 オブジェクト間の呼び出しや帰り値でやり取りされるデータ量 オブジェクトごとのメモリ使用量 独自の malloc, free を使ってカウント 2001/10/16

リソースモニタリング (2/2) オブジェクトごとの実行命令(クロック?)数/処理データ量 オブジェクトごとの停止時間 Linux インターバルタイマや Pentium RDTSC 命令を使用して計測 オブジェクトごとの停止時間 他の原因によって stall していた時間 2001/10/16

計算の動的再配置 最近 H 秒のモニタ情報から、オブジェクトのスタック列のなかで、アプリケーションのレスポンスタイムを短くするためには、どこでサーバ/クライアントを分ければよいか判断する。 client server 2001/10/16

レスポンスタイム変化の予測１ O0 ～ On までのオブジェクトスタックを考える 2001/10/16

レスポンスタイム変化の予測２ オブジェクト Oj ににおける処理時間を Pj, Oj Oj+1 間における stall 時間を Cj とした時、レスポンスタイム Tapp は 2001/10/16

レスポンスタイム変化の予測３ Oj が最近 H 秒間に処理したバイト数を bj, 命令数/byte を hj とし、 ノードの load average を Lnode, ノードの処理能力を Rnode とし、 ローカル呼び出しでのstall 時間を 0 と仮定して、 Ok と Ok+1 の間で切れているとき 2001/10/16

レスポンスタイム変化の予測４ 一般に k’ と k’+1 の間で切れているとき Lserver(k’) を以下のように予測する。 右辺の Tapp(k’) は不明である。 2001/10/16

レスポンスタイム変化の予測５ 一般に k’ と k’+1 で切れている場合、前式と以下の式から反復法によって Tapp(k’) を確定させる。 2001/10/16

オブジェクト移動の決定 移動にかかるコスト オブジェクトのサイズ ホスト間の帯域 (Tapp の減少によるご利益) – (移動にかかるコスト) が閾値(Bthresh) を超えるとき移動を行う。 デフォルト値 H = 1sec, Bthresh = 30% (??) 2001/10/16

実験環境 共通 表の見方 SAN 100Mbps, LAN 10Mbps Pentium 2 300MHz 32MB, Linux, 12台 At Client: クライアント側に固定 Adaptive: クライアント側からスタートして移動 At Server: サーバ側に固定 2001/10/16

実験１ RAID object based file system App, RAID のオブジェクトが移動する 2001/10/16

実験１ 結果 2001/10/16

実験１ 考察 2 clients 4MB Write @ LAN 2 clients 4MB Write @ SAN 2 clients degraded read @ SAN リカバリにかかる負荷の分 client でやったほうが速い → いずれも adaptive が中庸 → At Client/Server のいずれかが最適解だから 2001/10/16

実験２ insert/scan オブジェクト Cache オブジェクト Insert オブジェクト Scan オブジェクト Block Size 8KB > (insert/scan working set) Insert オブジェクト 192KB のファイルに 128bytes のレコードを 1500 個をランダムに書き込み Scan オブジェクト 192KB のファイルから 128bytes のレコードを 1500 個をランダムに読み込み insert + cache or scan + cache が移動する 2001/10/16

実験２ 結果 2001/10/16

実験３ アクセスパターンの変化 insert + cache / scan + cache を2回繰り返す insert + cache 2001/10/16

実験３ 結果 Adapt. が合計時間で At Client/Server を下回っている 2001/10/16

References Dynamic Function Placement for Data-intensive Cluster Computing. [Khalil Amiri et.al 2000] Dynamic Function Placement in Active Storage Clusters. [Khalil Amiri et.al 1999] 2001/10/16