From 9ac266c76f39620d8343e46ca41cb09d1534384c Mon Sep 17 00:00:00 2001 From: Sebastiano Tronto Date: Sat, 7 Dec 2024 16:38:40 +0100 Subject: Merge the "solver-experiments" branch that I have been working on for a few weeks. This include mainly three things: 1. Various tweaks for a total performance gain of around 30%. 2. Take into account symmetries and avoid repeated work. This required a re-work of the splitting into tasks before the solve. 3. Add a second fallback table (eoesep). This gives huge performance gains for particular scrambles (e.g. superflip). After merging this commit, remove and re-generate all pruning tables. Squashed commit of the following: commit 60f0705d2d69050e6a30581a2810f686d6f69b80 Author: Sebastiano Tronto Date: Sat Dec 7 16:06:48 2024 +0100 Fix indentation commit cc5d489a251812b6188c0ba264ac6cb2236f1afe Author: Sebastiano Tronto Date: Sat Dec 7 15:56:19 2024 +0100 Updated documentation commit a3f605dd628546e52564f82b139feb473b0725f3 Author: Sebastiano Tronto Date: Sat Dec 7 14:01:11 2024 +0100 use eoesep table as second fallback commit c75e43c9116c64f97e92b0fe038be8a032925a72 Author: Sebastiano Tronto Date: Fri Dec 6 16:13:23 2024 +0100 First commit for gendata_eoesep commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248 Author: Sebastiano Tronto Date: Tue Dec 3 17:31:00 2024 +0100 Add scramble to tool commit 66866cb71dea4ca8278ecb9e90ff4295771feb42 Author: Sebastiano Tronto Date: Tue Dec 3 17:22:59 2024 +0100 Added tool to check multiple solutions commit ef65611c772c3996bddca8d181da3538e0af1674 Author: Sebastiano Tronto Date: Tue Dec 3 17:16:20 2024 +0100 Write all solutions for symmetric positions commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e Author: Sebastiano Tronto Date: Tue Nov 26 09:14:54 2024 +0100 Added symmetry filter (TODO: print excluded solutions) commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb Author: Sebastiano Tronto Date: Mon Nov 25 14:51:13 2024 +0100 Improved task split commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba Author: Sebastiano Tronto Date: Fri Nov 22 19:06:41 2024 +0100 Reworked tasks for multi-threading in view of symmetry filter commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f Author: Sebastiano Tronto Date: Thu Oct 31 15:37:43 2024 +0100 Added transform move commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6 Author: Sebastiano Tronto Date: Thu Oct 31 09:29:15 2024 +0100 Clarified doc commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954 Author: Sebastiano Tronto Date: Thu Oct 31 08:36:58 2024 +0100 Handle solved cube correctly commit 57705cbc4982e3abe97a36ed64871738d4f721c0 Author: Sebastiano Tronto Date: Thu Oct 31 08:24:30 2024 +0100 Close file commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898 Author: Sebastiano Tronto Date: Tue Oct 29 15:05:48 2024 +0100 Removed stats tool commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9 Author: Sebastiano Tronto Date: Tue Oct 29 15:01:51 2024 +0100 Updated theory doc commit 39c315af562bc4ce896f41004388a4c34d475d37 Author: Sebastiano Tronto Date: Tue Oct 29 14:51:40 2024 +0100 Remove unused constants commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d Author: Sebastiano Tronto Date: Tue Oct 29 10:20:38 2024 +0100 Add tool to solve scrambles from file commit 07e2918c216636891b1fa6adecc9756086a901e9 Author: Sebastiano Tronto Date: Mon Oct 28 17:00:00 2024 +0100 Add make table to tool commit f5e5266c654eb027a5a35c57cc618555246f5e5e Author: Sebastiano Tronto Date: Mon Oct 28 09:35:49 2024 +0100 Remove old solver, other small things commit a1ec78025b7959dbb845213f7f4e6851ecebc204 Author: Sebastiano Tronto Date: Sun Oct 27 02:00:29 2024 +0200 Improvements commit 8eea23dbe888d923e662e24ae969130e2c67b999 Author: Sebastiano Tronto Date: Sat Oct 26 12:24:19 2024 +0200 Makefile fix commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1 Author: Sebastiano Tronto Date: Fri Oct 25 18:25:09 2024 +0200 More performance gains commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4 Author: Sebastiano Tronto Date: Fri Oct 25 15:53:20 2024 +0200 Alternative solver implementation, small performance gain --- src/solvers/h48/solve_multithread.h | 350 ------------------------------------ 1 file changed, 350 deletions(-) delete mode 100644 src/solvers/h48/solve_multithread.h (limited to 'src/solvers/h48/solve_multithread.h') diff --git a/src/solvers/h48/solve_multithread.h b/src/solvers/h48/solve_multithread.h deleted file mode 100644 index 72f519e..0000000 --- a/src/solvers/h48/solve_multithread.h +++ /dev/null @@ -1,350 +0,0 @@ -#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; - _Atomic long long nodes_visited_global; - _Atomic long long table_fallbacks_global; -} 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, uint64_t, - const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]); - -STATIC void -solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq) -{ - pthread_mutex_lock(&tq->mutex); - int64_t strl = 0; - uint8_t invertedpremoves[MAXLEN]; - char *solution = *arg->nextsol; - - strl = writemoves( - arg->moves, arg->nmoves, arg->solutions_size, *arg->nextsol); - - if (strl < 0) - goto solve_h48_appendsolution_thread_error; - *arg->nextsol += strl-1; - arg->solutions_size -= strl-1; - - if (arg->npremoves) - { - **arg->nextsol = ' '; - (*arg->nextsol)++; - arg->solutions_size--; - - invertmoves(arg->premoves, arg->npremoves, invertedpremoves); - strl = writemoves(invertedpremoves, - arg->npremoves, arg->solutions_size, *arg->nextsol); - - if (strl < 0) - goto solve_h48_appendsolution_thread_error; - *arg->nextsol += strl-1; - arg->solutions_size -= strl-1; - } - LOG("Solution found: %s\n", solution); - - **arg->nextsol = '\n'; - (*arg->nextsol)++; - arg->solutions_size--; - (*arg->nsols)++; - -solve_h48_appendsolution_thread_error: - /* We could add some logging, but writemoves() already does */ - 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); - queue->nodes_visited_global += task.nodes_visited; - queue->table_fallbacks_global += task.table_fallbacks; - - 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); - } - } - } - - arg->nodes_visited = nextarg.nodes_visited; - arg->table_fallbacks = nextarg.table_fallbacks; - return ret; -} - -STATIC int64_t -solve_h48_multithread( - cube_t cube, - int8_t minmoves, - int8_t maxmoves, - int8_t maxsolutions, - uint64_t data_size, - const void *data, - uint64_t solutions_size, - char *solutions, - long long stats[static NISSY_SIZE_SOLVE_STATS] -) -{ - _Atomic int64_t nsols = 0; - int p_depth = 0; - dfsarg_solveh48_t arg; - tableinfo_t info, fbinfo; - pthread_t threads[THREADS]; - - if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK) - goto solve_h48_multithread_error_data; - - arg = (dfsarg_solveh48_t){ - .cube = cube, - .inverse = inverse(cube), - .nsols = &nsols, - .depth = minmoves, - .maxsolutions = maxsolutions, - .h = info.h48h, - .k = info.bits, - .base = info.base, - .cocsepdata = (uint32_t *)((char *)data + INFOSIZE), - .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE, - .solutions_size = solutions_size, - .nextsol = &solutions, - .nodes_visited = 0, - .table_fallbacks = 0 - }; - - if (info.bits == 2) { - if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK) - goto solve_h48_multithread_error_data; - /* We only support h0k4 as fallback table */ - if (fbinfo.h48h != 0 || fbinfo.bits != 4) - goto solve_h48_multithread_error_data; - arg.h48data_fallback = arg.h48data + info.next; - } else { - arg.h48data_fallback = NULL; - } - - task_queue_t q; - init_queue(&q); - if (solve_h48_bfs(&arg, &q, maxmoves)) - return nsols; - - task_queue_t nq; - init_queue(&nq); - - nq.nodes_visited_global = nq.table_fallbacks_global = 0; - 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'; - - stats[0] = nq.nodes_visited_global; - stats[1] = nq.table_fallbacks_global; - LOG("Nodes visited: %lld\nTable fallbacks: %lld\n", - nq.nodes_visited_global, nq.table_fallbacks_global); - - return nsols; - -solve_h48_multithread_error_data: LOG("solve_h48: error reading table\n"); return NISSY_ERROR_DATA; -} -- cgit v1.3