全体ミーティング (9/12) 村田　雅之

今日の内容 修士論文について 先日の発表と基本的には同じになります Deterministic Parallel Copying Garbage Collection 先日の発表と基本的には同じになります

並列プログラムの非決定性 スレッドの実行順序により結果が非決定的に なること バグの原因になる デバッグが困難である

非決定性の例 Thread 1 Thread2 Thread 1 Thread2 x = 3 x = 3 x=x*2; x=x+1;

非決定性の例 非決定的 Thread 1 Thread2 Thread 1 Thread2 x = 3 x = 3 x=x*2;

ガベージコレクション (GC) 不要なメモリ領域を再利用するアルゴリズム GCの実行はユーザプログラムの性能に 影響を与えるので高速化したい 並列化すれば高速化が期待できる

並列GCの難しさ 実装が難しい GCの正しさの検証は複雑 並列化すると検証はもっと難しくなる 必要なデータがすべてコピーされるか、等 前述の非決定性が絡む Citation

並列GCの難しさ 実装が難しい GCの正しさの検証は複雑 並列化すると検証はもっと難しくなる 必要なデータがすべてコピーされるか、等 前述の非決定性が絡む Citation

本研究の目標 並列GCの決定性を保証する GCの実装の正しさの証明を難しくする一因となる非決定性を排除できる

本研究で提案する手法 並列GCのアルゴリズムを考える 決定性を検証できる型システムを適用する

DPJ (Deterministic Parallel Java) Type and Effect System for Deterministic Parallel Java Bocchino Jr. らが提案 (2009) 型システムを用いて静的に決定性を検証 実装が公開されている http://dpj.cs.uiuc.edu/

DPJの型システムの特徴 Region Effect ヒープ領域を分割する 一つのスレッドからしかアクセスしないようにする

Region ヒープを分割しデータを配置する ひとつのregionに複数のスレッドが同時に アクセスしないよう型システムで保証する y x 図では変数xをregion Aに変数yをregion Bに配置 ひとつのregionに複数のスレッドが同時に アクセスしないよう型システムで保証する 決定性を保証できる ヒープ region A region B x y

配列の分割 配列を分割してそれぞれを別のregionに 配置することができる region A

配列の分割 配列を分割してそれぞれを別のregionに 配置することができる region A0 region A1

Effect プログラム中の文の regionへのアクセスを表す型情報 例 y x y = x + 1; region A region B Aを読む、Bに書く y = x + 1; x y region A region B

型検査による決定性の検証 各スレッドのeffectが異なるregionへのものに なっていることを型検査で確かめる 各スレッドが違うデータにアクセスしていれば 実行順序は結果に影響しない

検証の例 配列に書き込みを行う 配列はregion Aに配置されている 2つの区間に分けて並列処理 region A 並列実行{ write(i,j); write(k,l); } 配列 二つの文を並列実行する

Regionを分割しなかったとき ともに「Aに書く」というeffectを持つ 型検査によりエラーとなる 同じregionに並列にアクセスする 決定性は保証されない region A 並列実行{ write(i,j); write(k,l); } Aに書く Aに書く

Regionを分割したとき 並列実行されるスレッドが別のregionへのeffectを持つ 型検査を通る 決定性が保証される region A0 region A1 並列実行{ write(i,j); write(k,l); } A0に書く A1に書く

本研究で行ったこと 並列コピーGCのアルゴリズムを考えた 逐次のコピーGCのアルゴリズムを拡張する DPJの型検査によって決定性を検証した

コピーGC ヒープを二つにわけて埋まってきたら必要なものだけコピーすることでGCを行う プログラムは普段は一方を使用 必要なもの = rootから到達可能なもの From To

コピーGC ヒープを二つにわけて埋まってきたら必要なものだけコピーすることでGCを行う プログラムは普段は一方を使用 必要なもの = rootから到達可能なもの From To

