連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 準備問題の定義 αβ 法 16 2 αβ 法の並列化概要 Young Brothers Wa

Size: px

Start display at page:

Download "連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 準備問題の定義 αβ 法 16 2 αβ 法の並列化概要 Young Brothers Wa"

けんじしもかさ
4 years ago
Views:

1 連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 準備問題の定義 αβ 法 16 2 αβ 法の並列化概要 Young Brothers Wait Concept 段数による逐次化適応的な待機強制終了 19 3 Cilk による並列化基本 YBWC 3.3 深さによる逐次化適応的な待機強制終了 22 4 OpenMP による並列化基本 YBWC 適応的な待機強制終了 27 Intel TBB による並列化 28.1 基本 28.2 YBWC 29.3 適応的な待機 3 6 実験設定訪問ノード数の増大逐次性能台数効果 ( スループット ) 台数効果 ( 実行時間 ) 36 7 まとめ 36

2 1 1.1,., g E(g). - (g ) E(g) = max ( E(h)) (g ) h:g h g h g h. g h., g,., g,. g,,. 1.2 αβ αβ C. 1: int eval(game_state_t g, int alpha, int beta) { 2: int moves[maxempties]; 3: int n_moves = gen_moves(g, moves); 4: if (n_moves == ) { : return g->disc_diff; 6: else { 7: int i; 8: for (i = ; i < n_moves; i++) { 9: int e = -move_and_eval(*g, i, moves[i], -beta, -alpha); : if (e > alpha) { 11: alpha = e; 12: if (e >= beta) break; 13: 14: 1: return alpha; 16: 17: g, [α, β]., α < E(g) < β E(g), E(g) α, α, E(g) β, β. β, 12. αβ,.

3 2 αβ 2.1 αβ,., αβ,.,, β, (12 ), (, α) (9 ),, 2. αβ,.,. β, ( ),, [ β, α],, α., αβ (g ),,. αβ,.,., Cilk [1, 6, ]. 2.2 Young Brothers Wait Concept, Young Brothers Wait Concept (YBWC) [2]., g h, h 1, h 2,..., h, h 1, h 2,... ( ).,, h.. (move ordering), h, i( E( h ) E( h i )), 11 α., h 1, h 2,...., h β, h 1, h 2,... β.,,..,.

4 YBWC,?, l d,. ( ) Θ(d l/2 ).,, Θ(dl)., l. d,, Θ(l log d). YBWC, h, Θ(d2 l/2 ). w, Θ(d(w + 1) l/2 )., w,., w 1,., Θ(d l/2 ), d > w + 1., YBWC (w = 1 ), w = ,,...,. Cilk, TBB, OpenMP,,.,, β,,,. αβ.,,,. 2.4 YBWC, w, w,. w, w, β,., β

5 ,.,,., h 1, h 2,...,,,,.,.,.,,,, (, ).,, β., , g h, β,, g,.,, Cilk, OpenMP, TBB. 3 Cilk 3.1 Cilk, spawn, sync, spawn.,. int eval(game_state_t g, int alpha, int beta) { int moves[maxempties]; int child_results[maxempties]; int n_moves = gen_moves(g, moves); if (n_moves == ) { return g->disc_diff; else { int i; for (i = ; i < n_moves; i++) { child_results[i] = spawn move_and_eval(*g, i, moves[i], -beta, -alpha); sync; for (i = ; i < n_moves; i++) { int e = -child_results[i];

6 if (e > alpha) { alpha = e; if (e >= beta) break; return alpha; 3.2 YBWC YBWC,, sync., w w. 1: int eval(game_state_t g, int alpha, int beta, int w) { 2: int moves[maxempties]; 3: int child_results[maxempties]; 4: int n_moves = gen_moves(g, moves); : if (n_moves == ) { 6: return g->disc_diff; 7: else { 8: int i; 9: for (i = ; i < n_moves; i++) child_results[i] = INF; : for (i = ; i < n_moves; i++) { 11: child_results[i] = spawn move_and_eval(*g, i, moves[i], -beta, -alpha); 12: if (i < w) { /* YBWC : w */ 13: sync; 14: int e = -child_results[i]; 1: if (e > alpha) { 16: alpha = e; 17: if (e >= beta) break; 18: 19: : 21: sync; 22: for (i = ; i < n_moves; i++) { 23: int e = -child_results[i]; 24: if (e > alpha) { 2: alpha = e; 26: if (e >= beta) break; 27: 28: 29: return alpha; 3:

7 31: 3.3. eval,,,., Cilk., spawn,., : for (i = ; i < n_moves; i++) { 11: child_results[i] = spawn move_and_eval(*g, i, moves[i], -beta, -alpha); 12:..., i = (x + 1), i x., i x i (x + 1), i x β. Cilk,., SYNCHED, spawn., sync. Cilk,, 11 12: if (i < w) { /* YBWC : w */ 13: sync; 14:..., 12 : if (i < w SYNCHED) { 13: sync; 14:...!, SYNCHED,. Cilk [3],. Cilk, spawn, spawn., work-first. spawn,, spawn ( ), (work stealing).,, work stealing. SYNCHED 1. SYNCHED, g,

8 h spawn h, g (h ) SYNCHED.,, , g,, β,, g. Cilk, spawn, spawn. Cilk spawn sync. spawn,. 3.4 SYNCHED, spawn,. Cilk, inlet., spawn,. inlet C., Cilk. spawn inlet, spawn., spawn f(...),, handler. inlet handler(int val, int x, int y) {... handler(spawn f(..), x, y);, inlet abort, g inlet, g., Cilk., sync inlet,,. /* g */ int eval(game_state_t g, int alpha, int beta, int w) { int moves[maxempties]; int n_moves = gen_moves(g, moves); if (n_moves == ) { return g->disc_diff; else { int i; inlet handler(int child_result, int j) { int e = -child_result;

9 if (e > alpha) { alpha = e; if (e >= beta) abort; for (i = ; i < n_moves; i++) { handler(spawn move_and_eval(*g, i, moves[i], -beta, -alpha, w), i); if (i < w SYNCHED) sync; if (alpha >= beta) break; return alpha; 4 OpenMP 4.1 OpenMP 3.. Cilk,. Cilk spawn, #pragma omp task shared(...) if(...). C,. Cilk,. shared,.,. if,,. Cilk sync, #pragma omp taskwait. Cilk spawn/sync. OpenMP, task, parallel., parallel,,., parallel, master,. #pragma omp parallel #pragma omp master, task/taskwait.

10 4.2 YBWC, Cilk spawn task, sync taskwait. 1: int eval(game_state_t g, int alpha, int beta, int w) { 2: int moves[maxempties]; 3: int child_results[maxempties]; 4: int n_moves = gen_moves(g, moves); : if (n_moves == ) { 6: return g->disc_diff; 7: else { 8: int i; 9: for (i = ; i < n_moves; i++) child_results[i] = INF; : for (i = ; i < n_moves; i++) { 11: #pragma omp task shared(child_results) 12: child_results[i] = move_and_eval(*g, i, moves[i], -beta, -alpha, w); 13: if (i < w) { /* YBWC : w */ 14: #pragma omp taskwait 1: int e = -child_results[i]; 16: if (e > alpha) { 17: alpha = e; 18: if (e >= beta) break; 19: : 21: 22: #pragma omp taskwait 23: for (i = ; i < n_moves; i++) { 24: int e = -child_results[i]; 2: if (e > alpha) { 26: alpha = e; 27: if (e >= beta) break; 28: 29: 3: return alpha; 31: 32: 33: 34: int main() { 3: #pragma omp parallel 36: #pragma omp master 37: { 38:... 39: eval(...); 4:...

11 41: 42: 4.3 OpenMP, Cilk SYNCHED. : for (i = ; i < n_moves; i++) { 11: #pragma omp task shared(child_results) 12: child_results[i] = move_and_eval(*g, i, moves[i], -beta, -alpha, w); 13: if (i < w) { /* YBWC : w */ 14: #pragma omp taskwait 1:..., if (i < w).,,,.,., : for (i = ; i < n_moves; i++) { : child_results[i] = INVALID; 11: #pragma omp task shared(child_results) 12: child_results[i] = move_and_eval(*g, i, moves[i], -beta, -alpha, w); 13 : if (i < w child_results[i]!= INVALID) { 14: #pragma omp taskwait 1:.... INVALID, move and eval ( ). ( ), GCC OpenMP (GOMP[4]),., GOMP Cilk work-first. GOMP, task,,., (parent-first ). taskwait,,.,,.,, work stealing Cilk,.,,, taskwait., h 1, h 2 (taskwait ), h 2, h 1

12 ., h 1, h 2,.,., g h, g ( h ),.,, alpha.,, alpha... alpha. 1: for (i = ; i < n_moves; i++) { 2: #pragma omp task shared(alpha) if(i>=w) 3: if (alpha < beta) { 4: int e = -move_and_eval(g, i, moves[i], -beta, -alpha, w); : omp_set_lock(&lock); 6: if (e > alpha) alpha = e; 7: omp_unset_lock(&lock); 8: 9: if (alpha >= beta) break; : 11: #pragma omp taskwait 12: return alpha; 3 if., 3, 4 alpha,., -7 alpha,,,., work stealing, parent-first if, i < w, taskwait,. 3., alpha. 4., 3 4 alpha,..,,,,,., for (i = ; i < n; i++) { #pragma omp task E(h i );

13 #pragma omp taskwait,, h n 1, h n 2,..., h..,,,., GOMP,. for i = x, moves,. 4.4 OpenMP task, Cilk abort.,,,., 1., 2. g, h, g (β ), h, g 1 3., 1,., typedef struct abort_signal { int aborting; struct abort_signal * parent; abort_signal, * abort_signal_t;., abort signal,.. 1: /* g */ 2: int eval(game_state_t g, int alpha, int beta, abort_signal_t as, int w) { 3: if (check_abort(as)) return -INF; 4: int moves[maxempties]; : int n_moves = gen_moves(g, moves); 6: if (n_moves == ) { 7: return g->disc_diff; 8: else { 9: int i; : abort_signal child_as[maxempties]; 11: for (i = ; i < n_moves; i++) { 12: child_as[i].parent = as; 13: child_as[i].aborting = ;

14 14: #pragma omp task shared(alpha, as, child_as) 1: if (alpha < beta) { 16: int e = -move_and_eval(g, i, moves[i], -beta, -alpha_, &child_as[i], w); 17: omp_set_lock(&lock); 18: if (e > alpha) alpha = e; 19: if (e >= beta) as[i].aborting = 1; : omp_unset_lock(&lock); 21: 22: if (alpha >= beta) break; 23: 24: #pragma omp taskwait 2: return alpha; 26: 27: check abort,. int check_abort(abort_signal_t as) { abort_signal_t p; for (p = as; p; p = p->parent) if (p->aborting) return 1; return ;,,.,,.,., 3.3,. Intel TBB.1 Intel TBB,, task, execute., spawn()., Cilk spawn/sync, OpenMP task/taskwait, task group. task group, run() wait(),., run(), operator(), task handle, C++ C++x

15 ,,. GCC, -std=c++x., OpenMP task.. 1: #include <tbb/task_group.h> 2: using namespace tbb; 3: 4: int fib(int n) { : if (n < 2) return 1; 6: else { 7: task_group tg; 8: int x, y; 9: tg.run([=,&x] { x = fib(n - 1); ); : y = fib(n - 2); 11: tg.wait(); 12: return x + y; 13: 14: 1: 16: int main(int argc, char ** argv) { 17: int n = atoi(argv[1]); 18: int x= fib(n); 19: printf("fib(%d) = %d\n", n, x); : GCC ( <tbb dir> TBB ). g++ -std=c++x -I<tbb_dir>/include fib.cc -L<tbb_dir>/lib -ltbb, 9: tg.run([=,&x] { x = fib(n - 1); );, [=,&x] { x = fib(n - 1); C++x ( ). [=,&x], &x, x =. OpenMP task, shared(x)..2 YBWC YBWC, OpenMP task/taskwait, task group run/wait.

16 1: int eval(game_state_t g, int alpha, int beta, int w) { 2: int moves[maxempties]; 3: int child_results[maxempties]; 4: int n_moves = gen_moves(g, moves); : if (n_moves == ) { 6: return g->disc_diff; 7: else { 8: int ii; 9: task_group tg; : for (ii = ; ii < n_moves; ii++) child_results[ii] = INF; 11: for (ii = ; ii < n_moves; ii++) { 12: int i = (ii < w? ii : n_moves - ii + w - 1); 13: tg.run([=,&child_results] 14: { child_results[i] = move_and_eval(*g, i, moves[i], -beta, -alpha, w); ); 1: if (i < w) { /* YBWC : w */ 16: tg.wait(); 17: int e = -child_results[i]; 18: if (e > alpha) { 19: alpha = e; : if (e >= beta) break; 21: 22: 23: 24: /* */ 2: tg.wait(); 26: for (ii = ; ii < n_moves; ii++) { 27: int e = -child_results[ii]; 28: if (e > alpha) { 29: alpha = e; 3: if (e >= beta) break; 31: 32: 33: return alpha; 34: 3: TBB, i >= w,.,, 11: int i = (ii < w? ii : n_moves - ii + w - 1);.

Cilk SYNCHED, GOMP, parent-first. OpenMP,,.

$n_moves; ii++) { int i = (ii < w?$ $run([=,&alpha,&lock_] { if (alpha < beta) { int e$ = -move_and_eval(g, i, moves[i], -beta, -alpha,

17 : ( )...3 TBB, OpenMP. Cilk SYNCHED, GOMP, parent-first. OpenMP,,. OpenMP,. task_group tg; spin_mutex lock_; for (ii = ; ii < n_moves; ii++) { int i = (ii < w? ii : n_moves - ii + w - 1); tg.run([=,&alpha,&lock_] { if (alpha < beta) { int e = -move_and_eval(g, i, moves[i], -beta, -alpha, w); spin_mutex::scoped_lock lock(lock_); if (e > alpha) alpha = e; ); if (i < w) tg.wait(); if (alpha >= beta) break; tg.wait(); return alpha;, OpenMP ,, Andersson The FFO endgame test suite ( 6,,,.

18 Legend adaptive w=1 adaptive w=2 abort w=1 abort w= : 3-. adaptive 2.4, abort 2.. w, 2.2,.,, 4, 47 ( 6, 2 ). 24 (48 ). CPU: Intel Nehalem-EX (E74) 2.GHz (6 core/12 4 ) L3 cache: 18MB memory: 24GB DDR3 6.2,., ( ). ( 6 ) , Cilk, OpenMP, TBB,,,,., 12 (w) 1 2

19 Legend Visited nodes blow up of Cilk (Problem 41) adaptive w=1 adaptive w=2 abort w=1 abort w= visited nodes Visited nodes blow up of OpenMP (Problem 41) Visited nodes blow up of Intel TBB (Problem 41) visited nodes visited nodes Visited nodes blow up of Cilk (Problem 47) Visited nodes blow up of OpenMP (Problem 47) visited nodes visited nodes visited nodes Visited nodes blow up of Intel TBB (Problem 47) : ( 41,47)

20 , 2 2 = 4..,,., ,,., ( YBWC w = 2 ),, ( ),.. 6.3, 41,, w ( ), 1. 12,. C (Andersson), 2 C,, C. C (Andersson) % - %, C %,. w C (Andersson) C Cilk abort Cilk abort Cilk adaptive Cilk adaptive OpenMP abort OpenMP abort OpenMP adaptive OpenMP adaptive Intel TBB abort Intel TBB abort Intel TBB adaptive Intel TBB adaptive ( ) 6.2,., ,,., w,.

21 Legend Throughput increase of Cilk (Problem 41) adaptive w=1 adaptive w=2 abort w=1 abort w= throughput up Throughput increase of OpenMP (Problem 41) Throughput increase of Intel TBB (Problem 41) throughput up throughput up Throughput increase of Cilk (Problem 47) Throughput increase of OpenMP (Problem 47) throughput up throughput up Throughput increase of Intel TBB (Problem 47) throughput up : ( 41, 47)

22 6. ( ), Andersson,., 3, 6.3, 4.,,, w = 2., , αβ. YBWC:, : :,.,,,,., work-first parent-first,,,,. Cilk OpenMP Intel TBB YBWC spawn, sync task, taskwait task group, run, wait work-first parent-first (GCC) parent-first SYNHCED, shared [&x] work-first inlet, abort,. [1] Don Dailey and Charles E. Leiserson. Using cilk to write multiprocessor chess programs. In Advances in Computer Games 9, 1. [2] Rainer Feldmann. Game Tree Search on Massively Parallel Systems. PhD thesis, University of Paderborn, [3] Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. The implementation of the cilk- multithreaded language. In ACM SIGPLAN Conference on Programming Language, pages , 1998.

23 Legend Absolute speedup of Cilk (Problem 41) adaptive w=1 adaptive w=2 abort w=1 abort w= Speedup to Andersson Absolute speedup of OpenMP (Problem 41) Absolute speedup of Intel TBB (Problem 41) Speedup to Andersson Speedup to Andersson Absolute speedup of Cilk (Problem 47) Absolute speedup of OpenMP (Problem 47) Speedup to Andersson Speedup to Andersson Absolute speedup of Intel TBB (Problem 47) Speedup to Andersson : Andersson ( 41, 47)

24 [4] GOMP an OpenMP implementation for GCC. [] Christopher F. Joerg and Bradley C. Kuszmaul. Massively parallel chess. In the Third DIMACS Parallel Implementation Challenge, [6] Bradley C. Kuszmaul. The startech massively parallel chess program. Journal of the International Computer Chess Association, 18(1), 199.

連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 概要 17 2 ゲーム木探索必勝必敗引き分け盤面の評価値 αβ 法指し手の順序付け (mo

連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 概要 17 2 ゲーム木探索 17 2.1 必勝必敗引き分け 17 2.2 盤面の評価値 18 2.3 αβ 法 19 2.4 指し手の順序付け (move ordering) 20 3 Andersson の詰み探索およびその並列化 21 3.1 Andersson

連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化 田浦健次朗 東京大学大学院情報理工学系研究科, 情報基盤センター 目次 1 準備 問題の定義 αβ 法 16 2 αβ 法の並列化 概要 Young Brothers Wa

連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 準備問題の定義 αβ 法 16 2 αβ 法の並列化概要 Young Brothers Wa