局所性を考慮した共有メモリ並列計算機上の並列BIBOPアロケータ遠藤敏夫 Joint work with 田浦健次朗, 米澤明憲 (JSPP2001投稿中) 並列プログラムのメモリ管理既存のアプローチ  逐次アロケータ + 排他制御  Libc mallocなどをそのまま使うと遅すぎる  各システム独自のアロケータ  Ex. Apacheサーバ, Cilk, KLIC。プログラマの負担大  汎用並列アロケータ (本研究のアプローチ) [Larsonら98] [Veeら99] …スケーラビリティ  [Bergerら00] …スケーラビリティ+消費量 DSMでの局所性への言及はまだない  分散共有メモリ(DSM)マシン  共有メモリマシンの一種 Origin 2000では、  リモート/ローカルメモリのアクセスコスト差は3倍程度  各ページは最初にアクセスしたプロセッサにとってローカル CPU Mem CPU Mem CPU Mem DSM(Originなど) CPU CPU CPU Mem Mem Mem SMP(Enterpriseなど) 並列アロケータが達成すべき目標  局所性 (Origin 2000などのDSM)   背景: ローカル/リモートメモリのアクセスコスト差(3倍) 確保者にとってローカルなメモリを使わせたい  メモリ消費量   アロケータによる消費量≧プログラムによる利用量多すぎると他プログラムに悪影響  スケーラビリティ   背景: プログラムによってはCPUあたり100K malloc/s 確保処理が並列にできる必要 3条件を満たすためには  空き領域の管理方法に注目  空き領域をスレッド独立に管理すると ○ 局所性、スケーラビリティ × 消費量  空き領域をスレッド間共有すると × 局所性、スケーラビリティ ○ 消費量  予告: スレッド独立+stealありの方法を提案メモリ消費量 v.s. 局所性  局所性を最優先させると、メモリ消費量増大の可能性   (B)で、必ずローカルメモリを確保すると消費量2m (B)で、消費量mに抑えるとスレッド2は全てリモートメモリ最悪スレッド数倍の消費 u1 thread 1 m u2 thread 2 m t (A) u1 thread 1 u2 thread 2 t m m (B) t t 本研究の貢献  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 × 非スケーラブル ○ 消費量最小 × 局所性悪 free obj list free page list OS All-shared(AS) ASは以降出てきません素朴な並列化(2/3)  All local(AL)  空き領域をスレッド個別管理 threads ○ スケーラブル × 消費量大 free obj list free page list 最悪、最小値のスレッド数倍 ○ 局所性良必ずローカルメモリを確保 OS All-local(AL) 素朴な並列化(3/3)  Page shared(PS)   空きオブジェクト: スレッド個別空きページ: 共有 threads free obj list ○ スケーラブル ○ 消費量小 ←以降の話の標準 × 局所性悪空きページを任意のスレッドが再利用 free page list OS Page-shared(PS) ○← →× mega malloc ops/sec PS, AL方式の性能(1/2) 25 20 PS AL libc 15 10 5 Origin 2000(blue1) 並列木作成ベンチマーク •GCあり、同期 •GC/free時間省く 0 0 20 40 #threads 60  Malloc回数のスループット計測   PS … 13.5M回/s(逐次の18.5倍) AL … 21.2M回/s(逐次の28.5倍)  両者ともIRIX libc mallocよりはるかにスケーラブル PS, AL方式の性能(2/2) 200 remote ratio consumption (MB) ×← →○ ×← →○ 250 150 100 50 0 0 2 4 6 8 10 # allocator threads 12 1 0.8 0.6 PS AL 0.4 0.2 0 0 2 4 6 8 10 12 # allocator threads  ALはメモリ消費が激しい  最悪PSの12倍  PSは局所性が悪い  空ページが別スレッドに再利用される率=約0.9 Origin 2000(chorus) 擬似サーバベンチ •常に12スレッド •GCあり、非同期 •使用量: 約20MB •横軸:v=同時にメモリ利用するスレッド数提案方式LPSの外部仕様  Locality-aware page shared (LPS) ○ スケーラブル ○ 消費量: PSのk倍以下かつ、AL以下 ○ 局所性: 上の条件内で最大限に  ユーザはk(許容消費倍率, k≧1)によってトレードオフの調節可 LPSの内部仕様(1/2)  空き領域をスレッド独立  まず自リストを探索 threads →同スレッドによって再利用されやすいその次は、  消費量を抑えたいとき、他リストを探索  局所性を上げたいとき、OSから確保 free obj list free page list OS Locality-aware page-shared(LPS) LPSの内部仕様(2/2) 空きオブジェクトリスト探索自分の空きページリスト探索 Yes a < k max l ? No 他人の空きページリスト探索 OSから確保またはGC 成功成功成功 a … アロケータによる消費ページ数 l … 前回のGCで生き残ったページ数 max l … これまでのlの最大値 k … 許容消費倍率 LPSの消費量について特定のプログラムに対する消費量 (1) (2) (3) kが小さいときはPS並 k max l までは消費性質上ALは超えない消費量 AL (#) (3) LPS (2) max l PS (1) 1 k 以上より、どのkに対してもLPS消費量は  PS消費量のk倍(#)以下  AL消費量以下 mega malloc ops/sec LPS方式の性能(1/2) 25 20 PS AL libc LPS(1) 15 10 5 0 0 20 40 #threads 60  LPS(k=1)のスケーラビリティはPSとALの中間  17.8M回/s(逐次の24倍) LPS方式の性能(2/2) 1 PS AL LPS(1) LPS(2) LPS(3) LPS(4) 200 150 100 50 0 0 2 4 6 8 10 12 # allocator threads remote ratio consumption (MB) 250 0.8 0.6 0.4 0.2 0 0 2 4 6 8 10 12 # allocator threads PS AL LPS(1) LPS(1.5) LPS(2) LPS(3) LPS(4) LPS(8)  消費量: 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スケジューリングとの関係の研究許容消費倍率の自動選択?