連続系アルゴリズム演習 第2回 OpenMPによる課題

スレッドモデル プロセス 各スレッドはそれぞれ 独立に実行される ただし、共有変数のみ どのスレッドからも アクセス可能 共有変数 スレッド0 スレッド1 スレッド2 変数 変数 変数 最近のプログラミング言語は、 言語レベルで スレッドを実装している

なぜスレッドか プロセスの立ち上げはコストがかかる プロセス間通信はめんどくさい Linuxだとfork(); WindowsだとCreateProcess(); メモリ領域を割り当てて、コピーして、プロセスIDを割り当てて....etc. プロセス間通信はめんどくさい スレッドだと共有変数を使えばOK 別の手法 pipe socket (MPI)

OpenMPの目的 プロセス スレッドごとに CPUを割り当てる 共有変数 CPUの作業分割を プログラマができる！ CPU1 CPU2 プロセッサを割り当てる 機構はない (スレッドを作るだけ) スレッドを<pthread.h>よりは書きやすく 環境によらずに言語実装としたのがOpenMP

OpenMPの使い方1 #include <omp.h> int main(){ #pragma omp parallel { printf("%d\n", omp_get_threads_num()); } omp.hをincludeする この部分が並列化 omp.hで定義されてる関数

OpenMPの使い方2 プロセス #include <omp.h> int main(){ int common_var; #pragma omp parallel { int k; } int common_var; スレッド0 スレッド1 スレッド2 int k; int k; int k; 定義する場所で共有変数か スレッド私有変数かが決まる

OpnMPの使い方3 各スレッドで同期を取る必要性 #pragma omp barrier MPIの場合と同じ 全てのスレッドが揃うまで待つ デバッグをするのにも必須

OpenMPの使い方4 共有変数の書き換え いつ書き変わるか分からない 必ず書き換えるには あんまり共有変数を使うのはよろしくない #pragma omp parallelの最初と終わり #pragma omp forの最後 #pragma omp flush #pragma omp barrier などなど あんまり共有変数を使うのはよろしくない 読んでもいいが、書き換えはまずい 読む場合も、同時に読もうとすると片方が待つ

OpenMPの使い方5 Lock機構がある これもOSでやったはず omp_lock_tという型の変数を共有変数で作る int main(){ omp_lock_t lock; omp_init_lock(&lock); int k = 0; #pragma omp parallel { omp_set_lock(&lock); k++; printf("%d\n", k); omp_unset_lock(&lock); } Lock変数の宣言と初期化 この間は 排他的に処理される =速くはならない

OpenMPの使い方6 #pragma omp parallel for schedule(option) ループ処理で最適化する手法 static, dynamic, guided, runtime... 自分で調べてみてください #pragma omp parallel for schedule(dynamic) for(i = 0; i < 100; i++){ function(i); } 余っているプロセッサが順次投入される

その他 もう少し細かいいろいろなことは、須田先生の解説を読むこと Web上にはほかにも資料がある OpenMPの書籍はあんまりない これ以外のプラグマが高速化などには必要かも Web上にはほかにも資料がある OpenMPで検索してくださいな OpenMPの書籍はあんまりない ギリギリ石川先生の本があったりする 後はFortranとか

課題 OpenMPを用いてN-queens問題を解くプログラムを実装せよ nの値を変えて時間を測定すること n×nの升目の場合に、解の個数を調べる 事前に準備とかしないこと！ それぞれの解を出力する必要は特にない nの値を変えて時間を測定すること そんなにたくさんのnを使う必要は別にない 適度に時間のかかる3つくらいの値を使えば良い p(スレッド数)を変えて時間を測定すること 並列化効率などの考察をすること(一番重要)

N-Queens Problem チェスのQueenを配置する Queen同士が攻撃できない配置にする 将棋で言うところの飛車+角 Queen同士が攻撃できない配置にする n×nの升目に、n個のQueenを配置する 何通りの配置がありうるか

N-Queens Problem 置ける場所 が減る 左上に置く 右から2番目 上から2番目に置く 4×4の升目に、 3つしか置けなかった 失敗

N-Queens Problem n=4の時の解 n=5の時 10種類 n=6の時 or 4種類 n=7の時 2種類 40種類

解のリスト n solution 1 2 3 4 5 10 6 7 40 8 92 9 352 724 11 2680 n solution 3 4 5 10 6 7 40 8 92 9 352 724 11 2680 n solution 12 14200 13 73712 14 365596 15 2279184 16 14772512 17 95815104 18 666090624 19 4968057848 20 39029188884 21 314666222712 22 2691008701644

参考 めちゃくちゃ遅いプログラムを置いておくので、それを使っても良い Webにもいくつか転がっているので参考にしても良い ただし、ちゃんとプロセッサを複数使って速くすること 自分で書いた方が普通は速くなる O(n!)で作ってある Webにもいくつか転がっているので参考にしても良い OpenMPを使って実装してあるものはダメ レポートにはそのことを明記すること 盗作はやめて

高速化のためのヒント 1プロセッサでの高速化 並列性能を上げる 盤面の対称性を利用する bit演算にする 関数呼び出しをloopにする 通信はあんまりさせない 終わったプロセッサには次の仕事を与える 最初からどのプロセッサがどの作業をするかを確定させない 動的に作業割り当てをする (Bounded Buffer) omp for