共有メモリ並列計算機上の スケーラブルな動的メモリ管理 モジュール 情報科学専攻 米澤研究室 遠藤 敏夫

プログラマの手間を軽くする 自動メモリ管理 メモリオブジェクトを大量に使うプログラム 自然言語処理、(不規則)シミュレーション 解探索問題、画像処理、ネットワークサーバ において、明示的メモリ解放(free())はバグの温床 マルチスレッドプログラムではさらに困難 自動メモリ管理によりプログラマの手間軽減 本研究では探索型ガーベージコレクション(GC)を対象 博士論文発表

メモリ管理モジュールは スケーラブルであるべき 共有メモリ並列計算機: 高性能計算を可能とするプラットフォームの一つ しかし、広まっているメモリ管理モジュール(OS標準のmalloc(), Java VMなどのメモリ管理)の多くは未並列化 アプリによっては スレッドあたり100K回/秒のメモリ確保 GC時間の割合～20% 並列アプリの性能を保つには スケーラブルなアロケータ+GCが必要 アプリを並列化しても メモリ管理が逐次の ままでは無意味！ 博士論文発表

研究の概要 共有メモリ並列計算機上のスケーラブルなメモリ管理モジュールの構築 メモリアロケータ/GCの高速化技法の提案、実装 ボトルネック削減 アーキテクチャの特徴(SMP, DSM)を考慮した技法 性能モデルによる性能解析 (フリーソフトウェアとして公開) http://www.yl.is.s.u-tokyo.ac.jp/gc/ 博士論文発表

本モジュールの概要(1) 対象ハードウェア: 共有メモリ並列計算機 対象ソフトウェア: マルチスレッドプログラム C/C++ Pthread, Solaris threadなど 本発表では1スレッド=1プロセッサを仮定 各スレッドは共有ヒープ中の任意のオブジェクトをアクセス可 CPU Mem CPU Mem SMP: 対称型共有メモリマシン DSM: 分散共有メモリマシン 博士論文発表

本モジュールの概要(2) Conservative GCライブラリ [Boehm et al. 88]の並列化拡張 BIBOP(Big-bag-of-pages)アロケータ 各スレッドが並列にメモリ確保可能 マークスイープGC 複数スレッドが協調的にGC処理 ストップ並列GC 並行並列GC 本研究の技法の多くはBIBOP+マークスイープ以外のシステムにも適用可能 博士論文発表

発表の概要 スケーラブルな並列アロケータ スケーラブルなストップ並列GC (手短に) ストップ並列GCの性能モデル 並行並列GC (手短に) 博士論文発表

Part 1 局所性を考慮したスケーラブルな並列アロケータ (JSPP 2001 で発表)

並列プログラムのアロケータ: 既存のアプローチ(1) 並列プログラムを記述するとき、アロケータをどうする？ 逐次アロケータ + 排他制御 Libc mallocなどをそのまま使うと遅すぎる Libc mallocのスループット SGI Origin 2000 16byteのオブジェクト確保を繰り返した場合のmalloc回数(全スレッド合計) 各スレッドを別プロセッサに割当 free時間省いて計算 ○←　→× 博士論文発表

並列プログラムのアロケータ: 既存のアプローチ(2) 各システム/アプリケーション独自のアロケータ 高速にすることができるが、プログラミングの手間がかかる 汎用並列アロケータ (本研究のアプローチ) [Larsonら98] [Veeら99] …スケーラビリティ [Bergerら00] …スケーラビリティ+消費量 分散共有メモリ(DSM)マシンでの局所性への言及はまだない 博士論文発表

ローカルヒープさえ用意すれば充分か？ スケーラビリティ、局所性は良 スレッド毎メモリ利用量が均一でない場合に問題 スケーラビリティ 各瞬間で必要なメモリ量はmだが、アロケータによる消費量は2m 最悪、(必要メモリ量×スレッド数)の消費 スレッド毎のメモリ利用量の遷移例 m thread 1 利用量 time m thread 2 利用量 time スケーラビリティ 局所性 トレードオフ メモリ利用効率 空き領域のスレッド間共有を 許さない 許す 博士論文発表

