BSPモデルを用いた
並列計算の有用性の検証
情報論理工学研究室
00-1-26-019 伊波 修一
目的
• BSPモデル上で高速なクイックソートを行う
※BSP:通信や同期を考慮した並列計算モデル
※クイックソート: 整列アルゴリズムの一種
並列計算とは
• 問題を複数の仕事に分解
• 並列化された計算機群に計算をさせる
• 1つの問題に対して複数のマシンを利用
• 目的:複雑な問題をより早く解く
PRAMモデル
(Parallel Random Access Memory)
Shared Memory
P1
P2
P3
・・・・・・
・通信時間時間を考えない
・並列処理機構が理想的
Pn
PRAMモデル
(Parallel Random Access Memory)
• 通信を考えない
→ 理想的な並列計算モデル
→ 現実と大きなギャップ
BSPモデル
(Bulk Synchronous Parallel )
• 分散メモリ型
• 現実に則した並列計算モデル
→ 通信時間や同期を考慮
BSP:分散メモリ型並列計算機
M1
M2
M3
・・・・・・
Mn
P1
P2
P3
・・・・・・
Pn
NETWORK
並列クイックソート
基準値を選ぶ
基準値を選ぶ
基準値を選ぶ
赤:プロセッサ1
青:プロセッサ2
緑:プロセッサ3
黄:プロセッサ4
基準値の選択法
• PRAMの場合
→ 通信時間がない
→ 基準値=中央値
• BSPの場合
→ 通信時間を考慮
→ 基準値=通信を考慮して選択
BSP上でクイックソートを行う場合の注意点
P1
内部計算時間T1
P2
内部計算時間T2
P3 内部計算時間T3
P4
通信時間S1
通信時間S2
内部計算時間T4
実行時間
T1+T2=T3+T4
S1=S2
基準値の選択
• サンプルS個を抽出
→ これを整列
→ X番目に小さい値を選ぶ
サンプル数(S)の決定
60000
58000
56000
計算量
54000
S=2
S=4
S=8
S=16
S=32
S=64
52000
50000
48000
46000
44000
42000
40000
0
1
2
4
8
16
32
64
プロセッサ数
128
256
512
図1 BSPモデルシミュレートの実験結果(L=16、g=32、X=S/2)
通信帯域幅が狭いときのシミュレーション
60000
55000
W=16
X=14
X=12
X=10
X=8
X=6
50000
計算量
45000
40000
35000
30000
25000
20000
15000
0
1
2
4
8
16
32
64
128 256 512
プロセッサ数
図2 B SPモデルシミュレートの実験結果( L= 1 6 、g= 3 2 、S= 3 2 )
X=8 1:3に分割
通信帯域幅が広いときのシミュレーション
60000
55000
50000
X=16
X=14
X=12
X=10
X=8
計算量
45000
40000
35000
30000
25000
20000
15000
10000
0
1
2
4
8
16
32
64
プロセ ッサ数
128
256
512
図6 B SPモデルシミュレート の実験結果( L= 1 6 、g= 8 )
通信帯域幅が広いときのシミュレーション
30000
28000
26000
X=16
X=14
X=12
X=10
X=8
計算量
24000
22000
20000
18000
16000
14000
12000
10000
0
1
2
4
8
16
32
64
128
256 512
プロセ ッサ数
図6 B SPモデルシミュレート の実験結果( L= 1 6 、g= 8 )
X=12 3:5
結論
• 通信帯域幅が狭くてもデータ分割
を上手く行えば高速化できる。
ダウンロード

BSPモデルを用いた 並列計算の有用性の検証