From 0478efe2875420236295450ba2d4d22dd5dd433e Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Thu, 19 Sep 2024 09:51:43 +0200 Subject: pthread solver to fix --- .gitignore | 4 + src/nissy.c | 5 +- src/solvers/h48/h48.h | 1 + src/solvers/h48/thread.h | 335 +++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 343 insertions(+), 2 deletions(-) create mode 100644 src/solvers/h48/thread.h diff --git a/.gitignore b/.gitignore index c2ff877..eaaa09e 100644 --- a/.gitignore +++ b/.gitignore @@ -1,13 +1,17 @@ +.DS_Store config.mk gen debuggen +utils/.DS_Store perf.data perf.data.old run tables/* test/*/runtest +test/.DS_Store test/run test/run.DSYM +tools/.DS_Store run.DSYM test/last.* tools/results diff --git a/src/nissy.c b/src/nissy.c index 6bc4aea..5eeb457 100644 --- a/src/nissy.c +++ b/src/nissy.c @@ -332,8 +332,9 @@ nissy_solve( LOG("gendata: could not parse options\n"); ret = -1; } else { - ret = solve_h48(c, minmoves, maxmoves, maxsolutions, - data, solutions); + ret = THREADS > 1 ? + solve_h48_parent(c, minmoves, maxmoves, maxsolutions, data, solutions) : + solve_h48(c, minmoves, maxmoves, maxsolutions, data, solutions); } } else if (!strcmp(solver, "h48stats")) { ret = solve_h48stats(c, maxmoves, data, solutions); diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h index 4edc5ac..ee865d9 100644 --- a/src/solvers/h48/h48.h +++ b/src/solvers/h48/h48.h @@ -3,3 +3,4 @@ #include "gendata_cocsep.h" #include "gendata_h48.h" #include "solve.h" +#include "thread.h" diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h new file mode 100644 index 0000000..1eade29 --- /dev/null +++ b/src/solvers/h48/thread.h @@ -0,0 +1,335 @@ +#include +#include +#include +#include +#include + +#define MAX_QUEUE_SIZE 500 + +typedef struct +{ + dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE]; + int front; + int rear; + int tasks_count; + pthread_mutex_t mutex; + pthread_cond_t cond; + atomic_int active_tasks; + pthread_mutex_t active_tasks_mutex; + pthread_cond_t active_tasks_cond; +} task_queue_t; + +STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); +STATIC void init_queue(task_queue_t *); +STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t *); +STATIC void copy_queue(task_queue_t *, task_queue_t *, int); +STATIC dfsarg_solveh48_t *get_task(task_queue_t *); +STATIC void *start_thread(void *); +STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *); +STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *); +STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void *, char *); + +STATIC void +solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq){ + pthread_mutex_lock(&tq->mutex); + int strl; + uint8_t invertedpremoves[MAXLEN]; + char *solution = *arg->nextsol; + + strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); + *arg->nextsol += strl; + + if (arg->npremoves) + { + **arg->nextsol = ' '; + (*arg->nextsol)++; + + invertmoves(arg->premoves, arg->npremoves, invertedpremoves); + strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); + *arg->nextsol += strl; + } + LOG("Solution found: %s\n", solution); + + **arg->nextsol = '\n'; + (*arg->nextsol)++; + (*arg->nsols)++; + pthread_mutex_unlock(&tq->mutex); +} + +STATIC void +init_queue(task_queue_t *queue) +{ + queue->front = 0; + queue->rear = 0; + queue->tasks_count = 0; + pthread_mutex_init(&queue->mutex, NULL); + pthread_cond_init(&queue->cond, NULL); +} + +STATIC void +submit_task(task_queue_t *queue, dfsarg_solveh48_t *task) +{ + pthread_mutex_lock(&queue->mutex); + queue->tasks[queue->rear] = task; + queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; + queue->tasks_count++; + pthread_cond_signal(&queue->cond); + pthread_mutex_unlock(&queue->mutex); +} + +STATIC void +copy_queue(task_queue_t *src, task_queue_t *dest, int depth) +{ + pthread_mutex_lock(&src->mutex); + pthread_mutex_lock(&dest->mutex); + for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE) + { + if (src->tasks[i] != NULL) + { + dest->tasks[i] = src->tasks[i]; + dest->tasks[i]->depth = depth; + } + } + dest->front = src->front; + dest->rear = src->rear; + dest->tasks_count = src->tasks_count; + pthread_mutex_unlock(&src->mutex); + pthread_cond_signal(&dest->cond); + pthread_mutex_unlock(&dest->mutex); +} +STATIC dfsarg_solveh48_t * +get_task(task_queue_t *queue) +{ + pthread_mutex_lock(&queue->mutex); + while (queue->tasks_count == 0) + { + pthread_cond_wait(&queue->cond, &queue->mutex); + } + dfsarg_solveh48_t *task = queue->tasks[queue->front]; + queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; + queue->tasks_count--; + pthread_mutex_unlock(&queue->mutex); + return task; +} + +STATIC void * +start_thread(void *arg) +{ + task_queue_t *queue = (task_queue_t *)arg; + while (true) + { + dfsarg_solveh48_t *task = get_task(queue); + if (task == NULL) + { + break; + } + solve_h48_single(task, queue); + free(task); + + pthread_mutex_lock(&queue->active_tasks_mutex); + atomic_fetch_sub(&queue->active_tasks, 1); + if (atomic_load(&queue->active_tasks) == 0) + { + pthread_cond_signal(&queue->active_tasks_cond); + } + pthread_mutex_unlock(&queue->active_tasks_mutex); + } + return NULL; +} + +STATIC int64_t +solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) +{ + dfsarg_solveh48_t queue[MAX_QUEUE_SIZE]; + int front = 0, rear = 0; + dfsarg_solveh48_t nextarg; + int depth = 0; + int nodes_at_current_depth = 1; + int nodes_at_next_depth = 0; + + queue[rear++] = *arg_zero; + + while (front < rear) + { + dfsarg_solveh48_t arg = queue[front++]; + nodes_at_current_depth--; + + if (*arg.nsols == arg.maxsolutions) + return 1; + + if (issolved(arg.cube)) + { + if (arg.nmoves + arg.npremoves != arg.depth) + continue; + solve_h48_appendsolution(&arg); + continue; + } + + arg.nissbranch = MM_NORMAL; + uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch); + + for (uint8_t m = 0; m < 18; m++) + { + if (allowed & (1 << m)) + { + nextarg = arg; + nextarg.nmoves = arg.nmoves + 1; + nextarg.moves[arg.nmoves] = m; + nextarg.cube = move(arg.cube, m); + nextarg.inverse = premove(arg.inverse, m); + + if (nextarg.nmoves == 2) + { + dfsarg_solveh48_t *task = malloc(sizeof(dfsarg_solveh48_t)); + *task = nextarg; + submit_task(tq, task); + } + else + { + queue[rear++] = nextarg; + nodes_at_next_depth++; + } + } + } + + if (nodes_at_current_depth == 0) + { + depth++; + nodes_at_current_depth = nodes_at_next_depth; + nodes_at_next_depth = 0; + } + if (depth == 2) + { + return 0; + } + } + return 0; +} + +STATIC int64_t +solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq) +{ + dfsarg_solveh48_t nextarg; + int64_t ret; + uint8_t m; + + if (*arg->nsols == arg->maxsolutions) + return 0; + + if (solve_h48_stop(arg)) + return 0; + + if (issolved(arg->cube)) + { + if (arg->nmoves + arg->npremoves != arg->depth) + return 0; + solve_h48_appendsolution_thread(arg, tq); + return 1; + } + + nextarg = *arg; + ret = 0; + uint32_t allowed; + if (arg->nissbranch & MM_INVERSE) + { + allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); + for (m = 0; m < 18; m++) + { + if (allowed & (1 << m)) + { + nextarg.npremoves = arg->npremoves + 1; + nextarg.premoves[arg->npremoves] = m; + nextarg.inverse = move(arg->inverse, m); + nextarg.cube = premove(arg->cube, m); + ret += solve_h48_single(&nextarg, tq); + } + } + } + else + { + allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); + for (m = 0; m < 18; m++) + { + if (allowed & (1 << m)) + { + nextarg.nmoves = arg->nmoves + 1; + nextarg.moves[arg->nmoves] = m; + nextarg.cube = move(arg->cube, m); + nextarg.inverse = premove(arg->inverse, m); + ret += solve_h48_single(&nextarg, tq); + } + } + } + return ret; +} + +STATIC int64_t +solve_h48_parent( + cube_t cube, + int8_t minmoves, + int8_t maxmoves, + int8_t maxsolutions, + const void *data, + char *solutions) +{ + int64_t nsols; + int p_depth = 0; + dfsarg_solveh48_t bfs_arg; + tableinfo_t info; + pthread_t threads[THREADS]; + + if (!readtableinfo_n(data, 2, &info)) + { + LOG("solve_h48: error reading table\n"); + return 0; + } + + bfs_arg = (dfsarg_solveh48_t){ + .cube = cube, + .inverse = inverse(cube), + .nsols = &nsols, + .maxsolutions = maxsolutions, + .h = info.h48h, + .k = info.bits, + .cocsepdata = get_cocsepdata_ptr(data), + .h48data = get_h48data_ptr(data), + .nextsol = &solutions}; + + task_queue_t q; + init_queue(&q); + if (solve_h48_bfs(&bfs_arg, &q)) + return nsols; + + task_queue_t nq; + init_queue(&nq); + + atomic_store(&nq.active_tasks, 0); + pthread_mutex_init(&nq.active_tasks_mutex, NULL); + pthread_cond_init(&nq.active_tasks_cond, NULL); + + for (int i = 0; i < THREADS; i++) + { + pthread_create(&threads[i], NULL, &start_thread, &nq); + } + + nsols = 0; + for (p_depth = minmoves > 2 ? minmoves : 2; + p_depth <= maxmoves && nsols < maxsolutions; + p_depth++) + { + LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth); + copy_queue(&q, &nq, p_depth); + pthread_mutex_lock(&nq.active_tasks_mutex); + while (nq.active_tasks > 0) + { + pthread_cond_wait(&nq.active_tasks_cond, &nq.active_tasks_mutex); + } + pthread_mutex_unlock(&nq.active_tasks_mutex); + } + for (int i = 0; i < THREADS; i++) + { + pthread_join(threads[i], NULL); + } + + return nsols; +} -- cgit v1.3 From c299466bfa9a9a172e1cc021cf7b9ed6a4093888 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Tue, 24 Sep 2024 16:45:42 +0200 Subject: Fixed multithread search, todo multiple scramble memory release --- src/solvers/h48/thread.h | 158 ++++++++++++++++++++--------------------------- 1 file changed, 66 insertions(+), 92 deletions(-) diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h index 1eade29..155bc6a 100644 --- a/src/solvers/h48/thread.h +++ b/src/solvers/h48/thread.h @@ -5,32 +5,31 @@ #include #define MAX_QUEUE_SIZE 500 - typedef struct { dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE]; int front; int rear; int tasks_count; + int active; pthread_mutex_t mutex; pthread_cond_t cond; - atomic_int active_tasks; - pthread_mutex_t active_tasks_mutex; - pthread_cond_t active_tasks_cond; + pthread_cond_t active_cond; + bool terminate; } task_queue_t; STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); STATIC void init_queue(task_queue_t *); STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t *); -STATIC void copy_queue(task_queue_t *, task_queue_t *, int); -STATIC dfsarg_solveh48_t *get_task(task_queue_t *); +STATIC void copy_queue(task_queue_t *, task_queue_t *, int, int64_t *); STATIC void *start_thread(void *); STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *); STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *); STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void *, char *); STATIC void -solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq){ +solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq) +{ pthread_mutex_lock(&tq->mutex); int strl; uint8_t invertedpremoves[MAXLEN]; @@ -62,8 +61,10 @@ init_queue(task_queue_t *queue) queue->front = 0; queue->rear = 0; queue->tasks_count = 0; + queue->active = 0; pthread_mutex_init(&queue->mutex, NULL); pthread_cond_init(&queue->cond, NULL); + pthread_cond_init(&queue->active_cond, NULL); } STATIC void @@ -73,14 +74,13 @@ submit_task(task_queue_t *queue, dfsarg_solveh48_t *task) queue->tasks[queue->rear] = task; queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; queue->tasks_count++; - pthread_cond_signal(&queue->cond); + pthread_cond_broadcast(&queue->cond); pthread_mutex_unlock(&queue->mutex); } STATIC void -copy_queue(task_queue_t *src, task_queue_t *dest, int depth) +copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols) { - pthread_mutex_lock(&src->mutex); pthread_mutex_lock(&dest->mutex); for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE) { @@ -93,46 +93,42 @@ copy_queue(task_queue_t *src, task_queue_t *dest, int depth) dest->front = src->front; dest->rear = src->rear; dest->tasks_count = src->tasks_count; - pthread_mutex_unlock(&src->mutex); - pthread_cond_signal(&dest->cond); + dest->active = src->active; + pthread_cond_broadcast(&dest->cond); pthread_mutex_unlock(&dest->mutex); } -STATIC dfsarg_solveh48_t * -get_task(task_queue_t *queue) -{ - pthread_mutex_lock(&queue->mutex); - while (queue->tasks_count == 0) - { - pthread_cond_wait(&queue->cond, &queue->mutex); - } - dfsarg_solveh48_t *task = queue->tasks[queue->front]; - queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; - queue->tasks_count--; - pthread_mutex_unlock(&queue->mutex); - return task; -} + STATIC void * start_thread(void *arg) { task_queue_t *queue = (task_queue_t *)arg; - while (true) - { - dfsarg_solveh48_t *task = get_task(queue); - if (task == NULL) - { + while (1) { + pthread_mutex_lock(&queue->mutex); + while (queue->tasks_count == 0 && !queue->terminate) { + pthread_cond_wait(&queue->cond, &queue->mutex); + } + if (queue->tasks_count == 0 && queue->terminate) { + pthread_mutex_unlock(&queue->mutex); break; } - solve_h48_single(task, queue); - free(task); - pthread_mutex_lock(&queue->active_tasks_mutex); - atomic_fetch_sub(&queue->active_tasks, 1); - if (atomic_load(&queue->active_tasks) == 0) - { - pthread_cond_signal(&queue->active_tasks_cond); + if (queue->tasks_count > 0) { + dfsarg_solveh48_t *task = queue->tasks[queue->front]; + queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; + queue->tasks_count--; + queue->active++; + pthread_mutex_unlock(&queue->mutex); + + solve_h48_single(task, queue); + + pthread_mutex_lock(&queue->mutex); + queue->active--; + + if(queue->tasks_count == 0 && queue->active == 0) + pthread_cond_signal(&queue->active_cond); } - pthread_mutex_unlock(&queue->active_tasks_mutex); + pthread_mutex_unlock(&queue->mutex); } return NULL; } @@ -146,19 +142,16 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) int depth = 0; int nodes_at_current_depth = 1; int nodes_at_next_depth = 0; - queue[rear++] = *arg_zero; - while (front < rear) - { + while (front < rear){ dfsarg_solveh48_t arg = queue[front++]; nodes_at_current_depth--; if (*arg.nsols == arg.maxsolutions) return 1; - if (issolved(arg.cube)) - { + if (issolved(arg.cube)){ if (arg.nmoves + arg.npremoves != arg.depth) continue; solve_h48_appendsolution(&arg); @@ -168,42 +161,32 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) arg.nissbranch = MM_NORMAL; uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch); - for (uint8_t m = 0; m < 18; m++) - { - if (allowed & (1 << m)) - { + for (uint8_t m = 0; m < 18; m++){ + if (allowed & (1 << m)){ nextarg = arg; nextarg.nmoves = arg.nmoves + 1; nextarg.moves[arg.nmoves] = m; nextarg.cube = move(arg.cube, m); nextarg.inverse = premove(arg.inverse, m); - if (nextarg.nmoves == 2) - { + if (nextarg.nmoves == 2){ dfsarg_solveh48_t *task = malloc(sizeof(dfsarg_solveh48_t)); *task = nextarg; submit_task(tq, task); - } - else - { + } else { queue[rear++] = nextarg; nodes_at_next_depth++; } } } - - if (nodes_at_current_depth == 0) - { + if (nodes_at_current_depth == 0){ depth++; nodes_at_current_depth = nodes_at_next_depth; nodes_at_next_depth = 0; } - if (depth == 2) - { - return 0; - } + if (depth == 2) return 0; } - return 0; + return 1; } STATIC int64_t @@ -219,8 +202,7 @@ solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq) if (solve_h48_stop(arg)) return 0; - if (issolved(arg->cube)) - { + if (issolved(arg->cube)){ if (arg->nmoves + arg->npremoves != arg->depth) return 0; solve_h48_appendsolution_thread(arg, tq); @@ -230,13 +212,10 @@ solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq) nextarg = *arg; ret = 0; uint32_t allowed; - if (arg->nissbranch & MM_INVERSE) - { + if (arg->nissbranch & MM_INVERSE){ allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); - for (m = 0; m < 18; m++) - { - if (allowed & (1 << m)) - { + for (m = 0; m < 18; m++){ + if (allowed & (1 << m)){ nextarg.npremoves = arg->npremoves + 1; nextarg.premoves[arg->npremoves] = m; nextarg.inverse = move(arg->inverse, m); @@ -244,14 +223,10 @@ solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq) ret += solve_h48_single(&nextarg, tq); } } - } - else - { + } else { allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); - for (m = 0; m < 18; m++) - { - if (allowed & (1 << m)) - { + for (m = 0; m < 18; m++){ + if (allowed & (1 << m)){ nextarg.nmoves = arg->nmoves + 1; nextarg.moves[arg->nmoves] = m; nextarg.cube = move(arg->cube, m); @@ -303,12 +278,7 @@ solve_h48_parent( task_queue_t nq; init_queue(&nq); - atomic_store(&nq.active_tasks, 0); - pthread_mutex_init(&nq.active_tasks_mutex, NULL); - pthread_cond_init(&nq.active_tasks_cond, NULL); - - for (int i = 0; i < THREADS; i++) - { + for (int i = 0; i < THREADS; i++){ pthread_create(&threads[i], NULL, &start_thread, &nq); } @@ -318,18 +288,22 @@ solve_h48_parent( p_depth++) { LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth); - copy_queue(&q, &nq, p_depth); - pthread_mutex_lock(&nq.active_tasks_mutex); - while (nq.active_tasks > 0) - { - pthread_cond_wait(&nq.active_tasks_cond, &nq.active_tasks_mutex); - } - pthread_mutex_unlock(&nq.active_tasks_mutex); + copy_queue(&q, &nq, p_depth, &nsols); + + pthread_mutex_lock(&nq.mutex); + while (nq.active > 0 || nq.tasks_count > 0) + pthread_cond_wait(&nq.active_cond, &nq.mutex); + pthread_mutex_unlock(&nq.mutex); } - for (int i = 0; i < THREADS; i++) - { + + pthread_mutex_lock(&nq.mutex); + nq.terminate = true; + pthread_cond_broadcast(&nq.cond); + pthread_mutex_unlock(&nq.mutex); + + for (int i = 0; i < THREADS; i++){ pthread_join(threads[i], NULL); } - + // fix memory release for multiple scrambles. return nsols; } -- cgit v1.3 From 2c109db35b3b30b27e71e7811776edec1af1208e Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Wed, 25 Sep 2024 11:00:40 +0200 Subject: Fixed nsols, added atomic vars where possible --- src/solvers/h48/thread.h | 20 ++++++++------------ 1 file changed, 8 insertions(+), 12 deletions(-) diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h index 155bc6a..d035b52 100644 --- a/src/solvers/h48/thread.h +++ b/src/solvers/h48/thread.h @@ -11,11 +11,11 @@ typedef struct int front; int rear; int tasks_count; - int active; + atomic_int active; pthread_mutex_t mutex; pthread_cond_t cond; pthread_cond_t active_cond; - bool terminate; + atomic_bool terminate; } task_queue_t; STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); @@ -62,6 +62,7 @@ init_queue(task_queue_t *queue) queue->rear = 0; queue->tasks_count = 0; queue->active = 0; + queue->terminate = ATOMIC_VAR_INIT(false); pthread_mutex_init(&queue->mutex, NULL); pthread_cond_init(&queue->cond, NULL); pthread_cond_init(&queue->active_cond, NULL); @@ -93,7 +94,7 @@ copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols) dest->front = src->front; dest->rear = src->rear; dest->tasks_count = src->tasks_count; - dest->active = src->active; + // atomic_init(&dest->active, &src->active); pthread_cond_broadcast(&dest->cond); pthread_mutex_unlock(&dest->mutex); } @@ -121,14 +122,12 @@ start_thread(void *arg) pthread_mutex_unlock(&queue->mutex); solve_h48_single(task, queue); - - pthread_mutex_lock(&queue->mutex); - queue->active--; + + atomic_fetch_sub(&queue->active, 1); if(queue->tasks_count == 0 && queue->active == 0) pthread_cond_signal(&queue->active_cond); } - pthread_mutex_unlock(&queue->mutex); } return NULL; } @@ -247,7 +246,7 @@ solve_h48_parent( const void *data, char *solutions) { - int64_t nsols; + int64_t nsols = 0; int p_depth = 0; dfsarg_solveh48_t bfs_arg; tableinfo_t info; @@ -296,14 +295,11 @@ solve_h48_parent( pthread_mutex_unlock(&nq.mutex); } - pthread_mutex_lock(&nq.mutex); - nq.terminate = true; + atomic_store(&nq.terminate, true); pthread_cond_broadcast(&nq.cond); - pthread_mutex_unlock(&nq.mutex); for (int i = 0; i < THREADS; i++){ pthread_join(threads[i], NULL); } - // fix memory release for multiple scrambles. return nsols; } -- cgit v1.3 From 3cb66440de97a787a974eed87a5fd876b46cef92 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Thu, 26 Sep 2024 10:48:27 +0200 Subject: Fixed solutions vector, added constants --- src/solvers/h48/solve.h | 3 ++- src/solvers/h48/thread.h | 21 ++++++++++++--------- tools/200_solve_small/solve_small.c | 2 ++ 3 files changed, 16 insertions(+), 10 deletions(-) diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index b67aedc..4a1e961 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -199,6 +199,7 @@ solve_h48( arg.npremoves = 0; solve_h48_dfs(&arg); } - + **arg.nextsol = '\0'; + (*arg.nextsol)++; return nsols; } diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h index d035b52..c76c9d6 100644 --- a/src/solvers/h48/thread.h +++ b/src/solvers/h48/thread.h @@ -4,7 +4,8 @@ #include #include -#define MAX_QUEUE_SIZE 500 +#define MAX_QUEUE_SIZE 244 +#define BFS_DEPTH 2 typedef struct { dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE]; @@ -31,7 +32,7 @@ STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq) { pthread_mutex_lock(&tq->mutex); - int strl; + int strl = 0; uint8_t invertedpremoves[MAXLEN]; char *solution = *arg->nextsol; @@ -168,7 +169,7 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) nextarg.cube = move(arg.cube, m); nextarg.inverse = premove(arg.inverse, m); - if (nextarg.nmoves == 2){ + if (nextarg.nmoves == BFS_DEPTH){ dfsarg_solveh48_t *task = malloc(sizeof(dfsarg_solveh48_t)); *task = nextarg; submit_task(tq, task); @@ -179,11 +180,11 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) } } if (nodes_at_current_depth == 0){ - depth++; nodes_at_current_depth = nodes_at_next_depth; nodes_at_next_depth = 0; + LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", *nextarg.nsols, depth++); } - if (depth == 2) return 0; + if (depth == BFS_DEPTH) return 0; } return 1; } @@ -248,7 +249,7 @@ solve_h48_parent( { int64_t nsols = 0; int p_depth = 0; - dfsarg_solveh48_t bfs_arg; + dfsarg_solveh48_t arg; tableinfo_t info; pthread_t threads[THREADS]; @@ -258,7 +259,7 @@ solve_h48_parent( return 0; } - bfs_arg = (dfsarg_solveh48_t){ + arg = (dfsarg_solveh48_t){ .cube = cube, .inverse = inverse(cube), .nsols = &nsols, @@ -271,7 +272,7 @@ solve_h48_parent( task_queue_t q; init_queue(&q); - if (solve_h48_bfs(&bfs_arg, &q)) + if (solve_h48_bfs(&arg, &q)) return nsols; task_queue_t nq; @@ -282,7 +283,7 @@ solve_h48_parent( } nsols = 0; - for (p_depth = minmoves > 2 ? minmoves : 2; + for (p_depth = minmoves > BFS_DEPTH ? minmoves : BFS_DEPTH; p_depth <= maxmoves && nsols < maxsolutions; p_depth++) { @@ -301,5 +302,7 @@ solve_h48_parent( for (int i = 0; i < THREADS; i++){ pthread_join(threads[i], NULL); } + **arg.nextsol = '\0'; + (*arg.nextsol)++; return nsols; } diff --git a/tools/200_solve_small/solve_small.c b/tools/200_solve_small/solve_small.c index 4d07728..ed71982 100644 --- a/tools/200_solve_small/solve_small.c +++ b/tools/200_solve_small/solve_small.c @@ -10,6 +10,8 @@ char *buf; char *scrambles[] = { "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */ "RLUD RLUD RLUD", /* 12 optimal */ + "R' U' F D2 L2 F R2 U2 R2 B D2 L B2 D' B2 L' R' B D2 B U2 L U2 R' U' F", /* FMC2019 A1 - 16 optimal */ + // "R' U' F D R F2 D L F D2 F2 L' U R' L2 D' R2 F2 R2 D L2 U2 R' U' F", /* FMC2024 A1 - 19 optimal */ NULL }; -- cgit v1.3 From 47fe842ee3375ad63cc96550e345d18f3af0885b Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Fri, 27 Sep 2024 15:47:03 +0200 Subject: format fix thread.h --- src/nissy.c | 4 ++-- src/solvers/h48/thread.h | 12 ++---------- 2 files changed, 4 insertions(+), 12 deletions(-) diff --git a/src/nissy.c b/src/nissy.c index 5eeb457..56acf25 100644 --- a/src/nissy.c +++ b/src/nissy.c @@ -333,8 +333,8 @@ nissy_solve( ret = -1; } else { ret = THREADS > 1 ? - solve_h48_parent(c, minmoves, maxmoves, maxsolutions, data, solutions) : - solve_h48(c, minmoves, maxmoves, maxsolutions, data, solutions); + solve_h48_parent(c, minmoves, maxmoves, maxsolutions, data, solutions) : + solve_h48(c, minmoves, maxmoves, maxsolutions, data, solutions); } } else if (!strcmp(solver, "h48stats")) { ret = solve_h48stats(c, maxmoves, data, solutions); diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h index c76c9d6..bea34d0 100644 --- a/src/solvers/h48/thread.h +++ b/src/solvers/h48/thread.h @@ -1,13 +1,8 @@ -#include #include -#include -#include -#include #define MAX_QUEUE_SIZE 244 #define BFS_DEPTH 2 -typedef struct -{ +typedef struct { dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE]; int front; int rear; @@ -95,12 +90,10 @@ copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols) dest->front = src->front; dest->rear = src->rear; dest->tasks_count = src->tasks_count; - // atomic_init(&dest->active, &src->active); pthread_cond_broadcast(&dest->cond); pthread_mutex_unlock(&dest->mutex); } - STATIC void * start_thread(void *arg) { @@ -253,8 +246,7 @@ solve_h48_parent( tableinfo_t info; pthread_t threads[THREADS]; - if (!readtableinfo_n(data, 2, &info)) - { + if (!readtableinfo_n(data, 2, &info)){ LOG("solve_h48: error reading table\n"); return 0; } -- cgit v1.3 From 1e768138b80b7b94cef922f1fb9d5c4bfa796052 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Sat, 28 Sep 2024 15:33:06 +0200 Subject: go back to non atomic active --- src/solvers/h48/thread.h | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h index bea34d0..91e092f 100644 --- a/src/solvers/h48/thread.h +++ b/src/solvers/h48/thread.h @@ -7,7 +7,7 @@ typedef struct { int front; int rear; int tasks_count; - atomic_int active; + int active; pthread_mutex_t mutex; pthread_cond_t cond; pthread_cond_t active_cond; @@ -117,11 +117,13 @@ start_thread(void *arg) solve_h48_single(task, queue); - atomic_fetch_sub(&queue->active, 1); + pthread_mutex_lock(&queue->mutex); + queue->active--; if(queue->tasks_count == 0 && queue->active == 0) pthread_cond_signal(&queue->active_cond); } + pthread_mutex_unlock(&queue->mutex); } return NULL; } -- cgit v1.3 From 105259a58425a9ca1cec1b85339588410ae4fff7 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Sat, 28 Sep 2024 17:47:49 +0200 Subject: No malloc, static tasks poll --- src/solvers/h48/thread.h | 21 ++++++++++----------- tools/200_solve_small/solve_small.c | 2 +- 2 files changed, 11 insertions(+), 12 deletions(-) diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h index 91e092f..fb5ccbc 100644 --- a/src/solvers/h48/thread.h +++ b/src/solvers/h48/thread.h @@ -3,7 +3,7 @@ #define MAX_QUEUE_SIZE 244 #define BFS_DEPTH 2 typedef struct { - dfsarg_solveh48_t *tasks[MAX_QUEUE_SIZE]; + dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE]; int front; int rear; int tasks_count; @@ -16,7 +16,7 @@ typedef struct { STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); STATIC void init_queue(task_queue_t *); -STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t *); +STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t); STATIC void copy_queue(task_queue_t *, task_queue_t *, int, int64_t *); STATIC void *start_thread(void *); STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *); @@ -65,7 +65,7 @@ init_queue(task_queue_t *queue) } STATIC void -submit_task(task_queue_t *queue, dfsarg_solveh48_t *task) +submit_task(task_queue_t *queue, dfsarg_solveh48_t task) { pthread_mutex_lock(&queue->mutex); queue->tasks[queue->rear] = task; @@ -81,11 +81,8 @@ copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols) pthread_mutex_lock(&dest->mutex); for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE) { - if (src->tasks[i] != NULL) - { dest->tasks[i] = src->tasks[i]; - dest->tasks[i]->depth = depth; - } + dest->tasks[i].depth = depth; } dest->front = src->front; dest->rear = src->rear; @@ -109,13 +106,13 @@ start_thread(void *arg) } if (queue->tasks_count > 0) { - dfsarg_solveh48_t *task = queue->tasks[queue->front]; + dfsarg_solveh48_t task = queue->tasks[queue->front]; queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; queue->tasks_count--; queue->active++; pthread_mutex_unlock(&queue->mutex); - solve_h48_single(task, queue); + solve_h48_single(&task, queue); pthread_mutex_lock(&queue->mutex); queue->active--; @@ -139,6 +136,8 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) int nodes_at_next_depth = 0; queue[rear++] = *arg_zero; + dfsarg_solveh48_t task_pool[MAX_QUEUE_SIZE]; + while (front < rear){ dfsarg_solveh48_t arg = queue[front++]; nodes_at_current_depth--; @@ -165,9 +164,9 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) nextarg.inverse = premove(arg.inverse, m); if (nextarg.nmoves == BFS_DEPTH){ - dfsarg_solveh48_t *task = malloc(sizeof(dfsarg_solveh48_t)); + dfsarg_solveh48_t *task = &task_pool[rear % MAX_QUEUE_SIZE]; *task = nextarg; - submit_task(tq, task); + submit_task(tq, *task); } else { queue[rear++] = nextarg; nodes_at_next_depth++; diff --git a/tools/200_solve_small/solve_small.c b/tools/200_solve_small/solve_small.c index ed71982..f1037b4 100644 --- a/tools/200_solve_small/solve_small.c +++ b/tools/200_solve_small/solve_small.c @@ -10,7 +10,7 @@ char *buf; char *scrambles[] = { "R D' R2 D R U2 R' D' R U2 R D R'", /* 12 optimal */ "RLUD RLUD RLUD", /* 12 optimal */ - "R' U' F D2 L2 F R2 U2 R2 B D2 L B2 D' B2 L' R' B D2 B U2 L U2 R' U' F", /* FMC2019 A1 - 16 optimal */ + // "R' U' F D2 L2 F R2 U2 R2 B D2 L B2 D' B2 L' R' B D2 B U2 L U2 R' U' F", /* FMC2019 A1 - 16 optimal */ // "R' U' F D R F2 D L F D2 F2 L' U R' L2 D' R2 F2 R2 D L2 U2 R' U' F", /* FMC2024 A1 - 19 optimal */ NULL }; -- cgit v1.3 From 8fcfb3a33fe053ed2032d58ecc0b5d640c155931 Mon Sep 17 00:00:00 2001 From: enricotenuti Date: Sun, 29 Sep 2024 12:38:43 +0200 Subject: minor changes for PR --- src/nissy.c | 3 +- src/solvers/h48/h48.h | 2 +- src/solvers/h48/solve.h | 4 +- src/solvers/h48/solve_multithread.h | 300 +++++++++++++++++++++++++++++++++++ src/solvers/h48/thread.h | 301 ------------------------------------ tools/200_solve_small/solve_small.c | 2 - 6 files changed, 305 insertions(+), 307 deletions(-) create mode 100644 src/solvers/h48/solve_multithread.h delete mode 100644 src/solvers/h48/thread.h diff --git a/src/nissy.c b/src/nissy.c index 56acf25..a2da73d 100644 --- a/src/nissy.c +++ b/src/nissy.c @@ -1,5 +1,6 @@ #include #include +#include #include #include #include @@ -333,7 +334,7 @@ nissy_solve( ret = -1; } else { ret = THREADS > 1 ? - solve_h48_parent(c, minmoves, maxmoves, maxsolutions, data, solutions) : + solve_h48_multithread(c, minmoves, maxmoves, maxsolutions, data, solutions) : solve_h48(c, minmoves, maxmoves, maxsolutions, data, solutions); } } else if (!strcmp(solver, "h48stats")) { diff --git a/src/solvers/h48/h48.h b/src/solvers/h48/h48.h index 2fe9575..176ce22 100644 --- a/src/solvers/h48/h48.h +++ b/src/solvers/h48/h48.h @@ -4,4 +4,4 @@ #include "gendata_h48.h" #include "stats.h" #include "solve.h" -#include "thread.h" +#include "solve_multithread.h" diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 4a1e961..c2dce91 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h @@ -4,7 +4,7 @@ typedef struct { int8_t nmoves; int8_t depth; uint8_t moves[MAXLEN]; - int64_t *nsols; + _Atomic int64_t *nsols; int64_t maxsolutions; uint8_t h; uint8_t k; @@ -167,7 +167,7 @@ solve_h48( char *solutions ) { - int64_t nsols; + _Atomic int64_t nsols; dfsarg_solveh48_t arg; tableinfo_t info; diff --git a/src/solvers/h48/solve_multithread.h b/src/solvers/h48/solve_multithread.h new file mode 100644 index 0000000..86171a9 --- /dev/null +++ b/src/solvers/h48/solve_multithread.h @@ -0,0 +1,300 @@ +#define MAX_QUEUE_SIZE 244 +#define BFS_DEPTH 2 + +typedef struct { + dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE]; + int front; + int rear; + int tasks_count; + int active; + pthread_mutex_t mutex; + pthread_cond_t cond; + pthread_cond_t active_cond; + atomic_bool terminate; +} task_queue_t; + +STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); +STATIC void init_queue(task_queue_t *); +STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t); +STATIC void copy_queue(task_queue_t *, task_queue_t *, int, _Atomic int64_t *); +STATIC void *start_thread(void *); +STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *, int8_t); +STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *); +STATIC int64_t solve_h48_multithread(cube_t, int8_t, int8_t, int8_t, const void *, char *); + +STATIC void +solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq) +{ + pthread_mutex_lock(&tq->mutex); + int strl = 0; + uint8_t invertedpremoves[MAXLEN]; + char *solution = *arg->nextsol; + + strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); + *arg->nextsol += strl; + + if (arg->npremoves) + { + **arg->nextsol = ' '; + (*arg->nextsol)++; + + invertmoves(arg->premoves, arg->npremoves, invertedpremoves); + strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); + *arg->nextsol += strl; + } + LOG("Solution found: %s\n", solution); + + **arg->nextsol = '\n'; + (*arg->nextsol)++; + (*arg->nsols)++; + pthread_mutex_unlock(&tq->mutex); +} + +STATIC void +init_queue(task_queue_t *queue) +{ + queue->front = 0; + queue->rear = 0; + queue->tasks_count = 0; + queue->active = 0; + queue->terminate = ATOMIC_VAR_INIT(false); + pthread_mutex_init(&queue->mutex, NULL); + pthread_cond_init(&queue->cond, NULL); + pthread_cond_init(&queue->active_cond, NULL); +} + +STATIC void +submit_task(task_queue_t *queue, dfsarg_solveh48_t task) +{ + pthread_mutex_lock(&queue->mutex); + queue->tasks[queue->rear] = task; + queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; + queue->tasks_count++; + pthread_cond_broadcast(&queue->cond); + pthread_mutex_unlock(&queue->mutex); +} + +STATIC void +copy_queue(task_queue_t *src, task_queue_t *dest, int depth, _Atomic int64_t *nsols) +{ + pthread_mutex_lock(&dest->mutex); + for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE) + { + dest->tasks[i] = src->tasks[i]; + dest->tasks[i].depth = depth; + } + dest->front = src->front; + dest->rear = src->rear; + dest->tasks_count = src->tasks_count; + pthread_cond_broadcast(&dest->cond); + pthread_mutex_unlock(&dest->mutex); +} + +STATIC void * +start_thread(void *arg) +{ + task_queue_t *queue = (task_queue_t *)arg; + while (1) { + pthread_mutex_lock(&queue->mutex); + while (queue->tasks_count == 0 && !queue->terminate) { + pthread_cond_wait(&queue->cond, &queue->mutex); + } + if (queue->tasks_count == 0 && queue->terminate) { + pthread_mutex_unlock(&queue->mutex); + break; + } + + if (queue->tasks_count > 0) { + dfsarg_solveh48_t task = queue->tasks[queue->front]; + queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; + queue->tasks_count--; + queue->active++; + pthread_mutex_unlock(&queue->mutex); + + solve_h48_single(&task, queue); + + pthread_mutex_lock(&queue->mutex); + queue->active--; + + if(queue->tasks_count == 0 && queue->active == 0) + pthread_cond_signal(&queue->active_cond); + } + pthread_mutex_unlock(&queue->mutex); + } + return NULL; +} + +STATIC int64_t +solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq, int8_t maxmoves) +{ + dfsarg_solveh48_t queue[MAX_QUEUE_SIZE]; + int front = 0, rear = 0; + dfsarg_solveh48_t nextarg; + int depth = 0; + int nodes_at_current_depth = 1; + int nodes_at_next_depth = 0; + queue[rear++] = *arg_zero; + + dfsarg_solveh48_t task_pool[MAX_QUEUE_SIZE]; + + while (front < rear){ + dfsarg_solveh48_t arg = queue[front++]; + nodes_at_current_depth--; + + if (*arg.nsols == arg.maxsolutions) + return 1; + + if (issolved(arg.cube)){ + if (arg.nmoves + arg.npremoves >= arg.depth && arg.nmoves + arg.npremoves <= maxmoves) + solve_h48_appendsolution(&arg); + continue; + } + + arg.nissbranch = MM_NORMAL; + uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch); + + for (uint8_t m = 0; m < 18; m++){ + if (allowed & (1 << m)){ + nextarg = arg; + nextarg.nmoves = arg.nmoves + 1; + nextarg.moves[arg.nmoves] = m; + nextarg.cube = move(arg.cube, m); + nextarg.inverse = premove(arg.inverse, m); + + if (nextarg.nmoves == BFS_DEPTH){ + dfsarg_solveh48_t *task = &task_pool[rear % MAX_QUEUE_SIZE]; + *task = nextarg; + submit_task(tq, *task); + } else { + queue[rear++] = nextarg; + nodes_at_next_depth++; + } + } + } + if (nodes_at_current_depth == 0){ + nodes_at_current_depth = nodes_at_next_depth; + nodes_at_next_depth = 0; + LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", *nextarg.nsols, depth++); + } + if (depth == BFS_DEPTH) return 0; + } + return 1; +} + +STATIC int64_t +solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq) +{ + dfsarg_solveh48_t nextarg; + int64_t ret; + uint8_t m; + + if (*arg->nsols == arg->maxsolutions) + return 0; + + if (solve_h48_stop(arg)) + return 0; + + if (issolved(arg->cube)){ + if (arg->nmoves + arg->npremoves != arg->depth) + return 0; + solve_h48_appendsolution_thread(arg, tq); + return 1; + } + + nextarg = *arg; + ret = 0; + uint32_t allowed; + if (arg->nissbranch & MM_INVERSE){ + allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); + for (m = 0; m < 18; m++){ + if (allowed & (1 << m)){ + nextarg.npremoves = arg->npremoves + 1; + nextarg.premoves[arg->npremoves] = m; + nextarg.inverse = move(arg->inverse, m); + nextarg.cube = premove(arg->cube, m); + ret += solve_h48_single(&nextarg, tq); + } + } + } else { + allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); + for (m = 0; m < 18; m++){ + if (allowed & (1 << m)){ + nextarg.nmoves = arg->nmoves + 1; + nextarg.moves[arg->nmoves] = m; + nextarg.cube = move(arg->cube, m); + nextarg.inverse = premove(arg->inverse, m); + ret += solve_h48_single(&nextarg, tq); + } + } + } + return ret; +} + +STATIC int64_t +solve_h48_multithread( + cube_t cube, + int8_t minmoves, + int8_t maxmoves, + int8_t maxsolutions, + const void *data, + char *solutions) +{ + _Atomic int64_t nsols = 0; + int p_depth = 0; + dfsarg_solveh48_t arg; + tableinfo_t info; + pthread_t threads[THREADS]; + + if (!readtableinfo_n(data, 2, &info)){ + LOG("solve_h48: error reading table\n"); + return 0; + } + + arg = (dfsarg_solveh48_t){ + .cube = cube, + .inverse = inverse(cube), + .nsols = &nsols, + .depth = minmoves, + .maxsolutions = maxsolutions, + .h = info.h48h, + .k = info.bits, + .cocsepdata = get_cocsepdata_ptr(data), + .h48data = get_h48data_ptr(data), + .nextsol = &solutions}; + + task_queue_t q; + init_queue(&q); + if (solve_h48_bfs(&arg, &q, maxmoves)) + return nsols; + + task_queue_t nq; + init_queue(&nq); + + for (int i = 0; i < THREADS; i++){ + pthread_create(&threads[i], NULL, &start_thread, &nq); + } + + nsols = 0; + for (p_depth = minmoves > BFS_DEPTH ? minmoves : BFS_DEPTH; + p_depth <= maxmoves && nsols < maxsolutions; + p_depth++) + { + LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth); + copy_queue(&q, &nq, p_depth, &nsols); + + pthread_mutex_lock(&nq.mutex); + while (nq.active > 0 || nq.tasks_count > 0) + pthread_cond_wait(&nq.active_cond, &nq.mutex); + pthread_mutex_unlock(&nq.mutex); + } + + atomic_store(&nq.terminate, true); + pthread_cond_broadcast(&nq.cond); + + for (int i = 0; i < THREADS; i++){ + pthread_join(threads[i], NULL); + } + **arg.nextsol = '\0'; + (*arg.nextsol)++; + return nsols; +} diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/thread.h deleted file mode 100644 index fb5ccbc..0000000 --- a/src/solvers/h48/thread.h +++ /dev/null @@ -1,301 +0,0 @@ -#include - -#define MAX_QUEUE_SIZE 244 -#define BFS_DEPTH 2 -typedef struct { - dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE]; - int front; - int rear; - int tasks_count; - int active; - pthread_mutex_t mutex; - pthread_cond_t cond; - pthread_cond_t active_cond; - atomic_bool terminate; -} task_queue_t; - -STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); -STATIC void init_queue(task_queue_t *); -STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t); -STATIC void copy_queue(task_queue_t *, task_queue_t *, int, int64_t *); -STATIC void *start_thread(void *); -STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *); -STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *); -STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void *, char *); - -STATIC void -solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq) -{ - pthread_mutex_lock(&tq->mutex); - int strl = 0; - uint8_t invertedpremoves[MAXLEN]; - char *solution = *arg->nextsol; - - strl = writemoves(arg->moves, arg->nmoves, *arg->nextsol); - *arg->nextsol += strl; - - if (arg->npremoves) - { - **arg->nextsol = ' '; - (*arg->nextsol)++; - - invertmoves(arg->premoves, arg->npremoves, invertedpremoves); - strl = writemoves(invertedpremoves, arg->npremoves, *arg->nextsol); - *arg->nextsol += strl; - } - LOG("Solution found: %s\n", solution); - - **arg->nextsol = '\n'; - (*arg->nextsol)++; - (*arg->nsols)++; - pthread_mutex_unlock(&tq->mutex); -} - -STATIC void -init_queue(task_queue_t *queue) -{ - queue->front = 0; - queue->rear = 0; - queue->tasks_count = 0; - queue->active = 0; - queue->terminate = ATOMIC_VAR_INIT(false); - pthread_mutex_init(&queue->mutex, NULL); - pthread_cond_init(&queue->cond, NULL); - pthread_cond_init(&queue->active_cond, NULL); -} - -STATIC void -submit_task(task_queue_t *queue, dfsarg_solveh48_t task) -{ - pthread_mutex_lock(&queue->mutex); - queue->tasks[queue->rear] = task; - queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE; - queue->tasks_count++; - pthread_cond_broadcast(&queue->cond); - pthread_mutex_unlock(&queue->mutex); -} - -STATIC void -copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols) -{ - pthread_mutex_lock(&dest->mutex); - for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE) - { - dest->tasks[i] = src->tasks[i]; - dest->tasks[i].depth = depth; - } - dest->front = src->front; - dest->rear = src->rear; - dest->tasks_count = src->tasks_count; - pthread_cond_broadcast(&dest->cond); - pthread_mutex_unlock(&dest->mutex); -} - -STATIC void * -start_thread(void *arg) -{ - task_queue_t *queue = (task_queue_t *)arg; - while (1) { - pthread_mutex_lock(&queue->mutex); - while (queue->tasks_count == 0 && !queue->terminate) { - pthread_cond_wait(&queue->cond, &queue->mutex); - } - if (queue->tasks_count == 0 && queue->terminate) { - pthread_mutex_unlock(&queue->mutex); - break; - } - - if (queue->tasks_count > 0) { - dfsarg_solveh48_t task = queue->tasks[queue->front]; - queue->front = (queue->front + 1) % MAX_QUEUE_SIZE; - queue->tasks_count--; - queue->active++; - pthread_mutex_unlock(&queue->mutex); - - solve_h48_single(&task, queue); - - pthread_mutex_lock(&queue->mutex); - queue->active--; - - if(queue->tasks_count == 0 && queue->active == 0) - pthread_cond_signal(&queue->active_cond); - } - pthread_mutex_unlock(&queue->mutex); - } - return NULL; -} - -STATIC int64_t -solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) -{ - dfsarg_solveh48_t queue[MAX_QUEUE_SIZE]; - int front = 0, rear = 0; - dfsarg_solveh48_t nextarg; - int depth = 0; - int nodes_at_current_depth = 1; - int nodes_at_next_depth = 0; - queue[rear++] = *arg_zero; - - dfsarg_solveh48_t task_pool[MAX_QUEUE_SIZE]; - - while (front < rear){ - dfsarg_solveh48_t arg = queue[front++]; - nodes_at_current_depth--; - - if (*arg.nsols == arg.maxsolutions) - return 1; - - if (issolved(arg.cube)){ - if (arg.nmoves + arg.npremoves != arg.depth) - continue; - solve_h48_appendsolution(&arg); - continue; - } - - arg.nissbranch = MM_NORMAL; - uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch); - - for (uint8_t m = 0; m < 18; m++){ - if (allowed & (1 << m)){ - nextarg = arg; - nextarg.nmoves = arg.nmoves + 1; - nextarg.moves[arg.nmoves] = m; - nextarg.cube = move(arg.cube, m); - nextarg.inverse = premove(arg.inverse, m); - - if (nextarg.nmoves == BFS_DEPTH){ - dfsarg_solveh48_t *task = &task_pool[rear % MAX_QUEUE_SIZE]; - *task = nextarg; - submit_task(tq, *task); - } else { - queue[rear++] = nextarg; - nodes_at_next_depth++; - } - } - } - if (nodes_at_current_depth == 0){ - nodes_at_current_depth = nodes_at_next_depth; - nodes_at_next_depth = 0; - LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", *nextarg.nsols, depth++); - } - if (depth == BFS_DEPTH) return 0; - } - return 1; -} - -STATIC int64_t -solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq) -{ - dfsarg_solveh48_t nextarg; - int64_t ret; - uint8_t m; - - if (*arg->nsols == arg->maxsolutions) - return 0; - - if (solve_h48_stop(arg)) - return 0; - - if (issolved(arg->cube)){ - if (arg->nmoves + arg->npremoves != arg->depth) - return 0; - solve_h48_appendsolution_thread(arg, tq); - return 1; - } - - nextarg = *arg; - ret = 0; - uint32_t allowed; - if (arg->nissbranch & MM_INVERSE){ - allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch); - for (m = 0; m < 18; m++){ - if (allowed & (1 << m)){ - nextarg.npremoves = arg->npremoves + 1; - nextarg.premoves[arg->npremoves] = m; - nextarg.inverse = move(arg->inverse, m); - nextarg.cube = premove(arg->cube, m); - ret += solve_h48_single(&nextarg, tq); - } - } - } else { - allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch); - for (m = 0; m < 18; m++){ - if (allowed & (1 << m)){ - nextarg.nmoves = arg->nmoves + 1; - nextarg.moves[arg->nmoves] = m; - nextarg.cube = move(arg->cube, m); - nextarg.inverse = premove(arg->inverse, m); - ret += solve_h48_single(&nextarg, tq); - } - } - } - return ret; -} - -STATIC int64_t -solve_h48_parent( - cube_t cube, - int8_t minmoves, - int8_t maxmoves, - int8_t maxsolutions, - const void *data, - char *solutions) -{ - int64_t nsols = 0; - int p_depth = 0; - dfsarg_solveh48_t arg; - tableinfo_t info; - pthread_t threads[THREADS]; - - if (!readtableinfo_n(data, 2, &info)){ - LOG("solve_h48: error reading table\n"); - return 0; - } - - arg = (dfsarg_solveh48_t){ - .cube = cube, - .inverse = inverse(cube), - .nsols = &nsols, - .maxsolutions = maxsolutions, - .h = info.h48h, - .k = info.bits, - .cocsepdata = get_cocsepdata_ptr(data), - .h48data = get_h48data_ptr(data), - .nextsol = &solutions}; - - task_queue_t q; - init_queue(&q); - if (solve_h48_bfs(&arg, &q)) - return nsols; - - task_queue_t nq; - init_queue(&nq); - - for (int i = 0; i < THREADS; i++){ - pthread_create(&threads[i], NULL, &start_thread, &nq); - } - - nsols = 0; - for (p_depth = minmoves > BFS_DEPTH ? minmoves : BFS_DEPTH; - p_depth <= maxmoves && nsols < maxsolutions; - p_depth++) - { - LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", nsols, p_depth); - copy_queue(&q, &nq, p_depth, &nsols); - - pthread_mutex_lock(&nq.mutex); - while (nq.active > 0 || nq.tasks_count > 0) - pthread_cond_wait(&nq.active_cond, &nq.mutex); - pthread_mutex_unlock(&nq.mutex); - } - - atomic_store(&nq.terminate, true); - pthread_cond_broadcast(&nq.cond); - - for (int i = 0; i < THREADS; i++){ - pthread_join(threads[i], NULL); - } - **arg.nextsol = '\0'; - (*arg.nextsol)++; - return nsols; -} diff --git a/tools/200_solve_small/solve_small.c b/tools/200_solve_small/solve_small.c index f1037b4..d476bce 100644 --- a/tools/200_solve_small/solve_small.c +++ b/tools/200_solve_small/solve_small.c @@ -1,5 +1,3 @@ -#include - #include "../tool.h" const char *solver = "h48"; -- cgit v1.3