並列アロケータが達成すべき 目標 スケーラビリティ 局所性 (ここではDSMに注目) メモリ利用効率 確保処理が並列にできる必要 局所性　(ここではDSMに注目) 背景: ローカル/リモートメモリのアクセスコスト差(3倍) 要求スレッドにローカルなメモリを渡せば、プログラム中のアクセスコストが向上 メモリ利用効率 アロケータによる消費量≧プログラムによる利用量 消費量をなるべく小さく抑えるべき スケーラビリティ、局所性 プログラム性能のため メモリ利用効率 他プログラムへの悪影響を小さくするため 博士論文発表

提案方式の概要 LPS(locality-aware page shared)方式 BIBOP(big bag of pages)型アロケータの並列化方式 スケーラブル 64プロセッサ(R10000 195MHz)で25M malloc/s … 1プロセッサ時の36倍 局所性・メモリ利用効率のトレードオフを連続的に調整可 ユーザは許容消費定数 (k, 1≦k≦スレッド数) を調整 博士論文発表

BIBOPアロケータの概要 ヒープは固定サイズのページから成り立つ 各ページは均一サイズのオブジェクトを含む 空き領域を以下のリストで管理 フリーオブジェクトリスト(サイズ毎) フリーページリスト 確保処理の流れ: フリーオブジェクトリスト探索 失敗ならフリーページリスト探索 失敗ならOSから新ページ確保/GC free obj list free page list heap 博士論文発表

素朴な並列化方式 All Local(AL)方式 Page Shared(PS)方式 空き領域をスレッド個別管理 threads All Local(AL)方式 空き領域をスレッド個別管理 ○ スケーラビリティ、局所性 × メモリ利用効率 Page Shared(PS)方式 空きオブジェクト: スレッド個別 空きページ: 共有 ○ メモリ利用効率 × 局所性 free obj list free　page list OS All-local(AL) threads free obj list free　page list OS Page-Shared(PS) 博士論文発表

Locality-aware page-shared(LPS) 空き領域のスレッド個別管理 + スレッド間の空きページ移動 1. 自フリーオブジェクトリストを探索 2. 失敗なら、自フリーページリストを探索 失敗したら、 3a. 消費量が閾値を超えそうなとき、他リストを探索 3b. 超えないとき、OSから確保 threads Locality-aware page-shared(LPS) free obj list free　page list OS (k×max(l)) kが小 → 利用効率重視 kが大 → 局所性重視 許容消費定数 (ユーザが調節可能) 最低限必要なメモリ量 (PSの消費量に相当) 博士論文発表

実験環境 計算機: DSMマシン SGI Origin 2000 ベンチマークプログラム: R10000 195MHz × 80 Hypercube network ページサイズ16KB 各ページは、プログラム中で最初にアクセスを行ったプロセッサにとってローカルな物理メモリノードに配置される(first-touch) ベンチマークプログラム: Matmul(行列積) CKY(文脈自由文法パーザ) BH(N体問題)、論文参照 C++, GC利用, StackThreads/MP [田浦 99] 利用(CKYのみ) 博士論文発表

予備実験: 確保処理のピーク性能 ○← →× 時間あたりのスレッド間合計malloc回数を計測 AL/LPSのスケーラビリティは良好 16byteのオブジェクト確保の繰り返し メモリ利用量はスレッド間で均一 free/GC時間省いて計算 ○←　→× 時間あたりのスレッド間合計malloc回数を計測 AL/LPSのスケーラビリティは良好 64スレッドで25M回/秒 (1スレッド時の36倍, libc 64 スレッドの54倍) 博士論文発表

性能評価(1): matmul × → サイクリック分割された密行列の積 行列積1回ごとに行列を確保しなおす 各スレッドは自分の行(または列)を確保 AL方式以外ではローカルメモリとは限らない 1000×1000行列同士の積を30回 64スレッド実行時のデータ × → 博士論文発表

性能評価(2): matmulの性能 LPS/ALはPSより3—19%高速 博士論文発表

性能評価(3): CKY 文脈自由文法パーザ 文法データと文データから、ありうる構文を全て計算 あらゆる部分文の構文要素をボトムアップに計算 36—100単語の文を200文解析 64スレッド実行時のデータ 各セルに解析結果の リストを格納 単語 博士論文発表

性能評価(4): CKYの性能 AL/PS間消費量差が大きい LPS/ALはPSより最大5%高速 博士論文発表

