アーキテクチャパラメータを利用した並列GCの性能予測 東京大学 米澤研究室 遠藤 敏夫/田浦 健次朗/米澤 明憲

様々な並列アーキテクチャ 分散メモリマシン 共有メモリマシン(本研究の対象) プログラムの記述移植性があっても性能移植性があるとは限らない MPP クラスタ 共有メモリマシン(本研究の対象) SMP (symmetric multiprocessor) DSM (distributed shared memory) ソフトウェアDSM プログラムの記述移植性があっても性能移植性があるとは限らない

プログラム性能予測の必要性 性能の理由を定量的に議論できるモデルが欲しい 同一プログラムの速度がマシン毎に違うことも 実行速度 プロセッサ数 同一プログラムの速度がマシン毎に違うことも 理由はレイテンシの違い？メモリ構造の違い？ 未知の計算機での速度を知りたい 今よりプロセッサ数が増えたら？通信が速くなったら？ 性能の理由を定量的に議論できるモデルが欲しい

性能予測研究の動向(非常にいい加減) 本研究の対象: 分散メモリの研究 ＞ 共有メモリの研究 共有メモリマシン(SMP, DSM) 分散メモリの研究 ＞ 共有メモリの研究 明示的な通信 キャッシュミスによる通信 マイクロベンチマークの研究 規則的プログラムの研究 不規則的プログラムの 研究 ＞ 本研究の対象: 共有メモリマシン(SMP, DSM) 不規則的プログラム(並列GC)

本研究の対象ハードウェア(1): Sun Enterprise 10000 CPU CPU CPU CPU cache cache cache cache 実際はメモリモジュールは１６個 memory memory memory memory 64PE SMP･･･ メモリレイテンシは場所によらない レイテンシ: 約600ns(contentionなしの時) メモリ配置は自動的に均等に 一つの大きなメモリモジュールと考えて問題ない アクセス時のメモリ占有は約20ns (一つの大きなメモリモジュールと仮定した場合の計算上の値)

本研究の対象ハードウェア(2): SGI Origin 2000 CPU CPU CPU CPU cache cache cache cache memory memory memory memory 実際はCPU2個+メモリモジュール 1個で1ノード DSM･･･ ローカル/リモートでレイテンシに差 レイテンシ: ローカル約400ns, リモート600ns以上 メモリの配置は、最初にアクセスしたCPUにより決定 メモリモジュール毎の使用メモリの差がアクセス不均衡をひきおこし、メモリコンテンションをひきおこす アクセス時のメモリ占有は約200ns

本研究の対象ソフトウェア: 並列マークスイープGC[遠藤 et al. 97] sweep PEs Time ユーザプログラム GC ユーザプログラムを止め、全プロセッサが協調してマーク・スイープ(以下、マークフェーズに話を絞る) ユーザプログラムのオブジェクトグラフ = 並列GCのタスクグラフ オブジェクトグラフの幅 = GCの並列度 動的負荷分散によるスケーラビリティの達成

並列マークフェーズの詳細 処理概要 メモリアクセス内容 各CPUは自分のルートからオブジェクトを再帰的にマーク(マークビットON) マークスタックによる仕事管理 仕事のなくなったCPUは、他のCPUのマークスタックから仕事を盗む メモリアクセス内容 オブジェクトread キャッシュミスが性能に大きく影響 マークビットtest&set モデルに入れる(後述) 自分のマークスタック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の性能モデル(2) T1: 全タスク量(1プロセッサでの実行時間) T∞: クリティカルパス長 のとき、 クリティカルパス中 のタスク 依存関係 T1: 全タスク量(1プロセッサでの実行時間) T∞: クリティカルパス長 のとき、 Pプロセッサでの平均実行時間 TP = O(T1/P + T∞) ただし実用上は、 TP = T1/P + c∞T∞ (c∞は負荷分散のコストなどに依存する定数)

