MPIとOpenMPを用いた Nクイーン問題の並列化

MPIとOpenMPを用いた
Nクイーン問題の並列化
高性能計算研究室
B4 杉田 卓司
2009/02/27
研究背景と目的
・研究背景
・扱うデータ量の増加 → 計算量の増加
・高速処理、リアルタイム処理
・目的
・MPIとOpenMPの2つの並列プログラムを
2種類のクラスタで実験、比較する
→ 実行時間、速度向上比
Nクイーン問題
1 2 3 4 5
1
●
2
●
3
●
4 ●
5
1 2 3 4 5
4 1 3 5 2
Nクイーンの配置を
●
1次元配列で表したもの
• N×Nのチェス盤上にN個のクイーンを置く
• どのクイーンもその移動可能な場所に
他のクイーンが置かれていないことが条件
• その場合の局面がいくつあるかを数える
逐次処理アルゴリズム
1 2 3 4 5
1
2●
3
4
●
5
1 2 3 4 5
1
●
2●
3
4
●
5
2 4
2 4 1
1 2 3 4 5
1 2 3 4 5
1
2●
3
4
●
5
1
2●
3
●
4
●
5
2 4
2 4 3
斜め方向に
クイーンがないため
計算続行
斜め方向に
クイーンがあるため
計算中止
並列アルゴリズム
1列目の配置に何行目のクイーンを
配置するかを4分割する。(N=14)
1
2
3
4
Process0
Process1
Process2
Process3
(1,5,9,13)
(2,6,10,14)
(3,7,11)
(4,8,12)
各プロセスの解の個数を回収して総和を求める
実験環境
Raptor
Gigabit
Ethernet
Server Host
-Xeon 2.8GHz
-2GB SDRAM
-250GB HDD
Nycto
Compute Host(6台)
-Pentium4 3.2GHz
-2GB SDRAM
-40GB HDD
Gigabit
Ethernet
Server Host
-Pentium4 3GHz
-240GB HDD
-2GB SDRAM
Compute Host(8CPU)
-Quad
Xeon 3GHz
-8GB
SDRAM
- 300GB HDD
Raptor上での実験結果
実行時間(秒)
実行時間
2500
2000
1500
1000
500
0
OpenMP
MPI
1台
2台
実行台数
4台
・OpenMP、MPI共に理想的な速度向上が得られた
・MPIの方が実行時間が短い
Nycto上での実験結果
実行時間(秒)
実行時間
2500
2000
1500
1000
500
0
OpenMP
MPI
1台
2台
4台
実行台数
8台
・OpenMP、MPI共に理想的な速度向上が得られた
・MPIの方が実行時間が短い
考察
Raptor
プロセス数
1
2
4
OpenMP
2303.
3
1153.
7
752.
7
MPI
938.6
716.9
439.
3
OpenMP
速度向上比
プロセス数
MPI
1
11
2
2
1.31
3
4
2.14
8
OpenMP
2204.
2
1298.
5
643.
9
281.
4
MPI
1863.
3
931.7
471.
4
240.
1
OpenMP
1
1.7
3.4
7.8
MPI
1
2
4
7.7
実行時間
(秒)
Nycto
実行時間
(秒)
速度向上比
・相性
・OpenMPの柔軟性
まとめと今後の課題
まとめ
・Nクイーン問題の並列化
・2つのPCクラスタでの実験、比較
今後の課題
・Nクイーン問題については高速化の余地あり
・実装までの時間を比較