PowerPoint

全体ミーティング (9/12)
村田雅之
今日の内容
• 修士論文について
– Deterministic Parallel Copying Garbage Collection
• 先日の発表と基本的には同じになります
並列プログラムの非決定性
• スレッドの実行順序により結果が非決定的に
なること
– バグの原因になる
– デバッグが困難である
非決定性の例
Thread 1
x=3
Thread2
Thread 1
x=3
Thread2
x=x*2;
x=x+1;
x=4
x=6
x=x*2;
x=8
x=x+1;
x=7
非決定性の例
Thread 1
x=3
Thread2
Thread 1
x=3
Thread2
x=x*2;
x=x+1;
x=4
x=6
x=x*2;
x=x+1;
x=8
x=7
非決定的
ガベージコレクション (GC)
• 不要なメモリ領域を再利用するアルゴリズム
• GCの実行はユーザプログラムの性能に
影響を与えるので高速化したい
• 並列化すれば高速化が期待できる
並列GCの難しさ
• 実装が難しい
• GCの正しさの検証は複雑
– 必要なデータがすべてコピーされるか、等
• 並列化すると検証はもっと難しくなる
– 前述の非決定性が絡む
並列GCの難しさ
• 実装が難しい
• GCの正しさの検証は複雑
– 必要なデータがすべてコピーされるか、等
• 並列化すると検証はもっと難しくなる
– 前述の非決定性が絡む
本研究の目標
• 並列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
– ヒープ領域を分割する
– 一つのスレッドからしかアクセスしないようにする
– 配列を分割して別のregionに配置することも可能
• Effect
– スレッドのregionへのアクセスを表す型情報
Region
• ヒープを分割しデータを配置する
– 図では変数xをregion Aに変数yをregion Bに配置
• ひとつのregionに複数のスレッドが同時に
アクセスしないよう型システムで保証する
– 決定性を保証できる
ヒープ
region A
region B
x
y
配列の分割
• 配列を分割してそれぞれを別のregionに
配置することができる
region A
配列の分割
• 配列を分割してそれぞれを別のregionに
配置することができる
region A0
region A1
Effect
• プログラム中の文の
regionへのアクセスを表す型情報
• 例
Aを読む、Bに書く
y = x + 1;
x
y
region A
region B
型検査による決定性の検証
• 各スレッドのeffectが異なるregionへのものに
なっていることを型検査で確かめる
– 各スレッドが違うデータにアクセスしていれば
実行順序は結果に影響しない
検証の例
• 配列に書き込みを行う
– 2つの区間に分けて並列処理
• 配列はregion Aに配置されている
region A
配列
並列実行{
write(i,j);
write(k,l);
}
二つの文を並列実行する
Regionを分割しなかったとき
• ともに「Aに書く」というeffectを持つ
– 同じregionに並列にアクセスする
• 型検査によりエラーとなる
– 決定性は保証されない
region A
並列実行{ Aに書く
write(i,j);
write(k,l);
}
Aに書く
Regionを分割したとき
• 並列実行されるスレッドが別のregionへの
effectを持つ
• 型検査を通る
– 決定性が保証される
region A1
region A0
並列実行{ A0に書く
write(i,j);
write(k,l);
}
A1に書く
本研究で行ったこと
• 並列コピーGCのアルゴリズムを考えた
– 逐次のコピーGCのアルゴリズムを拡張する
• DPJの型検査によって決定性を検証した
コピーGC
• ヒープを二つにわけて埋まってきたら必要な
ものだけコピーすることでGCを行う
– プログラムは普段は一方を使用
– 必要なもの = rootから到達可能なもの
From
To
コピーGC
• ヒープを二つにわけて埋まってきたら必要な
ものだけコピーすることでGCを行う
– プログラムは普段は一方を使用
– 必要なもの = rootから到達可能なもの
From
To
並列コピーGCのアルゴリズム
copy(from,to){
if(from,toが十分短ければ){
逐次コピーGCを行う
}else{
from,toを分割
並列実行{ // 再帰呼び出し
copy(fromの前半, toの前半);
copy(fromの後半, toの後半);
}
返ってきた結果を統合
}
}
終了後にデフラグ
並列コピーGCのアルゴリズム
copy(from,to){
if(from,toが十分短ければ){
逐次コピーGCを行う
STEP 1
}else{
大きなヒープの分割
from,toを分割
並列実行{ // 再帰呼び出し
copy(fromの前半, toの前半);
copy(fromの後半, toの後半);
}
返ってきた結果を統合
}
2つを並列実行する
}
終了後にデフラグ
並列コピーGCのアルゴリズム
copy(from,to){
STEP 2
if(from,toが十分短ければ){
各区間について
逐次コピーGCを行う
コピーGCをする
}else{
from,toを分割
並列実行{ // 再帰呼び出し
copy(fromの前半, toの前半);
copy(fromの後半, toの後半);
}
返ってきた結果を統合
}
}
終了後にデフラグ
並列コピーGCのアルゴリズム
copy(from,to){
if(from,toが十分短ければ){
逐次コピーGCを行う
}else{
from,toを分割
並列実行{ // 再帰呼び出し
copy(fromの前半, toの前半);
copy(fromの後半, toの後半);
}
STEP 3
返ってきた結果を統合
分割した結果を
}
ひとつにまとめる
}
終了後にデフラグ
並列コピーGCのアルゴリズム
copy(from,to){
if(from,toが十分短ければ){
逐次コピーGCを行う
}else{
from,toを分割
並列実行{ // 再帰呼び出し
copy(fromの前半, toの前半);
copy(fromの後半, toの後半);
}
返ってきた結果を統合 STEP 4
}
データを移動させて
}
隙間を減らす
終了後にデフラグ
4つのステップ
1.
2.
3.
4.
ヒープを分割する
分割したヒープそれぞれで並列にコピーGC
分割した結果をまとめる
データの移動
STEP 1: ヒープの分割
• 大きなヒープをあるサイズ以下になるまで
並列かつ再帰的に分割
– 分割したヒープをそれぞれ別の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
To1
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)
スケーラビリティの評価
• 実行時間を計測
– ヒープを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倍速い
Speed to sequential algorithm
3.5
3
2.5
2
Parallel
1.5
Sequential
1
0.5
0
1
2
3
4
5
6
7
8
9
Number of worker threads
10
11
12
実験結果(コピーとデフラグ)
• コピーの速度は12スレッドで5.5倍
– 1スレッドの時に対して
– 分割区間外へのポインタで並列性が下がる
• デフラグの速度は11.3倍
60
50
Time (sec)
40
30
Copying
Defrag
20
10
0
1
2
3
4
5
6
7
8
Number of worker threads
9
10
11
12
コピーGCとデフラグの時間
• コピーは分割すると速くなる
– 16分割までは特に
• 12 coresなので
• デフラグは分割が増えると非常に重くなる
70
60
Time (sec)
50
40
Defrag
30
Copying
20
10
0
1
2
4
8
16
32
Number of divided regions
64
128
256
条件を変えてみたとき
• ポインタがさしている距離を広くする
– 範囲外へのポインタが増える
実験結果
• 速度が伸びない
– 12スレッド使って1.5倍弱
1.6
Speed to sequential algorithm
1.4
1.2
1
0.8
Parallel
0.6
Sequential
0.4
0.2
0
1
2
4
6
Number of worker threads
8
12
実験結果
• コピーの並列性が低いためと考えられる
14
12
Speedup
10
8
Copy
6
Defrag
4
2
0
1
2
4
6
Number of worker threads
8
12
さらに別のケース
• ワーカースレッドの数と分割数をあわせる
• 1, 2, 4, 8, 12スレッドで実験
– 12のときのみ16分割
結果
• 8スレッドで3倍弱
– 12スレッドでも同じくらい
• 16分割のため遅くなる
3.5
Speed to sequential
3
2.5
2
Parallel
1.5
Sequential
1
0.5
0
1
2
3
4
5
6
7
8
Number of worker threads
9
10
11
12
結果
• コピーだけなら4.5倍程度
• デフラグの時間はあまり変わっていない
– 問題は複雑になるがスレッド数が増えるため？
50
45
40
Time (sec)
35
30
25
Copy
20
Defrag
15
10
5
0
1
2
3
4
5
6
7
8
Number of worker threads
9
10
11
12
ヒープの長さを変えてみたとき
• だいたい線型
• 並列コピー部分は増えにくい
100
Time (sec)
10
Copying
1
Defrag
Total
Sequential
0.1
0.01
1
2
4
8
16
32
64
Size of Heap (M)
128
256
512
1024
ヒープの長さを変えてみたとき
• 逐次と並列の時間の関係が変わっている
– キャッシュの効果？
100
Time (sec)
10
Copying
1
Defrag
Total
Sequential
0.1
0.01
1
2
4
8
16
32
64
Size of Heap (M)
128
256
512
1024
デフラグの効果
• すべての空き領域に対する
末尾にある空き領域の割合
末尾にある空き領域
– 理想的には100%
• 生きているデータの割合と分割区間数を変化
– 20, 40, 60%
– 1, 2, 4, 8, … , 256分割
測定結果
• 20, 40%では約9割の空き領域が末尾にある
• 60%では非常に悪い
– 使用領域＞空き領域のためデータ移動が困難
100
Ratio of free spaces at the tail (%)
90
80
70
60
20%
50
40%
40
60%
30
20
10
0
1
2
4
8
16
32
Number of divided regions
64
128
256
測定結果
• 分割を増やしたところで改善している
• ピースが小さくなって移動が容易になるため
100
Ratio of free spaces at the tail (%)
90
80
70
60
20%
50
40%
40
60%
30
20
10
0
1
2
4
8
16
32
Number of divided regions
64
128
256
関連研究: 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倍速い

Download Report