アーキテクチャパラメータを利用した並列GCの性能予測.pptVIP

アーキテクチャパラメータを利用した並列GCの性能予測 東京大学 米澤研究室 遠藤 敏夫/田浦 健次朗/米澤 明憲 様々な並列アーキテクチャ 分散メモリマシン MPP クラスタ 共有メモリマシン(本研究の対象) SMP (symmetric multiprocessor) DSM (distributed shared memory) ソフトウェアDSM プログラムの記述移植性があっても性能移植性があるとは限らない プログラム性能予測の必要性 同一プログラムの速度がマシン毎に違うことも 理由はレイテンシの違い？メモリ構造の違い？ 未知の計算機での速度を知りたい 今よりプロセッサ数が増えたら？通信が速くなったら？ 性能の理由を定量的に議論できるモデルが欲しい 性能予測研究の動向(非常にいい加減) 本研究の対象: 共有メモリマシン(SMP, DSM) 不規則的プログラム(並列GC) 本研究の対象ハードウェア(1):Sun Enterprise 10000 64PE SMP??? メモリレイテンシは場所によらない レイテンシ: 約600ns(contentionなしの時) メモリ配置は自動的に均等に 一つの大きなメモリモジュールと考えて問題ない アクセス時のメモリ占有は約20ns (一つの大きなメモリモジュールと仮定した場合の計算上の値) 本研究の対象ハードウェア(2):SGI Origin 2000 DSM??? ローカル/リモートでレイテンシに差 レイテンシ: ローカル約400ns, リモート600ns以上 メモリの配置は、最初にアクセスしたCPUにより決定 メモリモジュール毎の使用メモリの差がアクセス不均衡をひきおこし、メモリコンテンションをひきおこす アクセス時のメモリ占有は約200ns 本研究の対象ソフトウェア:並列マークスイープGC[遠藤 et al. 97] ユーザプログラムを止め、全プロセッサが協調してマーク?スイープ(以下、マークフェーズに話を絞る) ユーザプログラムのオブジェクトグラフ = 並列GCのタスクグラフ オブジェクトグラフの幅 = GCの並列度 動的負荷分散によるスケーラビリティの達成 並列マークフェーズの詳細 処理概要 各CPUは自分のルートからオブジェクトを再帰的にマーク(マークビットON) マークスタックによる仕事管理 仕事のなくなったCPUは、他のCPUのマークスタックから仕事を盗む メモリアクセス内容 オブジェクトread キャッシュミスが性能に大きく影響 マークビットtestset モデルに入れる(後述) 自分のマークスタックread/write ほとんどキャッシュにのる 他人のマークスタックread 回数は少ない 研究方針 簡単な性能予測モデルを提案 (特に不規則的プログラムでは)正確な予測精度を達成するのは難しい。 精度を上げることよりも、以下の項目を重視する。 アーキテクチャの差異による性能差をとらえる 性能頭打ちの原因をとらえる プログラムの性質が原因？ハードウェアが原因？ 最近のハードでは、メモリコンテンションに注目すべき LoPCモデルと、Cilk性能モデルを合わせたモデルを提案 モデルによる予測値と実測値を比較 LoPCモデル[M. Frank et al. 97] LoPC: 分散メモリマシンの性能モデルの一つ LogPモデル - バンド幅 + message contention contentionのコストを待ち行列理論により議論 本研究では共有メモリ(DSM/SMP)用にモデルを変更 共有メモリのキャッシュミス=分散メモリの通信 Cilkの性能モデル(1)[Blumofe et al. 94] Cilk: 並列プログラム言語 細粒度スレッド、動的負荷分散により、不規則的で効率的なプログラムを容易に記述可能 仕事量とクリティカルパスに基づいた性能モデルにより平均実行時間を保証 しかし、アーキテクチャの差異を考慮に入れていない Cilkの性能モデル(2) T1: 全タスク量(1プロセッサでの実行時間) T∞: クリティカルパス長 のとき、 Pプロセッサでの平均実行時間 TP = O(T1/P + T∞) ただし実用上は、 TP = T1/P + c∞T∞ (c∞は負荷分散のコストなどに依存する定数) 本研究のモデルの概念図(1) 本研究のモデルの概念図(2) 実験に使用したユーザプログラム N-Body(Barnes-Hut N体問題プログラム) オブジェクトグラフは木構造(GCのC.P.短し) 現在の実装ではメモリ配置の偏りが大きい CKY(自然言語パーザ) オブジェクトグラフは配列+リスト(GCのC.P.長め) メモリ配置は均等に近い 以上の