局所性を考慮した共有メモリ並列計算機上の並列BIBOPアロケータ 遠藤敏夫 Joint work with 田浦健次朗, 米澤明憲 (JSPP2001投稿中)

並列プログラムのメモリ管理 既存のアプローチ 逐次アロケータ + 排他制御 各システム独自のアロケータ Libc mallocなどをそのまま使うと遅すぎる 各システム独自のアロケータ Ex. Apacheサーバ, Cilk, KLIC。プログラマの負担大 汎用並列アロケータ (本研究のアプローチ) [Larsonら98] [Veeら99] …スケーラビリティ [Bergerら00] …スケーラビリティ+消費量 DSMでの局所性への言及はまだない

分散共有メモリ(DSM)マシン 共有メモリマシンの一種 Origin 2000では、 リモート/ローカルメモリのアクセスコスト差は3倍程度 各ページは最初にアクセスしたプロセッサにとってローカル CPU CPU CPU Mem Mem Mem DSM(Originなど) CPU CPU CPU Mem Mem Mem SMP(Enterpriseなど)

並列アロケータが達成すべき目標 局所性 (Origin 2000などのDSM) メモリ消費量 スケーラビリティ 背景: ローカル/リモートメモリのアクセスコスト差(3倍) 確保者にとってローカルなメモリを使わせたい メモリ消費量 アロケータによる消費量≧プログラムによる利用量 多すぎると他プログラムに悪影響 スケーラビリティ 背景: プログラムによってはCPUあたり100K malloc/s 確保処理が並列にできる必要

3条件を満たすためには 空き領域の管理方法に注目 予告: スレッド独立+stealあり の方法を提案 空き領域をスレッド独立に管理すると ○ 局所性、スケーラビリティ × 消費量 空き領域をスレッド間共有すると × 局所性、スケーラビリティ ○ 消費量 予告: スレッド独立+stealあり の方法を提案

メモリ消費量 v.s. 局所性 局所性を最優先させると、メモリ消費量増大の可能性 (B)で、必ずローカルメモリを確保すると消費量2m 最悪スレッド数倍の消費 u1 m thread 1 t u2 m thread 2 t (A) u1 m thread 1 t u2 m thread 2 t (B)

本研究の貢献 BIBOP(big bag of pages)型アロケータの並列化方式LPS(locality-aware page shared)の提案/実装 局所性 ⇔ 消費量間のトレードオフを自由に調整可 許容消費定数 k の導入 スケーラブル 48プロセッサ(R10000 195MHz)で18M malloc/s … 1プロセッサ時(750K malloc/s)の24倍

発表の概要 BIBOP 素朴な並列化方式 提案方式 LPS メモリ消費量解析(簡単に) 性能評価 まとめ

BIBOPアロケータの概要 広まっているアロケータの一つ ヒープは固定サイズページから成り立つ ページは同サイズオブジェクトを含む free obj list 広まっているアロケータの一つ ヒープは固定サイズページから成り立つ ページは同サイズオブジェクトを含む 空き領域は、 フリーオブジェクトリスト(サイズ毎) フリーページリスト で管理 free page list

素朴な並列化になっていない(1/3) All shared(AS) 空き領域を全て共有 × 非スケーラブル ○ 消費量最小 × 局所性悪 threads All-shared(AS) free obj list free　page list OS

素朴な並列化(2/3) All local(AL) 空き領域をスレッド個別管理 ○ スケーラブル × 消費量大 最悪、最小値のスレッド数倍 × 消費量大 最悪、最小値のスレッド数倍 ○ 局所性良 必ずローカルメモリを確保 threads All-local(AL) free obj list free　page list OS

素朴な並列化(3/3) Page shared(PS) 空きオブジェクト: スレッド個別 空きページ: 共有 ○ スケーラブル ○ 消費量小 ←以降の話の標準 × 局所性悪 空きページを任意のスレッドが再利用 threads Page-shared(PS) free obj list free　page list OS

PS, AL方式の性能(1/2) ○← →× Malloc回数のスループット計測 Origin 2000(blue1) 並列木作成ベンチマーク GCあり、同期 GC/free時間省く ○←　→× Malloc回数のスループット計測 PS … 13.5M回/s(逐次の18.5倍) AL … 21.2M回/s(逐次の28.5倍) 両者ともIRIX libc mallocよりはるかにスケーラブル

PS, AL方式の性能(2/2) ×← →○ ×← →○ ALはメモリ消費が激しい PSは局所性が悪い 最悪PSの12倍 Origin 2000(chorus) 擬似サーバベンチ 常に12スレッド GCあり、非同期 使用量: 約20MB 横軸:v=同時にメモリ 利用するスレッド数 ×←　→○ ×←　→○ ALはメモリ消費が激しい 最悪PSの12倍 PSは局所性が悪い 空ページが別スレッドに再利用される率=約0.9

提案方式LPSの外部仕様 Locality-aware page shared (LPS) ○ スケーラブル ○ 消費量: PSのk倍以下かつ、AL以下 ○ 局所性: 上の条件内で最大限に ユーザはk(許容消費倍率, k≧1)によってトレードオフの調節可

Locality-aware page-shared(LPS) 空き領域をスレッド独立 まず自リストを探索 →同スレッドによって再利用されやすい その次は、 消費量を抑えたいとき、他リストを探索 局所性を上げたいとき、OSから確保 threads Locality-aware page-shared(LPS) free obj list free　page list OS

LPSの内部仕様(2/2) a … アロケータによる消費ページ数 l … 前回のGCで生き残ったページ数 成功 空きオブジェクト リスト探索 a … アロケータによる消費ページ数 l … 前回のGCで生き残ったページ数 max l … これまでのlの最大値 k … 許容消費倍率 成功 自分の空きページ リスト探索 Yes a < k max l ? No 成功 他人の空きページ リスト探索 OSから確保 またはGC

LPSの消費量について k kが小さいときはPS並 k max l までは消費 性質上ALは超えない 以上より、どのkに対してもLPS消費量は PS消費量のk倍(#)以下 AL消費量以下 特定のプログラムに 対する消費量 AL 消費量 (#) (3) LPS (2) PS max l (1) 1 k

LPS方式の性能(1/2) LPS(k=1)のスケーラビリティはPSとALの中間 17.8M回/s(逐次の24倍)

LPS方式の性能(2/2) 消費量: v小(左)でもPSのほぼk倍に抑えられている 局所性: k大になるにつれ、remote確保率小 k=1は、PSと変わらず →バランスなプログラムでさえ、局所性を得るためには約2倍の消費が必要

まとめ 並列BIBOPアロケータ方式LPSを提案 ゴールは ユーザは許容消費倍率の調節によって、トレードオフを自由に調節可 スケーラビリティ メモリ消費量 局所性 ユーザは許容消費倍率の調節によって、トレードオフを自由に調節可 メモリ消費量解析、実験による性能評価 トレードオフ

関連研究 ローカルヒープを用いたスケーラブルな並列アロケータ (G)はGCあり、(E)は明示free [市吉ら94](G) … スレッドローカルGC。KLIC言語と密着 [Larsonら98](E) [Veeら99](E) … 共有ヒープへのアクセス頻度解析 [Bergerら00](E) … BIBOP,メモリ消費量解析 [Boehm00](G) … BIBOP, 空きオブジェクトリストの一部のみスレッドローカル いずれもDSMの局所性には言及せず

今後の予定 実用アプリでの実験 局所性の解析 GCスケジューリングとの関係の研究 許容消費倍率の自動選択?