連続系アルゴリズム演習第2回スレッドモデルプロセス各スレッドはそれぞれ独立に実行される共有変数スレッド0 スレッド1 スレッド2 変数変数変数ただし、共有変数のみどのスレッドからもアクセス可能最近のプログラミング言語は、言語レベルでスレッドを実装しているなぜスレッドか  プロセスの立ち上げはコストがかかる  Linuxだとfork();  WindowsだとCreateProcess();  メモリ領域を割り当てて、コピーして、プロセスIDを割り当てて....etc.  プロセス間通信はめんどくさい  スレッドだと共有変数を使えばOK  別の手法  pipe  socket  (MPI) OpenMPの目的スレッドごとに CPUを割り当てるプロセス共有変数 CPU1 CPU2 CPU3 変数変数変数 CPUの作業分割をプログラマができる！ただし、OpenMPにはプロセッサを割り当てる機構はない (スレッドを作るだけ) スレッドを<pthread.h>よりは書きやすく環境によらずに言語実装としたのがOpenMP OpenMPの使い方1 #include <omp.h> omp.hをincludeするこの部分が並列化 int main(){ #pragma omp parallel { printf("%d\n", omp_get_threads_num()); } } 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  各スレッドで同期を取る必要性  MPIの場合と同じ  #pragma omp barrier  全てのスレッドが揃うまで待つ  デバッグをするのにも必須 OpenMPの使い方4  共有変数の書き換え  いつ書き変わるか分からない  必ず書き換えるには      #pragma #pragma #pragma #pragma などなど omp omp omp omp parallelの最初と終わり forの最後 flush barrier  あんまり共有変数を使うのはよろしくない  読んでもいいが、書き換えはまずい  読む場合も、同時に読もうとすると片方が待つ OpenMPの使い方5  Lock機構がある  これもOSでやったはず  omp_lock_tという型の変数を共有変数で作る int main(){ omp_lock_t lock; Lock変数の宣言と初期化 omp_init_lock(&lock); int k = 0; #pragma omp parallel { この間は omp_set_lock(&lock); 排他的に処理される k++; printf("%d\n", k); =速くはならない omp_unset_lock(&lock); } } OpenMPの使い方6 #pragma omp parallel for schedule(option)  ループ処理で最適化する手法  #pragma omp parallel for schedule(dynamic) for(i = 0; i < 100; i++){ function(i); 余っているプロセッサが順次投入される }  optionにはいくつかある  static, dynamic, guided, runtime...  自分で調べてみてくださいその他  もう少し細かいいろいろなことは、須田先生の解説を読むこと  これ以外のプラグマが高速化などには必要かも  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 n solution 1 1 12 14200 2 0 13 73712 3 0 14 365596 4 2 15 2279184 5 10 16 14772512 6 4 17 95815104 7 40 18 666090624 8 92 19 4968057848 9 352 20 39029188884 10 724 21 314666222712 11 2680 22 2691008701644 参考  めちゃくちゃ遅いプログラムを置いておくので、それを使っても良い  ただし、ちゃんとプロセッサを複数使って速くすること  自分で書いた方が普通は速くなる  O(n!)で作ってある  Webにもいくつか転がっているので参考にしても良い  OpenMPを使って実装してあるものはダメ  レポートにはそのことを明記すること  盗作はやめて高速化のためのヒント  1プロセッサでの高速化  盤面の対称性を利用する  bit演算にする  関数呼び出しをloopにする  並列性能を上げる  通信はあんまりさせない  終わったプロセッサには次の仕事を与える  最初からどのプロセッサがどの作業をするかを確定させない  動的に作業割り当てをする  (Bounded Buffer)  omp for