本研究のモデルの概念図(1) Cilkモデル 仕事量T1 プログラムの挙動 からのデータ C.P.長 T∞ 予測実行時間(1) アーキテクチャ パラメータ CPU数 P キャッシュミスコストを 含まない値 定数 定数c∞ メモリアクセスパターン (オブジェクト、マークビットに対する)予測キャッシュミス数 キャッシュ構造 DSMの場合、メモリモジュール ごとのミスの統計をとる

本研究のモデルの概念図(2) LoPCモデル 予測実行時間(1) メモリ占有時間 予測キャッシュミス数 予測実行時間(2) 予測実行時間(3) メモリレイテンシ Contentionも含む 最終結果 キャッシュミスを含むが、 contentionなしと仮定した値 注: 現在のモデルはLoPCモデルと同様、バンド幅を含まない

実験に使用したユーザプログラム N-Body(Barnes-Hut N体問題プログラム) CKY(自然言語パーザ) オブジェクトグラフは木構造(GCのC.P.短し) 現在の実装ではメモリ配置の偏りが大きい CKY(自然言語パーザ) オブジェクトグラフは配列+リスト(GCのC.P.長め) メモリ配置は均等に近い 以上のプログラムを Enteprise 10000(E10K) Origin 2000(O2K) で走らせ、GCのマークフェーズ速度の実測値と予測値を比較

実験結果(1): 予測と実測の比較 E10K O2K 1～48プロセッサのGC速度の予測値と実測値を比較 N-Body CKY 予測 GC速度 E10K 実測 CPU数 O2K 1～48プロセッサのGC速度の予測値と実測値を比較 クリティカルパス長定数c∞=1として予測

実験結果(2): 予測結果の考察 N-Body CKY O2Kでの性能頭打ちを予測できている。 モデル上の考察から、頭打ちの最大の原因はメモリアクセス不均衡によるコンテンションのためと分かった。 ただし予測のずれは1.3倍程度ある(本発表では未解決)。 CKY 頭打ちが予測できていない。CKYでのGCはC.P.長が長いので、定数c∞の影響が大きいと考えられる。

実験結果(3): クリティカルパス定数の影響 N-Body CKY C∞=1 実測 C∞=2 C∞=4 E10K C∞=8 C∞=16 O2K N-BodyではC.P.が短いのでc∞の影響はほとんどない CKYでの実測値との比較から、 c∞は4～8程度らしい 同時に、CKYではC.P.の長さが頭打ちの最大の原因だと分かった

実験結果(4): 未知のプロセッサ台数での予測 N-Body CKY E10K O2K 32台時のオブジェクトグラフを基に、256台までの性能を予測 c∞=8として予測 N-Body/E10Kですら、頭打ちになるだろうと予測された 台数が多いと、SMPでもコンテンションが問題になりそう

まとめ 共有メモリマシン上の不規則的プログラム(並列GC)の性能予測モデルを提案 予測値と実測値との比較 性能の頭打ちの原因を考察 アーキテクチャパラメータを考慮に入れるためにLoPCモデルを利用 不規則なタスクグラフをとらえるためにCilkモデルを利用 予測値と実測値との比較 性能の頭打ちの原因を考察 N-Body (O2K)ではメモリコンテンションが最大の原因 CKYではクリティカルパスの長さが最大の原因

今後の課題 モデルの改良 予測結果のアルゴリズム自動選択への利用 モデルの適用範囲の拡張 予測精度の向上 定数c∞の詳細な考察 バンド幅、cache write backなどの導入 定数c∞の詳細な考察 動的負荷分散コストとの関連の調査 予測結果のアルゴリズム自動選択への利用 モデルの適用範囲の拡張 ソフトウェアDSMへの拡張 一般の不規則的並列プログラムへの拡張

コードネームSGC C/C++プログラムのための並列マークスイープGC Boehm GC ベース Boehm GC APIとほぼcompatible 任意のC/C++コンパイラ使用可 多種のマルチプロセッサマシンで動作 Linux/Intel processor Solaris/SPARC processor, Solaris/Intel processor IRIX/MIPS processor http://www.yl.is.s.u-tokyo.ac.jp/gc/