MPIとOpenMPを用いた Nクイーン問題の並列化 高性能計算研究室 Ｂ４ 杉田 卓司 ２００９/０２/２７
研究背景と目的 ・研究背景 ・扱うデータ量の増加 → 計算量の増加 ・高速処理、リアルタイム処理 ・目的 ・扱うデータ量の増加 → 計算量の増加 ・高速処理、リアルタイム処理 ・目的 ・MPIとOpenMPの２つの並列プログラムを ２種類のクラスタで実験、比較する → 実行時間、速度向上比 気象予測 デジタル画像処理
Nクイーン問題 ５ ４ ３ ２ １ ● N×Nのチェス盤上にN個のクイーンを置く どのクイーンもその移動可能な場所に １次元配列で表したもの 列番号→要素番号 行番号→要素の値 N×Nのチェス盤上にN個のクイーンを置く どのクイーンもその移動可能な場所に 他のクイーンが置かれていないことが条件 その場合の局面がいくつあるかを数える
逐次処理アルゴリズム 斜め方向に クイーンがないため 計算続行 クイーンがあるため 計算中止 Ｎの数を１６で計算した場合、解の総数は約１４７７万通りにもおよぶ→並列処理○
並列アルゴリズム １ ３ ２ ４ 1列目の配置に何行目のクイーンを配置するかを４分割する。（Ｎ＝14） 各プロセスの解の個数を回収して総和を求める １ ３ ２ ４ Ｐｒｏｃｅｓｓ０ （1，5，9，13） Ｐｒｏｃｅｓｓ１ （2，6，10，14） Ｐｒｏｃｅｓｓ２ （3，7，11） Ｐｒｏｃｅｓｓ３ （4，8，12） １列目のどの位置にクイーンを配置するかをプロセス毎に指定して処理を並列に割り当てる。
実験環境 Ｒａｐｔｏｒ Ｎｙｃｔｏ Server Host - Xeon 2.8GHz 2GB SDRAM 250GB HDD Compute Host （６台） Pentium4 3.2GHz 40GB HDD Gigabit Ethernet Ｒａｐｔｏｒ、ＭＰＩ→分散メモリ型 Ｎｙｃｔｏ、ＯｐｅｎＭＰ→共有メモリ型 ＯｐｅｎＭＰが分散メモリ上で動くためにＳＣｏｒｅ上のＳＣＡＳＨというシステムに よって共有メモリと見せかけて動かす Ｎｙｃｔｏ Gigabit Ethernet - Pentium4 3GHz Server Host 2GB SDRAM 240GB HDD Compute Host(8CPU) Quad Xeon 3GHz 8GB SDRAM 300GB HDD
Ｒａｐｔｏｒ上での実験結果 ・ＯｐｅｎＭＰ、ＭＰＩ共に理想的な速度向上が得られた ・ＭＰＩの方が実行時間が短い
Ｎｙｃｔｏ上での実験結果 ・ＯｐｅｎＭＰ、ＭＰＩ共に理想的な速度向上が得られた ・ＭＰＩの方が実行時間が短い
考察 Ｒａｐｔｏｒ Ｎｙｃｔｏ ・相性 ・ＯｐｅｎＭＰの柔軟性 プロセス数 1 2 4 実行時間（秒） ＯｐｅｎＭＰ 2303.3 1153.7 752.7 ＭＰＩ 938.6 716.9 439.3 速度向上比 3 1.31 2.14 プロセス数 1 2 4 8 実行時間（秒） ＯｐｅｎＭＰ 2204.2 1298.5 643.9 281.4 ＭＰＩ 1863.3 931.7 471.4 240.1 速度向上比 1.7 3.4 7.8 7.7 Ｎｙｃｔｏ ＯｐｅｎＭＰ 共有 Ｒａｐｔｏｒ 分散 ＭＰＩ 分散 Ｎｙｃｔｏ 共有 ・相性 ・ＯｐｅｎＭＰの柔軟性
まとめと今後の課題 まとめ ・Ｎクイーン問題の並列化 ・２つのＰＣクラスタでの実験、比較 今後の課題 ・Ｎクイーン問題については高速化の余地あり ・実装までの時間を比較