全体ミーティング (6/13) 村田雅之
テーマ 決定的な並列コピーガベージコレクション 何度実行しても結果が決定的 Deterministic Parallel Copying Garbage Collection 何度実行しても結果が決定的 DPJ [Bocchino Jr. et al. 2009] を応用する シンプルなアルゴリズムを実装
アルゴリズムの概要 copy (heap){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする) // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する) (隙間をつめる) (ポインタのつけかえ) }
前回の問題点 ポインタのつけかえに時間がかかっていた ヒープ全体を見る必要がある 分割の回数に比例した時間がかかる データ位置とポインタの値は関連がない 分割の回数に比例した時間がかかる
ヒープに隙間があるとき 1 2 3 4 5 6 7 1 4 4 1 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 7 4 5 1 2 4 5 1 2 3 4 5 6 7
必要に応じてポインタを修正 1 2 3 4 5 6 7 1 4 4 1 7 4 5 1 2 4 3 1 2 3 4 5 6 7
ポインタの修正を行うところ 分割ごとにこの操作を行っていた
対策 データを移動させるごとにどの範囲のデータがどれだけ移動したか覚えておく その情報をもとに最後にまとめてポインタ情報を書き換える さっきの例なら、7番のデータが4つ前に移動した ポインタの変更回数を減らせる ヒープ全体をチェックする必要があるため重い
前回までのアルゴリズム copy (heap){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする) // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する) (隙間をつめる) (ポインタのつけかえ) }
新しいアルゴリズム copy (heap){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする) // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する) (隙間をつめる) // データの移動履歴を記憶 } (ポインタのつけかえ)
Linuxでも動いた DPJはMacで動かしていた Javaのバージョンが重要だった 必要なのは1.6以上とされる 試したときはharpでJava1.4だったので動かない harpはSolarisだが… DPJのバージョン自体も最初と変わっているかも
環境 candy 配列長さが1G (= 230) Intel Xeon x5570 (4 core) 2.93GHz * 2 8コア, HTで論理的には16コア 72GB RAM Linux Java 1.6.0 update 18 配列長さが1G (= 230) そろそろ signed int の限界 (= 231-1 ) longへの書き換えをする?
結果 かなり速くなる
ワーカースレッドの数の変化 64分割で測定 限界を超えているのは…
逐次実行との比較 8並列で逐次アルゴリズムを上回る
どこで時間がかかるのか 各部分について時間を 計測した copy (ヒープ){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする); // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する); (隙間をつめる); // データの移動履歴を記憶 } (ポインタのつけかえ); 各部分について時間を 計測した
測定結果 ポインタのつけかえに多くの時間がかかる
対策を考える データの移動を少なくする 移動の情報をコンパクトに 完全に前から詰める必要はないのでは？ 複数回の移動を1回にまとめてしまう 10→8→2と移動させるところを10→2にする
その他 調べようとしていること GCの検証について GCのときのキャッシュに関する話
今後の日程 7/20 15:00 題目・要旨提出 8/24 15:00 本文提出 8/31 発表 (15分+質疑5分)