考察 アロケータにより全体性能が変わる原因: 確保処理の速度向上か？ 局所性向上によるメモリアクセス速度向上か？ 考えにくい 32スレッド以下でも差が出ている CKYでさえピーク性能の10%以下の確保頻度 局所性向上によるメモリアクセス速度向上か？ Matmulの速度向上がCKYより大きい原因は調査中 考えにくい 16スレッド利用時のデータ (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 ストップ並列GC方式: 複数スレッドが協調的にGCを行う → GC時間を短縮 ユーザ GC time スレッド ストップ GC 並行GC … × 飢餓状態の可能性 [Doligez 93]など ストップ並列GC 並行並列GC (Part 4) [Halstead 85]など [Cheng 01] ストップ並列GC方式: 複数スレッドが協調的にGCを行う → GC時間を短縮 GC中はGCに専念 →　ライトバリアなどを避ける 博士論文発表

並列マークスイープGC(1) GC開始時に全ユーザプログラムを停止 全スレッドにより協調的にマーク処理 → 時間短縮したい! 全スレッドにより協調的にマーク処理 →　時間短縮したい! 終わったらプログラム再開、少しづつスイープ root heap root heap root heap 博士論文発表

並列マークスイープGC(2) スケーラビリティのために、 各スレッド毎にタスクプール (マークスタック) タスクスチール: ひまスレッドは他のマークスタックから仕事(マークすべきオブジェクト)を獲得 スタックの底から一つだけ獲得　→　部分木を獲得することに相当 PE Mark stack PE Mark stack PE Mark stack PE Mark stack PE Mark stack Lazy task creation [Mohr et al. 90]の方式 博士論文発表

スケーラビリティのための 最適化技法 巨大オブジェクトの分割スキャン ボトルネックを除去した終了判定アルゴリズム DSMにおける、マークビットのメモリノード間均等配置 ボトルネック 博士論文発表

実験環境 計算機 プログラム Sun Enterprise 10000 SMP SGI Origin 2000 DSM BH (N体問題) Ultra SPARC 250 MHz × 64 10GB/sクロスバネットワーク SGI Origin 2000 DSM プログラム BH (N体問題) Cube (Rubik’s Cube近似解探索) CKY (文脈自由文法パーザ) 論文参照 博士論文発表

アプリケーション: BH A 点 Barnes-HutアルゴリズムによるN体問題プログラム 60スレッド実行時のデータ (Enterprise, BH-pt) Barnes-HutアルゴリズムによるN体問題プログラム フェーズ1: 各質点を葉とする木構造を、位置を考慮し作成 フェーズ2: 各質点にかかる力を計算 (計算量O(N log N)) 近い点からの力を正確に計算 遠い点からの力を木の中途ノードを用い近似計算 2バージョンの並列プログラム フェーズ2のみ並列化(BH-st) → 1スレッドのみが木作成 フェーズ1,2を並列化(BH-pt) 30,000点を20ステップ計算 ヒープサイズ: 50MB固定 A 博士論文発表 点

アプリケーション: Cube Rubik’s Cubeパズルの近似解 幅優先探索を行い、時々枝刈り(点数の高い局面だけ残す) 60スレッド実行時のデータ (Enterprise) Rubik’s Cubeパズルの近似解 幅優先探索を行い、時々枝刈り(点数の高い局面だけ残す) 局面の重複を防ぐために、局面を二分木で管理 ヒープサイズ: 35MB固定 枝刈り 各局面オブジェクトは 回転履歴リストを含む 博士論文発表

性能評価(1): EnterpriseでのGC速度向上 (マークオブジェクト量/マーク時間)の平均値を計測 負荷分散なしでは全く台数効果は出ない 60スレッドで19—32倍の速度向上 博士論文発表

性能評価(2): OriginでのGC速度向上 13倍 7倍 Enterpriseより速度向上は低い Originでのみ、BH-ptとBH-stの差が大きい なぜ？原因をPart3で解析 博士論文発表

関連研究 ストップ並列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倍の台数効果 博士論文発表

(コンピュータソフトウェア掲載, IPDPS2001で発表) Part 3: ストップ並列GCの性能モデル (コンピュータソフトウェア掲載, IPDPS2001で発表)

メモリアーキテクチャのGC性能への影響 Part2で、ストップ並列GCの性能を計測 … SMP/DSM間の性能差は何のため？ メモリレイテンシ？ バスバンド幅？ アーキテクチャを考慮した、定量的な解析を行いたい GCの性能モデルを提案、性能予測器を構築 考えられる応用: 未知のマシンでの性能評価 オンライン最適化への利用(論文参照) 博士論文発表

性能予測器の特徴 スケーラビリティを低下させる以下の事項を考慮 並列化によるキャッシュミス増加 メモリノードへのアクセス衝突コスト オブジェクト配置のばらつきができうるDSMで重要 CPU cache memory CPU cache memory Enterprise 10000 (SMP) Origin 2000 (DSM) 博士論文発表

性能予測器の概要(1) 入力: GC対象のヒープスナップショット 出力: Pスレッドでの並列GC時間の予測値 ヒープスナップショットに擬似マーク処理を行う Liveオブジェクト量、メモリアクセスパターンを記録 1スレッド実行でのCPU時間、キャッシュミス数を見積もる CPU時間 ← Liveオブジェクト量に比例 キャッシュミス数 ← メモリアクセスパターン+キャッシュシミュレータ 次ページへ 博士論文発表

性能予測器の概要(2) 逐次時 並列時 CPU時間 T1 TP 生存キャッシュ ライン解析 予測並列GC時間 キャッシュミス数 Q1 QP ヒープスナップショットから 逐次時 並列時 CPU時間 T1 TP 生存キャッシュ ライン解析 予測並列GC時間 キャッシュミス数 Q1 QP TPM TPM = TP + QPMP/P キャッシュミス コスト MVA M1 MP 論文訂正: 4.3.1 最終行 × TPM = TP + QPMP ○ TPM = TP + QPMP / P 本説明ではキャッシュミス=メインメモリアクセス 実際には一次/二次キャッシュ、TLBを考慮 博士論文発表

モデルが仮定する事項 各オブジェクトがどのスレッドによりマークされるかはランダム アクセス要求はメモリノードでのみ衝突 1/Pの確率でローカルメモリアクセス アクセス要求はメモリノードでのみ衝突 ネットワーク途中での衝突を無視 (cf. LoPCモデル[Frank et al.97]) キャッシュ無効化の影響を無視 アクセス要求は常に CPU→Mem→CPU 参照カウント2以上のオブジェクトは非常に少量 グラフのほとんどの個所が合流のない木構造と仮定 仕事移動自体のコスト、終了判定コストを無視 博士論文発表

並列時のミスコスト見積もり SL SO 衝突による 待ち時間 プロセッサ ※ ホームメモリノードから 他プロセッサへのアクセス フォワードはないと仮定 メモリノード SL SO SL SL: 片道レイテンシ、SO: メモリノード占有時間のとき、 平均ミスコスト MP = 2 SL + SO +平均待ち時間 混んだメモリノードほど大 各メモリノードへのアクセス頻度より平均待ち時間を取得 擬似マーク中に取得 DSMでは偏り！ 博士論文発表

並列時のミス数見積もり(1) 逐次実行では連続だった仕事が、並列実行では別スレッドによるかもしれない → ミス数の増加 逐次実行 並列実行 B B A A The total number of cache misses on parallel execution may be larger than that on serial execution, Because of task steals. Two objects, this and this, are marked contiguously on serial execution, but they may be marked by other processors on parallel execution. This situation causes more cache misses on parallel execution. PE1 PE1 PE2 PE3 逐次実行では連続だった仕事が、並列実行では別スレッドによるかもしれない → ミス数の増加 博士論文発表

並列時のミス数見積もり(2) 並列時のキャッシュミス数の見積もり: 逐次実行 Q1 = 4 キャッシュライン 並列実行 QP = Q1+4=8 キャッシュミス キャッシュヒット キャッシュライン寿命 並列時のキャッシュミス数の見積もり: QP = Q1 + (タスクスチール数) * (平均生存キャッシュライン数) 今のところ経験則 P log(#live-objects) ヒープスナップショットから取得 博士論文発表

実験結果: 実測と予測の比較 BH(DSM)ではアクセス集中が最大原因 Cubeではミス数増加が最大原因 予測誤差は7%—38% BH-st SMP O2000 DSM 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 LoPCモデル[Vernon et al. 97] 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 ユーザ GC 博士論文発表

並行並列 v.s. ストップ並列 並行並列GCの利害得失: ○ 停止時間の短縮 × ライトバリアのオーバヘッド ○ メモリへのアクセス集中緩和 影響最大 プログラム速度低下 プログラム速度向上 博士論文発表

並行並列GCアルゴリズム ストップ並列GC 今回実装した 並行並列GC Mostly parallel GC[Boehm 91]の並列化 GC cycle 開始フェーズ 並行フェーズ 終了フェーズ 今回実装した 並行並列GC GC cycle Mostly parallel GC[Boehm 91]の並列化 負荷分散あり Incremental updateアルゴリズム[Dijkstra 78]に基づく 実験では、終了フェーズの停止時間と全実行時間を測定 博士論文発表

ライトバリアの必要性 ユーザによるオブジェクト書き込みをGCへ知らせる マーク漏れを防ぐため Incremental updateアルゴリズムの流れ 開始フェーズ: ルートをマークスタックへ 並行フェーズ: 少しづつマーク ユーザ: 書き込んだオブジェクトをGCへ通知 終了フェーズ: [A] 書き込みがあったオブジェクト [B] ルート から再マーク (ストップ並列マーク) ただし原理的に[A]は前倒し可(論文参照) root heap root heap root heap root heap root heap root heap 博士論文発表

ライトバリアの実装 2種類のライトバリアを実装 仮想メモリ機構のページ保護を利用 コード挿入 ○ コンパイラの協力不要 ○ GC中のみオーバヘッドがかかる × 保護コストはマルチプロセッサで大 コード挿入 コンパイラの代わりに、アプリケーションコードに手作業で挿入 博士論文発表

性能評価(1): 停止時間 ストップ並列GCと、並行並列GC(VM利用版)を比較 BH-pt Cube O2K E10K CKY BH-pt CKY Cube E10K O2K ストップ並列GCと、並行並列GC(VM利用版)を比較 E10000 8スレッドにおいて最も効果が高く、1.7—3.2倍の短縮 それ以上では、ストップ並列の方が相対的に速度向上しやすい 博士論文発表

性能評価(2): 実行時間 並行並列GCはストップ並列GCに比べ、同等または遅い(最悪1.9倍) BH-pt CKY Cube E10K O2K 並行並列GCはストップ並列GCに比べ、同等または遅い(最悪1.9倍) VMを使った並行並列はスレッドが増えるほどオーバヘッド大 コード挿入の場合はスレッドが多いときにVMに勝つ 博士論文発表

実行時間の考察 並行並列化によるGCコスト増加は見られるが、全体時間増加を説明するほどではない ライトバリア頻度が高いほど全体時間が長い ライトバリアのコストが最大要因 BH-pt/E10K CKY/E10K Cube/E10K BH-pt/O2K CKY/O2K Cube/O2K 博士論文発表

関連研究 インクリメンタルGC/並行GC 並行並列GC [Cheng et al. 01] [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仕事量/解放量の解析 メモリアーキテクチャの影響の解析 博士論文発表

全体のまとめ スケーラブルなメモリ管理モジュールにより、並列プログラムの性能向上が可能 メモリ管理処理自体の性能向上 各スレッドからの要求を並列に処理する並列アロケータ (Part 1) 複数スレッドで協調的にGC処理を行う並列GC (Part 2, 4) プログラムのメモリアクセス性能向上 局所性を考慮したアロケータ　(Part 1) また、以下の点にも注目 アロケータによるメモリ消費量 (Part 1) GCによる停止時間 (Part 4) 博士論文発表

今後の仕事: さらなる性能向上へ向けて 他アプローチとの融合 コンパイラの協力による最適化 性能予測器の結果を利用した適応的GCアルゴリズム Region analysis 世代別GC 参照カウント ヒープ全体のスケーラブルなGCは依然必要 コンパイラの協力による最適化 Escape analysis → スレッド固有オブジェクト/共有オブジェクトの区別 型情報、フロー解析などによるライトバリア除去 性能予測器の結果を利用した適応的GCアルゴリズム マーク順序/負荷分散方法の自動選択 博士論文発表

コメントお願いします 博士論文発表