From bd377a962f0b777f76c7cc74fb6b82797264edb2 Mon Sep 17 00:00:00 2001 From: Jean-loup Gailly Date: Tue, 12 Jan 2010 21:30:57 +0100 Subject: [PATCH] Revert "Use local test&set instead of global mutex to expand a node" to do it again in multiple commits. This reverts commit 7cb9686ecf7ab6c09ffe42ada5019e2554348942. --- uct/tree.c | 23 ++++++++--------------- uct/tree.h | 15 +++++---------- uct/uct.c | 11 ++--------- uct/walk.c | 16 ++++++++-------- 4 files changed, 23 insertions(+), 42 deletions(-) diff --git a/uct/tree.c b/uct/tree.c index 8cee67b..1c73e8a 100644 --- a/uct/tree.c +++ b/uct/tree.c @@ -17,7 +17,7 @@ #include "uct/prior.h" #include "uct/tree.h" -/* This function may be called by multiple threads in parallel */ + static struct tree_node * tree_init_node(struct tree *t, coord_t coord, int depth) { @@ -26,11 +26,10 @@ tree_init_node(struct tree *t, coord_t coord, int depth) fprintf(stderr, "tree_init_node(): OUT OF MEMORY\n"); exit(1); } - __sync_fetch_and_add(&t->node_sizes, sizeof(*n)); n->coord = coord; n->depth = depth; - volatile static long c = 1000000; - n->hash = __sync_fetch_and_add(&c, 1) - 1; + static long c = 1000000; + n->hash = c++; if (depth > t->max_depth) t->max_depth = depth; return n; @@ -45,6 +44,7 @@ tree_init(struct board *board, enum stone color) t->root = tree_init_node(t, pass, 0); t->root_symmetry = board->symmetry; t->root_color = stone_other(color); // to research black moves, root will be white + pthread_mutex_init(&t->expansion_mutex, NULL); return t; } @@ -59,7 +59,6 @@ tree_done_node(struct tree *t, struct tree_node *n) ni = nj; } free(n); - t->node_sizes -= sizeof(*n); // atomic operation not needed here } void @@ -199,12 +198,10 @@ tree_node_load(FILE *f, struct tree_node *node, int *num) if (node->amaf.playouts > MAX_PLAYOUTS) { node->amaf.playouts = MAX_PLAYOUTS; } -#ifdef ROOT_PARALLEL - // Code needed only for thread_model=root which is much worse - // than treevl. I suggest removing this model entirely. + memcpy(&node->pamaf, &node->amaf, sizeof(node->amaf)); memcpy(&node->pu, &node->u, sizeof(node->u)); -#endif + struct tree_node *ni = NULL, *ni_prev = NULL; while (fgetc(f)) { ni_prev = ni; ni = calloc(1, sizeof(*ni)); @@ -262,7 +259,7 @@ tree_copy(struct tree *tree) return t2; } -#ifdef ROOT_PARALLEL + static void tree_node_merge(struct tree_node *dest, struct tree_node *src) { @@ -360,7 +357,6 @@ tree_normalize(struct tree *tree, int factor) { tree_node_normalize(tree->root, factor); } -#endif // ROOT_PARALLEL /* Get a node of given coordinate from within parent, possibly creating it @@ -445,8 +441,7 @@ tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum s /* Now, create the nodes. */ struct tree_node *ni = tree_init_node(t, pass, node->depth + 1); - struct tree_node *first_child = ni; - ni->parent = node; + ni->parent = node; node->children = ni; ni->prior = map.prior[pass]; ni->d = TREE_NODE_D_MAX + 1; /* The loop considers only the symmetry playground. */ @@ -480,8 +475,6 @@ tree_expand_node(struct tree *t, struct tree_node *node, struct board *b, enum s ni->d = distances[c]; } } - // Must set children only after everything else is properly initialized - node->children = first_child; } diff --git a/uct/tree.h b/uct/tree.h index 643fa0d..a4c14a0 100644 --- a/uct/tree.h +++ b/uct/tree.h @@ -41,19 +41,11 @@ struct tree_node { struct move_stats prior; /* XXX: Should be way for policies to add their own stats */ struct move_stats amaf; -#ifdef ROOT_PARALLEL - /* Stats before starting playout; used for multi-thread normalization. - * Commented by default to save memory, only needed for thread_model=root */ + /* Stats before starting playout; used for multi-thread normalization. */ struct move_stats pu, pamaf; -#endif #define TREE_HINT_INVALID 1 // don't go to this node, invalid move int hints; - - // In case multiple threads walk the tree, this lock is used - // to prevent them from expanding the same node in parallel. - // The first thread setting this lock expands the node. - int expansion_lock; }; struct tree { @@ -63,13 +55,16 @@ struct tree { enum stone root_color; float extra_komi; + // In case multiple threads walk the tree, this mutex is used + // to prevent them from expanding the same node in parallel. + pthread_mutex_t expansion_mutex; + // Summary statistics of good black, white moves in the tree struct move_stats *chvals; // [bsize2] root children struct move_stats *chchvals; // [bsize2] root children's children // Statistics int max_depth; - volatile long node_sizes; // byte size of all allocated nodes }; struct tree *tree_init(struct board *board, enum stone color); diff --git a/uct/uct.c b/uct/uct.c index fae3bd2..fe9c3c3 100644 --- a/uct/uct.c +++ b/uct/uct.c @@ -166,9 +166,8 @@ uct_chat(struct engine *e, struct board *b, char *cmd) return "no game context (yet?)"; enum stone color = u->t->root_color; struct tree_node *n = u->t->root; - snprintf(reply, 1024, "In %d playouts, %s %s can win with %.2f%% probability", - n->u.playouts * (u->thread_model == TM_ROOT ? u->threads : 1), - stone2str(color), coord2sstr(n->coord, b), + snprintf(reply, 1024, "In %d*%d playouts, %s %s can win with %.2f%% probability", + n->u.playouts, u->threads, stone2str(color), coord2sstr(n->coord, b), tree_node_get_value(u->t, -1, n->u.value) * 100); if (abs(u->t->extra_komi) >= 0.5) { sprintf(reply + strlen(reply), ", while self-imposing extra komi %.1f", @@ -307,12 +306,10 @@ uct_playouts_parallel(struct uct *u, struct board *b, enum stone color, struct t pthread_join(threads[finish_thread], (void **) &ctx); played_games += ctx->games; joined++; -#ifdef ROOT_PARALLEL if (!shared_tree) { tree_merge(t, ctx->t); tree_done(ctx->t); } -#endif free(ctx); if (UDEBUGL(2)) fprintf(stderr, "Joined thread %d\n", finish_thread); @@ -323,12 +320,10 @@ uct_playouts_parallel(struct uct *u, struct board *b, enum stone color, struct t } pthread_mutex_unlock(&finish_mutex); -#ifdef ROOT_PARALLEL if (!shared_tree) { /* XXX: Should this be done in shared trees as well? */ tree_normalize(t, u->threads); } -#endif return played_games; } @@ -566,7 +561,6 @@ uct_state_init(char *arg, struct board *b) if (!strcasecmp(optval, "none")) { /* Turn off multi-threaded reading. */ u->thread_model = TM_NONE; -#ifdef ROOT_PARALLEL } else if (!strcasecmp(optval, "root")) { /* Root parallelization - each thread * does independent search, trees are @@ -574,7 +568,6 @@ uct_state_init(char *arg, struct board *b) u->thread_model = TM_ROOT; u->parallel_tree = false; u->virtual_loss = false; -#endif } else if (!strcasecmp(optval, "tree")) { /* Tree parallelization - all threads * grind on the same tree. */ diff --git a/uct/walk.c b/uct/walk.c index df09c5a..998622f 100644 --- a/uct/walk.c +++ b/uct/walk.c @@ -19,8 +19,6 @@ #include "uct/uct.h" #include "uct/walk.h" -// This should become a dynamic parameter. 7G is suitable for 20k*23 threads. -#define MAX_NODE_SIZES (7L*1024*1024*1024) float uct_get_extra_komi(struct uct *u, struct board *b) @@ -41,7 +39,6 @@ uct_progress_status(struct uct *u, struct tree *t, enum stone color, int playout fprintf(stderr, "... No moves left\n"); return; } - fprintf(stderr, "node sizes %ldM\n", t->node_sizes/1000000); fprintf(stderr, "[%d] ", playouts); fprintf(stderr, "best %f ", tree_node_get_value(t, 1, best->u.value)); @@ -94,7 +91,7 @@ uct_leaf_node(struct uct *u, struct board *b, enum stone player_color, { enum stone next_color = stone_other(node_color); int parity = (next_color == player_color ? 1 : -1); - if (n->u.playouts >= u->expand_p && t->node_sizes < MAX_NODE_SIZES) { + if (n->u.playouts >= u->expand_p) { // fprintf(stderr, "expanding %s (%p ^-%p)\n", coord2sstr(n->coord, b), n, n->parent); if (!u->parallel_tree) { /* Single-threaded, life is easy. */ @@ -105,10 +102,13 @@ uct_leaf_node(struct uct *u, struct board *b, enum stone player_color, * threads to meet in the same node, the latter * one will simply do another simulation from * the node itself, no big deal. */ - if (!__sync_lock_test_and_set(&n->expansion_lock, 1) && - tree_leaf_node(n) && t->node_sizes < MAX_NODE_SIZES) { - tree_expand_node(t, n, b, next_color, u, parity); - } + pthread_mutex_lock(&t->expansion_mutex); + if (tree_leaf_node(n)) { + tree_expand_node(t, n, b, next_color, u, parity); + } else { + // fprintf(stderr, "cancelling expansion, thread collision\n"); + } + pthread_mutex_unlock(&t->expansion_mutex); } } if (UDEBUGL(7)) -- 2.11.4.GIT