From a8c4da5b955eab2eed9ebb03ee4b1212ec6fe042 Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 20 Nov 2021 16:08:43 +0100 Subject: Multithreading seems to be working now, it was easier than expected! --- src/solve.c | 197 ++++++++++++++++++++++++++++++++++++++++++++++++++++-------- 1 file changed, 172 insertions(+), 25 deletions(-) (limited to 'src/solve.c') diff --git a/src/solve.c b/src/solve.c index 29f614b..a35a837 100644 --- a/src/solve.c +++ b/src/solve.c @@ -8,6 +8,8 @@ static void dfs_branch(Cube c, Step *s, SolveOptions *os, DfsData *dd); static bool dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd); static void dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd); static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd); +static void * instance_thread(void *arg); +static void multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d); /* Local functions ***********************************************************/ @@ -41,12 +43,24 @@ dfs(Cube c, Step *s, SolveOptions *opts, DfsData *dd) static void dfs_branch(Cube c, Step *s, SolveOptions *opts, DfsData *dd) { - Move m, l1 = dd->last1, l2 = dd->last2, *moves = dd->sorted_moves; - - int i, maxnsol = opts->max_solutions; - - for (i = 0; moves[i] != NULLMOVE && dd->sols->len < maxnsol; i++) { - m = moves[i]; + bool b = false; + int i; + Move m, l1, l2; + + l1 = dd->last1; + l2 = dd->last2; + + for (i = 0; dd->sorted_moves[i] != NULLMOVE; i++) { + /* + pthread_mutex_lock(dd->sols_mutex); + b = dd->sols->len >= opts->max_solutions; + pthread_mutex_unlock(dd->sols_mutex); + */ + + if (b) + break; + + m = dd->sorted_moves[i]; if (allowed_next(m, dd)) { dd->last2 = dd->last1; dd->last1 = m; @@ -68,8 +82,12 @@ dfs_check_solved(Step *s, SolveOptions *opts, DfsData *dd) return false; if (dd->current_alg->len == dd->d) { - if (s->is_valid(dd->current_alg) || opts->all) - append_alg(dd->sols, dd->current_alg); + if (s->is_valid(dd->current_alg) || opts->all) { + pthread_mutex_lock(dd->sols_mutex); + if (dd->sols->len < opts->max_solutions) + append_alg(dd->sols, dd->current_alg); + pthread_mutex_unlock(dd->sols_mutex); + } if (opts->verbose) print_alg(dd->current_alg, false); @@ -103,14 +121,13 @@ dfs_niss(Cube c, Step *s, SolveOptions *opts, DfsData *dd) static bool dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd) { + bool b = false; + CubeTarget ct = { .cube = c, .target = dd->d - dd->current_alg->len }; - if (dd->sols->len >= opts->max_solutions) - return true; - dd->lb = s->estimate(ct); if (opts->can_niss && !dd->niss) dd->lb = MIN(1, dd->lb); @@ -118,7 +135,131 @@ dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd) if (dd->current_alg->len + dd->lb > dd->d) return true; - return false; + pthread_mutex_lock(dd->sols_mutex); + b = dd->sols->len >= opts->max_solutions; + pthread_mutex_unlock(dd->sols_mutex); + + return b; +} + +static void * +instance_thread(void *arg) +{ + bool b; + Cube c; + ThreadData *td; + AlgListNode *node; + DfsData dd; + + td = (ThreadData *)arg; + + while (1) { + b = false; + + pthread_mutex_lock(td->start_mutex); + if ((node = *(td->node)) == NULL) + b = true; + else + *(td->node) = (*(td->node))->next; + pthread_mutex_unlock(td->start_mutex); + + if (b) + break; + + c = node->alg->inv[0] ? + apply_move(node->alg->move[0], inverse_cube(td->cube)) : + apply_move(node->alg->move[0], td->cube); + + dd.d = td->depth; + dd.m = 1; + dd.niss = node->alg->inv[0]; + dd.lb = -1; + dd.last1 = node->alg->move[0]; + dd.last2 = NULLMOVE; + dd.sols = td->sols; + dd.sols_mutex = td->sols_mutex; + dd.current_alg = new_alg(""); + append_move(dd.current_alg, node->alg->move[0], + node->alg->inv[0]); + dd.sorted_moves = td->sorted_moves; + dd.move_position = td->move_position; + +/* + pthread_mutex_lock(td->sols_mutex); + printf("Starting thread %d with move: ", td->thid); + print_alg(dd.current_alg, false); + pthread_mutex_unlock(td->sols_mutex); +*/ + + dfs(c, td->step, td->opts, &dd); + + free_alg(dd.current_alg); + } + + return NULL; +} + +static void +multidfs(Cube c, Step *s, SolveOptions *opts, AlgList *sols, int d) +{ + int i, *move_position; + Move *sorted_moves; + Alg *alg; + AlgList *start; + AlgListNode **node; + pthread_t t[opts->nthreads]; + ThreadData td[opts->nthreads]; + pthread_mutex_t *start_mutex, *sols_mutex; + + move_position = malloc(NMOVES * sizeof(int)); + sorted_moves = malloc(NMOVES * sizeof(Move)); + node = malloc(sizeof(AlgListNode *)); + start_mutex = malloc(sizeof(pthread_mutex_t)); + sols_mutex = malloc(sizeof(pthread_mutex_t)); + + start = new_alglist(); + pthread_mutex_init(start_mutex, NULL); + pthread_mutex_init(sols_mutex, NULL); + + moveset_to_list(s->moveset, sorted_moves); + movelist_to_position(sorted_moves, move_position); + for (i = 0; sorted_moves[i] != NULLMOVE; i++) { + alg = new_alg(""); + append_move(alg, sorted_moves[i], false); + append_alg(start, alg); + if (opts->can_niss) { + alg->inv[0] = true; + append_alg(start, alg); + } + free_alg(alg); + } + *node = start->first; + + for (i = 0; i < opts->nthreads; i++) { + td[i].thid = i; + td[i].cube = c; + td[i].step = s; + td[i].depth = d; + td[i].sorted_moves = sorted_moves; + td[i].move_position = move_position; + td[i].opts = opts; + td[i].start = start; + td[i].node = node; + td[i].sols = sols; + td[i].start_mutex = start_mutex; + td[i].sols_mutex = sols_mutex; + pthread_create(&t[i], NULL, instance_thread, &td[i]); + } + + for (i = 0; i < opts->nthreads; i++) + pthread_join(t[i], NULL); + + free_alglist(start); + free(node); + free(start_mutex); + free(sols_mutex); + free(move_position); + free(sorted_moves); } /* Public functions **********************************************************/ @@ -126,11 +267,12 @@ dfs_stop(Cube c, Step *s, SolveOptions *opts, DfsData *dd) AlgList * solve(Cube cube, Step *step, SolveOptions *opts) { + int d; + AlgList *sols = new_alglist(); AlgListNode *node; - DfsData dd; Cube c; - prepare_step(step, &dd); + prepare_step(step); if (step->detect != NULL) step->pre_trans = step->detect(cube); @@ -139,24 +281,29 @@ solve(Cube cube, Step *step, SolveOptions *opts) if (step->ready != NULL && !step->ready(c)) { fprintf(stderr, "Cube not ready for solving step: "); fprintf(stderr, "%s\n", step->ready_msg); - return dd.sols; + return sols; + } + + if (step->estimate((CubeTarget){.cube = c, .target = 0}) == 0 && + opts->min_moves == 0) { + append_alg(sols, new_alg("")); + return sols; } - for (dd.d = opts->min_moves; - dd.d <= opts->max_moves && - !(dd.sols->len && opts->optimal_only) && - dd.sols->len < opts->max_solutions; - dd.d++) { + for (d = MAX(1, opts->min_moves); + d <= opts->max_moves && + !(sols->len && opts->optimal_only) && + sols->len < opts->max_solutions; + d++) { if (opts->verbose) fprintf(stderr, "Found %d solutions, searching depth %d...\n", - dd.sols->len, dd.d); - dfs(c, step, opts, &dd); + sols->len, d); + multidfs(c, step, opts, sols, d); } - for (node = dd.sols->first; node != NULL; node = node->next) + for (node = sols->first; node != NULL; node = node->next) transform_alg(inverse_trans(step->pre_trans), node->alg); - free_alg(dd.current_alg); - return dd.sols; + return sols; } -- cgit v1.3