スライド 1 - Oyanagi Laboratory WWW Server

連続系アルゴリズム演習第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

Download Report