囲碁のC、C++言語のプログラミングについての質問です。

Question

OpenMPを使用して以下のプログラムを並列化したいと考えております。
その並列化の手法が”Tree並列化”というもので、概要はわかったのですが、
プログラムへの実装方法が全くわからず、手が止まっている状態です。
よろしければご教授いただきたく思います。
以下にTree並列化の概要と並列化したいプログラムを書いておきます。

※Tree並列化とは、１つの探索木を持ち、個々のスレッドがばらばらにUCTの木を降りてプレイアウトを行う。
個々のスレッドが探索木を参照、変更するときにロックを変更する必要があるが、
これを木全体をロックすると効率が下がるので局面ごとでロックを行う。

・Tree並列化したいプログラム
http://www1.axfc.net/u/3530598

どうかよろしくお願い致します。

Answer 1

そもそも一つの盤のデータだけで実装するのではなく、最初は1手か2手先であり得る全ての盤の状態を配列にして、それにたいしてforループで探索して、最後に結果を統合するようにするといいと思います。

int board[BOARD_MAX];
int baords[][BOARD_MAX];
double win_rate[];
double result;
int board_cnt = 0;

for( y=0 ; y<B_SIZE ; ++y ){
    for( x=0 ; x<B_SIZE ; ++x ){
        if( can_put( x , y , board) ){
            boards[board_cnt++] = put( x , y , board );
        }
    }
}

#pragma omp parallel for
for( i = 0 ; i<board_cnt ; ++i){
    win_rate[i] = search_tree(boards[i]);
}

//reduction
#pragma omp parallel for reduction(+:result)
for( i=0 ; i<board_cnt ; ++i ){
    result += win_rate[i];
}

Comments

[yosuke0313]

投稿者です。ご回答ありがとうございます。

仰ることはよくわかったのですが、いざプログラムに実装しようとしましたら、新しく関数を置くその関数の中身など考えてみたのですが結果上手く動かない状態になってしまいました。

プログラミングの知識が乏しく申し訳ないのですが、その辺りも詳しく教えて頂けないでしょうか？

[_nyannyan_]

ソースコードをサクッとみた感じ591行目がOpenMPで並列化するのにいいと思います。
search_uctの中ではグローバル変数にアクセスしないように変更したら並列化できると思います。
619行目のforループのMAX処理なのでここも並列化できると思います。
http://www.techdarting.com/2013/06/openmp-min-max-reduction-code.html

並列化に限らないのですが、変数はなるべく有効範囲が狭くなるようにスコープが狭くなるようにするとやりやすいですよ。
int kifu[1000]はmain関数の中からしかアクセスしていないのでmainの中で宣言しても他への影響が少なくなります。関数のメモリアクセスが関数内の変数にのみ限定されていると並列化が簡単になります。

[yosuke0313]

投稿者です。回答ありがとうございます。

OpenMPで並列すべき場所、そしてどう並列化するかはおおまかに決まりました。
本当にありがとうございます。

OpenMPをもう少し勉強し、コードを書き進めてみようと思います。
また何か質問するときはぜひともよろしくお願い致します。