共有メモリ並列計算機上の スケーラブルな動的メモリ管理 モジュール 情報科学専攻 米澤研究室 遠藤 敏夫 プログラマの手間を軽くする 自動メモリ管理 メモリオブジェクトを大量に使うプログラム 自然言語処理、(不規則)シミュレーション 解探索問題、画像処理、ネットワークサーバ において、明示的メモリ解放(free())はバグの温床 マルチスレッドプログラムではさらに困難 自動メモリ管理によりプログラマの手間軽減 本研究では探索型ガーベージコレクション(GC)を対象 博士論文発表 メモリ管理モジュールは スケーラブルであるべき 共有メモリ並列計算機: 高性能計算を可能とするプ ラットフォームの一つ しかし、広まっているメモリ管理モジュール(OS標準の malloc(), Java VMなどのメモリ管理)の多くは未並列化 アプリによっては アプリを並列化しても スレッドあたり100K回/秒のメモリ確保 メモリ管理が逐次の GC時間の割合~20% ままでは無意味! 並列アプリの性能を保つには スケーラブルなアロケータ+GCが必要 博士論文発表 研究の概要 共有メモリ並列計算機上のスケーラブルなメモ リ管理モジュールの構築 メモリアロケータ/GCの高速化技法の提案、実装 ボトルネック削減 アーキテクチャの特徴(SMP, DSM)を考慮した技法 性能モデルによる性能解析 (フリーソフトウェアとして公開) http://www.yl.is.s.u-tokyo.ac.jp/gc/ 博士論文発表 本モジュールの概要(1) 対象ハードウェア: 共有メモリ並列計算機 CPU CPU CPU CPU Mem Mem Mem Mem CPU Mem Mem SMP: 対称型共有メモリマシン CPU DSM: 分散共有メモリマシン 対象ソフトウェア: マルチスレッドプログラム C/C++ Pthread, Solaris threadなど 本発表では1スレッド=1プロセッサを仮定 各スレッドは共有ヒープ中の任意のオブジェクトをアクセス可 博士論文発表 本モジュールの概要(2) Conservative GCライブラリ [Boehm et al. 88]の並列化拡張 BIBOP(Big-bag-of-pages)アロケータ 各スレッドが並列にメモリ確保可能 マークスイープGC 複数スレッドが協調的にGC処理 ストップ並列GC 並行並列GC 本研究の技法の多くはBIBOP+マークスイープ以外のシス テムにも適用可能 博士論文発表 発表の概要 1. 2. 3. 4. スケーラブルな並列アロケータ スケーラブルなストップ並列GC ストップ並列GCの性能モデル 並行並列GC (手短に) 博士論文発表 (手短に) Part 1 局所性を考慮したスケーラブル な並列アロケータ (JSPP 2001 で発表) 並列プログラムのアロケータ: 既存のアプローチ(1) 並列プログラムを記述するとき、アロケータをどうする? 逐次アロケータ + 排他制御 Libc mallocなどをそのまま使うと遅すぎる ○← →× malloc回数 (M回/秒) Libc mallocのスループット 1.2 1 0.8 0.6 libc 0.4 0.2 SGI Origin 2000 • 16byteのオブジェクト確保を繰り返した 場合のmalloc回数(全スレッド合計) • 各スレッドを別プロセッサに割当 • free時間省いて計算 0 0 20 40 スレッド数 60 80 博士論文発表 並列プログラムのアロケータ: 既存のアプローチ(2) 各システム/アプリケーション独自のアロケータ 高速にすることができるが、プログラミングの手間がかかる 汎用並列アロケータ (本研究のアプローチ) [Larsonら98] [Veeら99] …スケーラビリティ [Bergerら00] …スケーラビリティ+消費量 分散共有メモリ(DSM)マシンでの局所性への言及はまだない 博士論文発表 ローカルヒープさえ用意すれば 充分か? スケーラビリティ、局所性は良 スレッド毎メモリ利用量が均一でない 場合に問題 各瞬間で必要なメモリ量はmだが、アロケー タによる消費量は2m 最悪、(必要メモリ量×スレッド数)の消費 スレッド毎のメモリ 利用量の遷移例 thread 1 利用量 m thread 2 利用量 m time time スケーラビリティ 局所性 トレードオフ メモリ利用効率 空き領域のスレッド間共有を 許さない 許す 博士論文発表 並列アロケータが達成すべき 目標 スケーラビリティ 局所性 (ここではDSMに注目) 確保処理が並列にできる必要 背景: ローカル/リモートメモリのアクセスコスト差(3倍) 要求スレッドにローカルなメモリを渡せば、プログラム中のアクセスコストが 向上 メモリ利用効率 アロケータによる消費量≧プログラムによる利用量 消費量をなるべく小さく抑えるべき スケーラビリティ、局所性 プログラム性能のため メモリ利用効率 他プログラムへの悪影響を小さくするため 博士論文発表 提案方式の概要 LPS(locality-aware page shared)方式 BIBOP(big bag of pages)型アロケータの並列化方式 スケーラブル 64プロセッサ(R10000 195MHz)で25M malloc/s … 1プロセッサ時の36倍 局所性・メモリ利用効率のトレードオフを連続的に調整可 ユーザは許容消費定数 (k, 1≦k≦スレッド数) を調整 博士論文発表 BIBOPアロケータの概要 ヒープは固定サイズのページから成り立つ 各ページは均一サイズのオブジェクトを含む 空き領域を以下のリストで管理 free obj list フリーオブジェクトリスト(サイズ毎) フリーページリスト 確保処理の流れ: - フリーオブジェクトリスト探索 失敗ならフリーページリスト探索 失敗ならOSから新ページ確保/GC heap 博士論文発表 free page list 素朴な並列化方式 threads All Local(AL)方式 空き領域をスレッド個別管理 ○ スケーラビリティ、局所性 × メモリ利用効率 free obj list free page list OS Page Shared(PS)方式 All-local(AL) 空きオブジェクト: スレッド個別 空きページ: 共有 ○ メモリ利用効率 × 局所性 threads free obj list free page list OS Page-Shared(PS) 博士論文発表 提案方式: LPS方式 Locality-aware Page Shared (LPS)方 式 空き領域のスレッド個別管理 + スレッド間の 空きページ移動 1. 自フリーオブジェクトリストを探索 2. 失敗なら、自フリーページリストを探索 失敗したら、 3a. 消費量が閾値を超えそうなとき、他リストを探索 3b. 超えないとき、OSから確保 threads (k×max(l)) 許容消費定数 最低限必要なメモリ量 (ユーザが調節可能) (PSの消費量に相当) 博士論文発表 free obj list free page list OS Locality-aware page-shared(LPS) kが小 → 利用効率重視 kが大 → 局所性重視 実験環境 計算機: DSMマシン SGI Origin 2000 R10000 195MHz × 80 Hypercube network ページサイズ16KB 各ページは、プログラム中で最初にアクセスを行ったプロセッサにとって ローカルな物理メモリノードに配置される(first-touch) ベンチマークプログラム: Matmul(行列積) CKY(文脈自由文法パーザ) BH(N体問題)、論文参照 C++, GC利用, StackThreads/MP [田浦 99] 利用(CKYのみ) 博士論文発表 ○← →× malloc回数 (M回/秒) 予備実験: 確保処理のピーク性能 30 25 PS LPS(k=1) LPS(k=1.5) AL libc 20 15 10 5 • 16byteのオブジェクト確保の繰り返し • メモリ利用量はスレッド間で均一 • free/GC時間省いて計算 0 0 20 40 スレッド数 60 80 時間あたりのスレッド間合計malloc回数を計測 AL/LPSのスケーラビリティは良好 64スレッドで25M回/秒 (1スレッド時の36倍, libc 64 スレッドの 54倍) 博士論文発表 性能評価(1): matmul サイクリック分割された密行列の積 行列積1回ごとに行列を確保しなおす 各スレッドは自分の行(または列)を確保 AL方式以外ではローカルメモリとは限らない 1000×1000行列同士の積を30回 × → 博士論文発表 64スレッド実行時のデータ 全確保量(MB) 最大生存量(MB) 全確保回数 実行時間(s) 確保頻度(/s) 496.2 43.9 65065 25.7 2535.2 リモートページ確保率 最終メモリ消費量 (MB) 性能評価(2): matmulの性能 80 60 40 20 0 0 20 40 60 スレッド数 50 0 40 60 スレッド数 80 PS LPS(k=1) LPS(k=1.5) AL 0.6 0.4 0.2 0 0 実行時間比 実行時間(秒) 100 20 0.8 80 150 0 1 20 40 60 スレッド数 80 1 0.8 0.6 0.4 0.2 0 PS LPS(k=1) LPS(k=1.5) AL 8 16 24 32 48 スレッド数 LPS/ALはPSより3—19%高速 博士論文発表 64 性能評価(3): CKY 文脈自由文法パーザ 文法データと文データから、ありう る構文を全て計算 あらゆる部分文の構文要素をボト ムアップに計算 36—100単語の文を200文解析 64スレッド実行時のデータ 全確保量(MB) 最大生存量(MB) 全確保回数 実行時間(s) 確保頻度(/s) 各セルに解析結果の リストを格納 博士論文発表 単語 1202.5 31.6 79196965 68.5 1155856.3 リモートページ確保率 140 120 100 80 60 40 20 0 0 40 60 スレッド数 20 40 60 スレッド数 1 0.8 PS LPS(k=1) LPS(k=1.5) AL 0.6 0.4 0.2 0 80 70 60 50 40 30 20 10 0 0 20 0 実行時間比 実行時間(秒) 最終メモリ消費量 (MB) 性能評価(4): CKYの性能 20 40 60 スレッド数 80 1 0.8 0.6 0.4 PS LPS(k=1) LPS(k=1.5) AL 0.2 0 80 8 AL/PS間消費量差が大きい LPS/ALはPSより最大5%高速 16 24 32 48 64 スレッド数 博士論文発表 考察 アロケータにより全体性能が変わる原因: 確保処理の速度向上か? 32スレッド以下でも差が出ている CKYでさえピーク性能の10%以下の確保頻度 考えにくい 局所性向上によるメモリアクセス速度向上か? Matmulの速度向上がCKYより大きい原因は調査中 16スレッド利用時のデータ matmul CKY 確保頻度(/s) 980 1305000 PSでのリモートアクセス率 0.84 0.87 ALでのリモートアクセス率 0.72 0.48 (IRIX Memory Reference Counterにより計測) 博士論文発表 関連研究 ローカルヒープを用いたスケーラブルな並列アロケータ [市吉ら94] … KLIC用アロケータ。スレッドローカルGC [Larsonら98] [Veeら99] … 共有ヒープへのアクセス頻度解析 [Bergerら00] … BIBOP,メモリ消費量解析 [Boehm00] … BIBOP, 空きオブジェクトリストの一部のみスレッドローカ ル いずれもDSMの局所性には言及せず 博士論文発表 Part1のまとめ 並列BIBOPアロケータ方式LPSを提案 ゴールは スケーラビリティ ・・・ 64スレッドで36倍 メモリ利用効率 トレードオフ DSMでの局所性 ユーザは許容消費倍率の調節によって、トレードオフ を自由に調節可 博士論文発表 Part 2 スケーラブルなストップ並列GC (SC97, JSSST全国大会98で発表) ストップ並列GC ユーザ スレッド time GC ストップ GC 並行GC … × 飢餓状態の可能性 ストップ並列GC 並行並列GC (Part 4) [Halstead 85]など [Doligez 93]など [Cheng 01] ストップ並列GC方式: 複数スレッドが協調的にGCを行う → GC時間を短縮 GC中はGCに専念 → ライトバリアなどを避ける 博士論文発表 並列マークスイープGC(1) GC開始時に全ユーザプログラムを停止 全スレッドにより協調的にマーク処理 → 時間短縮したい! 終わったらプログラム再開、少しづつスイープ root heap 博士論文発表 並列マークスイープGC(2) スケーラビリティのために、 各スレッド毎にタスクプール (マークスタック) タスクスチール: ひまスレッドは他のマークスタックから仕事 (マークすべきオブジェクト)を獲得 スタックの底から一つだけ獲得 → 部分木を獲得することに相当 PE PE PE Mark stack 博士論文発表 Lazy task creation [Mohr et al. 90]の方式 スケーラビリティのための 最適化技法 巨大オブジェクトの分割スキャン ボトルネック ボトルネックを除去した終了判定アルゴリズム DSMにおける、マークビットのメモリノード間均等配置 博士論文発表 実験環境 計算機 Sun Enterprise 10000 SMP Ultra SPARC 250 MHz × 64 10GB/sクロスバネットワーク SGI Origin 2000 DSM プログラム BH (N体問題) Cube (Rubik’s Cube近似解探索) CKY (文脈自由文法パーザ) 論文参照 博士論文発表 アプリケーション: BH 60スレッド実行時のデータ (Enterprise, BH-pt) Barnes-HutアルゴリズムによるN体問題プログラム フェーズ1: 各質点を葉とする木構造を、位置を考慮し作成 フェーズ2: 各質点にかかる力を計算 (計算量O(N log N)) 全確保量(MB) 435.6 最大生存量(MB) 33.7 全確保回数 5873518 実行時間(s) 40.6 確保頻度(/s) 144771.3 近い点からの力を正確に計算 遠い点からの力を木の中途ノードを用い近似計算 2バージョンの並列プログラム フェーズ2のみ並列化(BH-st) → 1スレッドのみが木作成 フェーズ1,2を並列化(BH-pt) 30,000点を20ステップ計算 ヒープサイズ: 50MB固定 A 博士論文発表 点 アプリケーション: Cube Rubik’s Cubeパズルの近似解 幅優先探索を行い、時々枝刈り(点数の高い局 面だけ残す) 局面の重複を防ぐために、局面を二分木で管理 ヒープサイズ: 35MB固定 60スレッド実行時のデータ (Enterprise) 全確保量(MB) 183.1 最大生存量(MB) 12.6 全確保回数 8253291 実行時間(s) 14.0 確保頻度(/s) 590364.2 枝刈り 各局面オブジェクトは 回転履歴リストを含む 博士論文発表 性能評価(1): EnterpriseでのGC速度向上 BH-st on E10K Cube on E10K 40 30 30 30 20 10 0 speed-up 40 speed-up speed-up BH-pt on E10K 40 20 10 0 0 20 40 60 number of processors Opt Simple Linear 20 10 0 0 20 40 60 number of processors Opt Simple Linear 0 20 40 60 number of processors Opt Simple Linear (マークオブジェクト量/マーク時間)の平均値を計測 負荷分散なしでは全く台数効果は出ない 60スレッドで19—32倍の速度向上 博士論文発表 性能評価(2): OriginでのGC速度向上 BH-pt on O2K BH-st on O2K 20 10 0 40 30 30 7倍 20 10 0 0 20 40 60 number of processors Opt Simple Linear Cube on O2K 40 speed-up 13倍 30 speed-up speed-up 40 20 10 0 0 20 40 60 number of processors Opt Simple Linear Enterpriseより速度向上は低い Originでのみ、BH-ptとBH-stの差が大きい なぜ?原因をPart3で解析 博士論文発表 0 20 40 60 number of processors Opt Simple Linear 関連研究 ストップ並列GC [Halstead et al. 85]: 負荷分散なし [Uzuhara 90] [Imai et al. 93]: 負荷分散を行うが、ボトル ネック除去が不完全 [Flood et al. 01] 負荷分散、ボトルネック除去。Copy GCと mark-compact GCの並列化 博士論文発表 Part2のまとめ スケーラブルなストップ並列マークスイープGCの構築 負荷分散とボトルネックを除去する最適化 Enterprise 10000 60スレッドで19—32倍の台数効果 Origin 2000 64スレッドで7—20倍の台数効果 博士論文発表 Part 3: ストップ並列GCの性能モデル (コンピュータソフトウェア掲載, IPDPS2001で発表) メモリアーキテクチャのGC性能 への影響 Part2で、ストップ並列GCの性能を計測 … SMP/DSM間の性能差は何のため? メモリレイテンシ? バスバンド幅? アーキテクチャを考慮した、定量的な解析を行いたい GCの性能モデルを提案、性能予測器を構築 考えられる応用: 未知のマシンでの性能評価 オンライン最適化への利用(論文参照) 博士論文発表 性能予測器の特徴 スケーラビリティを低下させる以下の事項を考慮 並列化によるキャッシュミス増加 メモリノードへのアクセス衝突コスト オブジェクト配置のばらつきができうるDSMで重要 CPU CPU CPU CPU CPU CPU cache cache cache cache cache cache memory memory memory memory memory Enterprise 10000 (SMP) Origin 2000 (DSM) 博士論文発表 memory 性能予測器の概要(1) 入力: GC対象のヒープスナップショット 出力: Pスレッドでの並列GC時間の予測値 1. ヒープスナップショットに擬似マーク処理を行う 1スレッド実行でのCPU時間、キャッシュミス数を見積もる 2. 3. Liveオブジェクト量、メモリアクセスパターンを記録 CPU時間 ← Liveオブジェクト量に比例 キャッシュミス数 ← メモリアクセスパターン+キャッシュシミュレータ 次ページへ 博士論文発表 性能予測器の概要(2) ヒープスナップショットから CPU時間 キャッシュミス数 逐次時 並列時 T1 TP Q1 生存キャッシュ ライン解析 予測並列GC時間 QP TPM TPM = TP + QPMP/P キャッシュミス コスト M1 MVA MP • 本説明ではキャッシュミス=メインメモリアクセス • 実際には一次/二次キャッシュ、TLBを考慮 博士論文発表 論文訂正: 4.3.1 最終行 × TPM = TP + QPMP ○ TPM = TP + QPMP / P モデルが仮定する事項 各オブジェクトがどのスレッドによりマークされるかはランダム アクセス要求はメモリノードでのみ衝突 アクセス要求は常に CPU→Mem→CPU 参照カウント2以上のオブジェクトは非常に少量 ネットワーク途中での衝突を無視 (cf. LoPCモデル[Frank et al.97]) キャッシュ無効化の影響を無視 1/Pの確率でローカルメモリアクセス グラフのほとんどの個所が合流のない木構造と仮定 仕事移動自体のコスト、終了判定コストを無視 博士論文発表 並列時のミス数見積もり(1) 逐次実行 並列実行 B B A A PE1 PE1 PE2 PE3 逐次実行では連続だった仕事が、並列実行では別スレッド によるかもしれない → ミス数の増加 博士論文発表 並列時のミス数見積もり(2) 逐次実行 Q1 = 4 キャッシュライン 並列実行 QP = Q1+4=8 キャッシュミス キャッシュヒット キャッシュライン寿命 並列時のキャッシュミス数の見積もり: QP = Q1 + (タスクスチール数) * (平均生存キャッシュライン数) 今のところ経験則 P log(#live-objects) ヒープスナップショットから取得 博士論文発表 実験結果: 実測と予測の比較 Cube 50 50 40 40 GC speed-up E10000 SMP GC speed-up BH-st 30 20 10 0 50 10 20 30 40 # of processors 10 50 0 10 20 30 40 # of processors 50 0 10 20 30 40 # of processors 50 50 40 GC speed-up GC speed-up 20 0 0 O2000 DSM 30 30 20 10 0 40 30 20 10 0 0 10 20 30 40 # of processors 50 BH(DSM)ではアクセス集中が最大原因 Cubeではミス数増加が最大原因 予測誤差は7%—38% 博士論文発表 Real Pred (full) Pred (no contention) Pred (no miss incr.) 関連研究 LogPモデル[Culler et al. 93] LoPCモデル[Vernon et al. 97] latency, overhead, gap(bandwidth), #processor active messageの文脈でのアーキテクチャモデル メッセージ衝突のコストを考慮 Portable Parallel Memory [Frigo 99] 一般の不規則プログラムの性能モデル ミスコスト一定を仮定 ←underestimate 並列ミス増を(ライン数 x steal回数)と見積もり ←overestimate 博士論文発表 Part3のまとめ 並列GC実行時間を見積もるモデルを提案 ヒープスナップショットから、Pスレッドでの実行時間見積り スケーラビリティを制限する以下の要素を考慮 オブジェクトグラフの幅不足(論文参照) 並列化によるキャッシュミス増加 メモリノードでのアクセス衝突コスト GCスレッド数の自動調整(論文参照) 今後の仕事 モデルの改良(タスクスチール回数の正当な見積もりなど) 高速かつ正確な予測器の構築 博士論文発表 Part 4 並行並列GC 並行並列GC リアルタイム性の必要なアプリケーションでは、GCによる停止時 間が問題 → 並行GCが望ましい アプリケーションのスケーラビリティを落とさないためには? GCとプログラムが同時に動き、 GC自体も並列 並行並列GC ユーザ 博士論文発表 GC 並行並列 v.s. ストップ並列 並行並列GCの利害得失: 影響最大 ○ 停止時間の短縮 × ライトバリアのオーバヘッド プログラム速度低下 × 解放量/GC仕事量比の悪化 ○ ひまプロセッサのGCへの利用可 プログラム速度向上 ○ メモリへのアクセス集中緩和 博士論文発表 並行並列GCアルゴリズム ストップ並列GC 開始フェーズ GC cycle 並行フェーズ 終了フェーズ 今回実装した 並行並列GC GC cycle Mostly parallel GC[Boehm 91]の並列化 負荷分散あり Incremental updateアルゴリズム[Dijkstra 78]に基づく 実験では、終了フェーズの停止時間と全実行時間を測定 博士論文発表 ライトバリアの必要性 ユーザによるオブジェクト書き込みをGCへ知らせる マーク漏れを防ぐため root heap Incremental updateアルゴリズムの流れ • 開始フェーズ: ルートをマークスタックへ • 並行フェーズ: 少しづつマーク • ユーザ: 書き込んだオブジェクトをGCへ通 知 • 終了フェーズ: [A] 書き込みがあったオブジェクト [B] ルート から再マーク (ストップ並列マーク) ただし原理的に[A]は前倒し可(論文参照) 博士論文発表 ライトバリアの実装 2種類のライトバリアを実装 仮想メモリ機構のページ保護を利用 ○ コンパイラの協力不要 ○ GC中のみオーバヘッドがかかる × 保護コストはマルチプロセッサで大 コード挿入 コンパイラの代わりに、アプリケーションコードに手作業で挿入 博士論文発表 40 20 # of threads 60 400 160 140 300 120 100 200 80 60 100 40 20 0 pause time (ms) pause time (ms) 0 O2K CKY 0 20 40 # of threads 60 250 1800 1600 Stop avg. 200 1400Stop avg. Stop Stop max. max. 1200 150 1000 Conc Conc avg. avg. 800 100 Conc max. Conc max. 600 400 50 200 00 00 20 40 20 40 ## of of threads threads Cube 100 500 pause time (ms) 1400 200 1200 Stop avg. 1000 150 Stop max. 800 Conc avg. 100 600 Conc max. 400 50 200 00 20 40 60 00 20 40 60 ofthreads threads ## of 80 Stop avg. 400 Stop max. 300 60 Conc avg. 40 Conc max. 200 Stop avg. Stop max. Conc avg. Conc max. 100 20 0 0 20 40 # of threads 60 200 500 pause time (ms) BH-pt 120 400 100 300 80 60 200 40 100 20 0 pause time (ms) E10K pause time (ms) 性能評価(1): 停止時間 400Stop avg. 150 Stop max. 300 100 Conc avg. 200Conc max. 50 100 Stop avg. Stop max. Conc avg. Conc max. 0 60 0 20 40 # of threads 60 ストップ並列GCと、並行並列GC(VM利用版)を比較 E10000 8スレッドにおいて最も効果が高く、1.7—3.2倍の短縮 それ以上では、ストップ並列の方が相対的に速度向上しやすい 博士論文発表 性能評価(2): 実行時間 Stop 1 Conc-VM Conc-Soft 0.5 0.5 0 1 0.5 Conc-Soft 0.5 Normalized Execution Time Normalized Execution Time 1 1.5 Stop 1 Conc-VM 1.5 0 1 0 8 16 32 48 60 # of threads 8 16 32 48 64 # of threads 2 Stop Conc-VM Conc-Soft Stop 1.5 Conc-VM 1 0.5 0 8 16 32 48 60 # of threads 1 Normalized Execution Time 1 1 O2K 1.5 Cube Normalized Execution Time 1.5 CKY Normalized Execution Time E10K Normalized Execution Time BH-pt 32 48 60 #8 of16 threads 2 Stop Conc-VM Conc-Soft Stop 1.5 Conc-VM 1 0 1 8 16 32 48 64 # of threads 0.5 0 1 8 16 32 48 64 # of threads 並行並列GCはストップ並列GCに比べ、同等または遅い(最悪1.9倍) VMを使った並行並列はスレッドが増えるほどオーバヘッド大 コード挿入の場合はスレッドが多いときにVMに勝つ 博士論文発表 実行時間の考察 BH-pt/E10K CKY/E10K Cube/E10K BH-pt/O2K CKY/O2K Cube/O2K GC/全体(%) ライトバリア(回/s) GC/全体(%) ライトバリア(回/s) GC/全体(%) ライトバリア(回/s) GC/全体(%) ライトバリア(回/s) GC/全体(%) ライトバリア(回/s) GC/全体(%) ライトバリア(回/s) ストップ 0.7 並行 (VM) 並行 (Soft) 0.8 1.7 335 274K ストップ 2.3 並行 (VM) 並行 (Soft) 3.7 N/A 496 N/A ストップ 3.3 並行 (VM) 並行 (Soft) 6.1 4.6 767 42.3M ストップ 1.6 並行 (VM) 並行 (Soft) 1.5 2 197 313K ストップ 3.9 並行 (VM) 並行 (Soft) 4.2 N/A 213 N/A ストップ 7.4 並行 (VM) 並行 (Soft) 8.5 12.5 499 47.1M 並行並列化によるGCコスト増加 は見られるが、全体時間増加を 説明するほどではない ライトバリア頻度が高いほど全 体時間が長い ライトバリアのコストが最大要因 博士論文発表 関連研究 インクリメンタルGC/並行GC [Steele 75] [Dijkstra 78] [Baker 78] [Yuasa 90] [Doligez 93] GCとユーザプログラムをインタリーブ マルチプロセッサにおいて1スレッドがGCを行うと、スタベーション 並行並列GC [Cheng et al. 01] 並行並列コピーGCアルゴリズムの提案と性能評価 MLでの実装、コンパイラによるライトバリア → 本研究よりもライトバリアの影響が小さい環境 博士論文発表 Part4のまとめ 並行並列マークスイープGCの構築 実行時間・停止時間について、ストップ並列GCと比較 停止時間の短縮 ライトバリアのコストが実行時間に大きく影響 2種類のライトバリアのオーバヘッド評価 仮想メモリ版はコード挿入版よりスケーラビリティ低 今後の仕事: ライトバリア効率化 別アルゴリズム(Snapshot-at-beginningなど)との比較 性能解析 GC仕事量/解放量の解析 メモリアーキテクチャの影響の解析 博士論文発表 全体のまとめ スケーラブルなメモリ管理モジュールにより、並列プログラムの性能向上が可能 1. メモリ管理処理自体の性能向上 2. 各スレッドからの要求を並列に処理する並列アロケータ (Part 1) 複数スレッドで協調的にGC処理を行う並列GC (Part 2, 4) プログラムのメモリアクセス性能向上 局所性を考慮したアロケータ (Part 1) また、以下の点にも注目 アロケータによるメモリ消費量 (Part 1) GCによる停止時間 (Part 4) 博士論文発表 今後の仕事: さらなる性能向上へ向けて 他アプローチとの融合 Region analysis 世代別GC 参照カウント ヒープ全体のスケーラブルなGCは依然必要 コンパイラの協力による最適化 Escape analysis → スレッド固有オブジェクト/共有オブジェクトの区別 型情報、フロー解析などによるライトバリア除去 性能予測器の結果を利用した適応的GCアルゴリズム マーク順序/負荷分散方法の自動選択 博士論文発表 コメントお願いします 博士論文発表
© Copyright 2024 ExpyDoc