全体ミーティング (6/13) 村田雅之.

Presentation on theme: "全体ミーティング (6/13) 村田雅之."— Presentation transcript:

1 全体ミーティング (6/13) 村田雅之

2 テーマ 決定的な並列コピーガベージコレクション 何度実行しても結果が決定的
Deterministic Parallel Copying Garbage Collection 何度実行しても結果が決定的 DPJ [Bocchino Jr. et al. 2009] を応用する シンプルなアルゴリズムを実装

3 アルゴリズムの概要 copy (heap){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする) // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する) (隙間をつめる) (ポインタのつけかえ) }

4 前回の問題点 ポインタのつけかえに時間がかかっていた ヒープ全体を見る必要がある 分割の回数に比例した時間がかかる
データ位置とポインタの値は関連がない 分割の回数に比例した時間がかかる

5 ヒープに隙間があるとき 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

6 データを移動する 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

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

8 ポインタの修正を行うところ 分割ごとにこの操作を行っていた

9 対策 データを移動させるごとにどの範囲のデータがどれだけ移動したか覚えておく その情報をもとに最後にまとめてポインタ情報を書き換える
さっきの例なら、7番のデータが4つ前に移動した ポインタの変更回数を減らせる ヒープ全体をチェックする必要があるため重い

10 前回までのアルゴリズム copy (heap){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする) // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する) (隙間をつめる) (ポインタのつけかえ) }

11 新しいアルゴリズム copy (heap){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする) // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する) (隙間をつめる) // データの移動履歴を記憶 } (ポインタのつけかえ)

12 Linuxでも動いた DPJはMacで動かしていた Javaのバージョンが重要だった 必要なのは1.6以上とされる
試したときはharpでJava1.4だったので動かない harpはSolarisだが… DPJのバージョン自体も最初と変わっているかも

13 環境 candy 配列長さが1G (= 230) Intel Xeon x5570 (4 core) 2.93GHz * 2
8コア, HTで論理的には16コア 72GB RAM Linux Java update 18 配列長さが1G (= 230) そろそろ signed int の限界 (= ) longへの書き換えをする?

14 結果 かなり速くなる

15 ワーカースレッドの数の変化 64分割で測定 限界を超えているのは…

16 逐次実行との比較 8並列で逐次アルゴリズムを上回る

17 どこで時間がかかるのか 各部分について時間を 計測した
copy (ヒープ){ if ( heap.length < Threshold ) then { (逐次アルゴリズムでコピーする); // 範囲外は無視 }else{ cobegin { copy(前半); copy(後半); } // 並列実行 (範囲外だったポインタを処理する); (隙間をつめる); // データの移動履歴を記憶 } (ポインタのつけかえ); 各部分について時間を 計測した

18 測定結果 ポインタのつけかえに多くの時間がかかる

19 対策を考える データの移動を少なくする 移動の情報をコンパクトに 完全に前から詰める必要はないのでは？ 複数回の移動を1回にまとめてしまう
10→8→2と移動させるところを10→2にする

20 その他 調べようとしていること GCの検証について GCのときのキャッシュに関する話

21 今後の日程 7/20 15:00 題目・要旨提出 8/24 15:00 本文提出 8/31 発表 (15分+質疑5分)