並列コピーGCのアルゴリズム copy(from,to){ if(from,toが十分短ければ){ 逐次コピーGCを行う }else{ 並列実行{ // 再帰呼び出し copy(fromの前半, toの前半); copy(fromの後半, toの後半); } 返ってきた結果を統合 終了後にデフラグ

並列コピーGCのアルゴリズム STEP 1 大きなヒープの分割 2つを並列実行する copy(from,to){ if(from,toが十分短ければ){ 逐次コピーGCを行う }else{ from,toを分割 並列実行{ // 再帰呼び出し copy(fromの前半, toの前半); copy(fromの後半, toの後半); } 返ってきた結果を統合 終了後にデフラグ STEP 1 大きなヒープの分割 2つを並列実行する

並列コピーGCのアルゴリズム STEP 2 各区間について コピーGCをする copy(from,to){ if(from,toが十分短ければ){ 逐次コピーGCを行う }else{ from,toを分割 並列実行{ // 再帰呼び出し copy(fromの前半, toの前半); copy(fromの後半, toの後半); } 返ってきた結果を統合 終了後にデフラグ STEP 2 各区間について コピーGCをする

並列コピーGCのアルゴリズム STEP 3 分割した結果を ひとつにまとめる copy(from,to){ if(from,toが十分短ければ){ 逐次コピーGCを行う }else{ from,toを分割 並列実行{ // 再帰呼び出し copy(fromの前半, toの前半); copy(fromの後半, toの後半); } 返ってきた結果を統合 終了後にデフラグ STEP 3 分割した結果を ひとつにまとめる

並列コピーGCのアルゴリズム STEP 4 データを移動させて 隙間を減らす copy(from,to){ if(from,toが十分短ければ){ 逐次コピーGCを行う }else{ from,toを分割 並列実行{ // 再帰呼び出し copy(fromの前半, toの前半); copy(fromの後半, toの後半); } 返ってきた結果を統合 終了後にデフラグ STEP 4 データを移動させて 隙間を減らす

4つのステップ ヒープを分割する 分割したヒープそれぞれで並列にコピーGC 分割した結果をまとめる データの移動

STEP 1: ヒープの分割 大きなヒープをあるサイズ以下になるまで 並列かつ再帰的に分割 十分小さくなったら逐次コピーGCを行う 分割したヒープをそれぞれ別のregionに配置することで決定的な並列実行ができる 十分小さくなったら逐次コピーGCを行う

STEP 2: 逐次コピーGC 基本的には逐次アルゴリズムと同様 ただし分割されたregionの外へのポインタは後回しにする

例: STEP 1 ヒープの分割 ヒープを2分割するケース From To

例: STEP 1 ヒープの分割 From, Toをそれぞれ2分割し別のregionとする From0 From1 To0 To1

例: STEP 2 逐次コピーGC 2つに分けたregionで並列にコピーGCを行う From0 From1 To0 To1

例: STEP 2 逐次コピーGC ただし、regionの外へのポインタがあれば それを記憶して後で追跡する From0 From1 To0

STEP 3: 分割したregionの統合 後回しにしていた、regionの外へのポインタを 再び追跡する

例: STEP3 分割したregionの統合 統合前の状態 From0 From1 To0 To1

例: STEP3 分割したregionの統合 Regionが統合される From To

例: STEP3 分割したregionの統合 後回しにしていたポインタから新たに到達 可能になるデータをコピー From To

例: STEP3 分割したregionの統合 ここでは新しいデータは前から詰めていく 空き領域をリストで管理している From To

例: STEP3 分割したregionの統合 これで必要なデータのコピーが終わる From To

まだ不満なこと ヒープを分割するのでデータが連続して 配置されない From To 隙間が空いている

STEP 4: デフラグを行う データを移動して間を詰める 本研究では単純な方法をとる 末尾に大きく連続した空き領域ができる 後ろの断片から順にできるだけ前に移動

デフラグをするメリット 単純なメモリ管理ができる データをうしろに配置していくだけ 逐次のコピーGCで可能だったこと

例: STEP4 デフラグ このような状態のヒープがあるときを考える

例: STEP4 デフラグ 一番うしろから動かそうとする 末尾の空き領域を大きくしたいので

例: STEP4 デフラグ 移動可能な空き領域を前から探していく この場合一番最初で見つかる

例: STEP4 デフラグ 移動可能な領域を移動する 移動を並列化することで高速化する

例: STEP4 デフラグ 以上の手続きをできるだけ繰り返す

例: STEP4 デフラグ 以上の手続きをできるだけ繰り返す

デフラグの注意点 データを移動させると間違った場所を指す ポインタが生まれる もともとのポインタ

デフラグの注意点 データを移動させると間違った場所を指す ポインタが生まれる データを移動した 間違ったポインタ

間違ったポインタの修正 データ移動の履歴を記憶しておいて移動後に間違ったポインタを修正する 修正は並列に行うことで高速化する この移動の情報を覚えておいて 後でポインタを修正する

このアルゴリズムの決定性の検証 DPJ言語でこのアルゴリズムを記述する DPJの型検査により決定性が検証される

実験 本研究の並列GCの正しさを確認する 性能を測定する 環境 単純なデータについて確認 スケーラビリティ デフラグの効果 6-core Opteron 2.80 GHz * 2 (12 コア), 64GB RAM Linux, Java 1.6.0 update 18, DPJ version 1.7.0

本研究の並列GCの正しさの確認 単純なモデルについて結果を検証 実際にすべてのデータがコピーされている ことを確認 すべてコピーされることが予想されるヒープに このアルゴリズムを適用する 実際にすべてのデータがコピーされている ことを確認 形式的検証は難しいのでできなかった

性能測定 スケーラビリティ デフラグの効果 ヒープの仮想的なモデルを作成 そのモデルについてコピーGCを行う

ヒープの仮想的モデル 2つのポインタを持つオブジェクトを配置 ポインタは一定距離より近いところを指す サイズは230 (= 1G) 局所性がある サイズは230 (= 1G)

スケーラビリティの評価 実行時間を計測 環境 ヒープを16分割してGCを行う 約40%が生きているデータ ワーカースレッドの数を1から12まで変化させる 環境 6-core Opteron 2.80 GHz * 2 (12 コア), 64GB RAM Linux, Java 1.6.0 update 18, DPJ version 1.7.0

実験結果 逐次コピーGCに対して3.2倍速い 12スレッド使用時 1スレッドの場合に対して7.3倍速い

実験結果(コピーとデフラグ) コピーの速度は12スレッドで5.5倍 デフラグの速度は11.3倍 1スレッドの時に対して 分割区間外へのポインタで並列性が下がる デフラグの速度は11.3倍

コピーGCとデフラグの時間 コピーは分割すると速くなる 16分割までは特に 12 coresなので デフラグは分割が増えると非常に重くなる

条件を変えてみたとき ポインタがさしている距離を広くする 範囲外へのポインタが増える

実験結果 速度が伸びない 12スレッド使って1.5倍弱

実験結果 コピーの並列性が低いためと考えられる

さらに別のケース ワーカースレッドの数と分割数をあわせる 1, 2, 4, 8, 12スレッドで実験 12のときのみ16分割

結果 8スレッドで3倍弱 12スレッドでも同じくらい 16分割のため遅くなる

結果 コピーだけなら4.5倍程度 デフラグの時間はあまり変わっていない 問題は複雑になるがスレッド数が増えるため？

ヒープの長さを変えてみたとき だいたい線型 並列コピー部分は増えにくい

ヒープの長さを変えてみたとき 逐次と並列の時間の関係が変わっている キャッシュの効果？

デフラグの効果 すべての空き領域に対する 末尾にある空き領域の割合 生きているデータの割合と分割区間数を変化 理想的には100% 20, 40, 60% 1, 2, 4, 8, … , 256分割 末尾にある空き領域

測定結果 20, 40%では約9割の空き領域が末尾にある 60%では非常に悪い 使用領域＞空き領域のためデータ移動が困難

測定結果 分割を増やしたところで改善している ピースが小さくなって移動が容易になるため

関連研究: GCの形式的検証 Automated Verification of Practical Garbage Collectors. Hawblitzel and Petrank, 2009 正しさや安全性に関する条件式を含めてGCの アルゴリズムを記述する そこから得られた条件式をTheorem Proverを 用いて解くことで性質を検証する 並列GCの決定性については扱わない

関連研究: 並列GC Parallel Garbage Collection for Shared Memory Multiprocessors Flood et al., 2001 ヒープを分割して行う並列コピーGC ヒープ分割による隙間はそのまま 8コアで5倍前後の高速化 条件の差異のため単純比較はできない 決定性についての考察はされていない

Future Works 並列GCの検証に形式的な証明を与える アルゴリズムの改善 コピーGCの速度向上 デフラグの効果を高める 現実的な構造のヒープについて効果的か？

並列GCの形式的検証 決定性を検証して、逐次環境での正しさを 検証すれば並列GCの正しさの検証になる 並列環境と逐次環境の結果は決定的 本研究の並列アルゴリズムは決定的なので あとは逐次環境での形式的検証が必要

まとめ 並列なコピーGCのアルゴリズムを考えた そのアルゴリズムにDPJの型検査を適用し 決定性を検証した 単純なモデルについては正しさを確認した 性能測定を行った 12コアで逐次コピーGCより3.2倍速い