全体ミーティング (4/25) 村田雅之

今日の内容 修士研究の進捗について

テーマ Deterministic Parallel Copying Garbage Collection 結果の決定性が保証された並列コピーGC

動機 GCを並列化したい 高速化が期待できる 並列化すると特有の問題がある 結果が実行ごとに変わることがある 実行順序が不定である

並列プログラムの検証に関する研究 Deterministic Parallel Java (DPJ) これを用いる Bocchino Jr. et al., OOPSLA 2009 型検査でメモリ領域へのアクセスを把握する 実行結果の決定性を検証する これを用いる

本研究のアプローチ 並列GCのアルゴリズムの決定性をDPJの型 システムを応用して検証する 並列GCの正しさを検証するための第一歩 結果の決定性が保証されれば 逐次実行環境での正しさを検証するだけで済む

まずやろうとしたこと 単純な並列GCのアルゴリズムを実装してみる

本研究でのヒープのモデル化 単純な整数の配列として表現する 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 配列のインデックスがアドレスを表す 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 よみやすく

単純な並列GCアルゴリズム ヒープを分割してそれぞれの領域について 並列にコピーGCを実行しそれを統合する

単純な並列GCアルゴリズム 1. 分割フェイズ ヒープを複数の区間に分割 区間内にあるrootから到達可能なデータを コピーする 区間外へのポインタが現れたら一時停止

分割フェイズの例 region From 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 region To 1 2 3 4 5 6 7

分割フェイズの例 region From0 region From1 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 region To0 region To1 1 2 3 4 5 6 7

分割フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 ? ? 1 2 3 4 5 6 7

分割フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 1 ? 5 ? 1 2 3 4 5 6 7

分割フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 1 ? 5 4 1 2 3 4 5 6 7

分割フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 範囲外へのポインタは 後回しにする 1 ? 5 4 1 2 3 4 5 6 7

単純な並列GCのアルゴリズム 2. 統合フェイズ 隣り合う領域をひとつの領域として扱う その範囲内でコピーを続ける

統合フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 1 ? 5 4 1 2 3 4 5 6 7

統合フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 1 2 ? 5 4 1 2 3 4 5 6 7

統合フェイズの例 1 2 3 4 5 6 7 1 4 4 1 3 7 4 5 1 2 3 1 5 4 1 2 3 4 5 6 7

単純なアルゴリズムを実装 まずはこのアルゴリズムを実装した(つもりだった) 実は2分割の場合しか考えられていなかった 4分割以上すると不都合なことが起こる

見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・

見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 ? 5 ? ・・・ 1 2 3 4 5 6 7

見落としていた例 さらに範囲外へのポインタ 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 2 ? 5 ? ・・・ 1 2 3 4 5 6 7

見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 2 ? 2 5 3 ・・・ 1 2 3 4 5 6 7 データは前からつめていく方針

見落としていた例 1 2 3 4 5 6 7 1 4 4 2 12 7 4 2 ・・・ 1 2 ? 2 5 3 ・・・ 1 2 3 4 5 6 7 終わっていないのに無視されてしまう ここから前は終わったことにしていた

修正の方針 統合する過程では複数個の処理されて いないポインタが存在 まだコピーされていないデータのインデックスを入れるキューを用意してそれを利用する など

性能について 未完成ではあるが実行時間を計測してみた CPU : Intel Core i7 2.2GHz (4コア) メモリ : 4GB おおまかには評価できそう？ 正確な実装ではさらに計算量が増えそう CPU : Intel Core i7 2.2GHz (4コア) メモリ : 4GB OS : Mac OS X 10.6.7 Java 1.6.0_24

分割サイズを変えてみる 長さ65536の配列について実行 配列を分割する最小サイズを変えてみる 5回実行したときの最速値を計測 ランダムにポインタを設定 配列を分割する最小サイズを変えてみる 5回実行したときの最速値を計測

結果 横軸は分割のサイズ 縦軸は実行時間(μs) 128から落ち着いている

逐次アルゴリズムとの比較 分割・並列化によるコストが大きい 予想はしていたが 実行時間(μs) 128まで分割 6265 逐次アルゴリズム 215

ワーカースレッドの数を変える 1から4で変えてみた DPJのオプション 長さ65536の配列 分割サイズは128

結果 1スレッドの場合と比較した速さ 4スレッドで約1.3倍 逐次部分が多いため？

次にすること 単純なアルゴリズムの実装の修正 性能向上を考える アルゴリズムの工夫 既存アルゴリズムを参考にするなど