aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48/solve_multithread.h
diff options
context:
space:
mode:
authorSebastiano Tronto <sebastiano@tronto.net>2024-12-07 16:38:40 +0100
committerSebastiano Tronto <sebastiano@tronto.net>2024-12-07 16:38:40 +0100
commit9ac266c76f39620d8343e46ca41cb09d1534384c (patch)
tree823bd419d99fe0f00e6b5b713237a73b4ec7ffca /src/solvers/h48/solve_multithread.h
parentea25a7ccad625c4e664dfd114147971b8a2677f3 (diff)
downloadnissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.tar.gz
nissy-core-9ac266c76f39620d8343e46ca41cb09d1534384c.zip
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 <sebastiano@tronto.net> Date: Sat Dec 7 16:06:48 2024 +0100 Fix indentation commit cc5d489a251812b6188c0ba264ac6cb2236f1afe Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Dec 7 15:56:19 2024 +0100 Updated documentation commit a3f605dd628546e52564f82b139feb473b0725f3 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Dec 7 14:01:11 2024 +0100 use eoesep table as second fallback commit c75e43c9116c64f97e92b0fe038be8a032925a72 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Dec 6 16:13:23 2024 +0100 First commit for gendata_eoesep commit fea7688ab8bdc5ae0c3480622e2510a3bcd39248 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Dec 3 17:31:00 2024 +0100 Add scramble to tool commit 66866cb71dea4ca8278ecb9e90ff4295771feb42 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Dec 3 17:22:59 2024 +0100 Added tool to check multiple solutions commit ef65611c772c3996bddca8d181da3538e0af1674 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Dec 3 17:16:20 2024 +0100 Write all solutions for symmetric positions commit e3ded26db7d7d4ae7c0e2488151ed14f581f7b8e Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Nov 26 09:14:54 2024 +0100 Added symmetry filter (TODO: print excluded solutions) commit 864c437a9751c58d58562650ca9eba4a9e6ad3eb Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon Nov 25 14:51:13 2024 +0100 Improved task split commit b88926d36d7ab0c64c5fe3bb954fd15d41267fba Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Nov 22 19:06:41 2024 +0100 Reworked tasks for multi-threading in view of symmetry filter commit 26fa653f97df8cd601aecb80eaf89f0a00e9ba9f Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 15:37:43 2024 +0100 Added transform move commit 19f655ef94d658eaa2fefb5cea3c167a3ec58db6 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 09:29:15 2024 +0100 Clarified doc commit 3b0fe1e5ef8b628854e30f0f0067300e2763c954 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 08:36:58 2024 +0100 Handle solved cube correctly commit 57705cbc4982e3abe97a36ed64871738d4f721c0 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Thu Oct 31 08:24:30 2024 +0100 Close file commit fc7d462b58bcf3d3a3fbf26c1f3bd04c640a4898 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 15:05:48 2024 +0100 Removed stats tool commit 359bf7cb49ef405ee76ed662207d47cb2abcc5a9 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 15:01:51 2024 +0100 Updated theory doc commit 39c315af562bc4ce896f41004388a4c34d475d37 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 14:51:40 2024 +0100 Remove unused constants commit 57a5d24538aa59a4df9221dad2f99e9f0286bd9d Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Tue Oct 29 10:20:38 2024 +0100 Add tool to solve scrambles from file commit 07e2918c216636891b1fa6adecc9756086a901e9 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon Oct 28 17:00:00 2024 +0100 Add make table to tool commit f5e5266c654eb027a5a35c57cc618555246f5e5e Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Mon Oct 28 09:35:49 2024 +0100 Remove old solver, other small things commit a1ec78025b7959dbb845213f7f4e6851ecebc204 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sun Oct 27 02:00:29 2024 +0200 Improvements commit 8eea23dbe888d923e662e24ae969130e2c67b999 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Sat Oct 26 12:24:19 2024 +0200 Makefile fix commit 3fc3927beacc78971cefeb42da8d71fe6c015fc1 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Oct 25 18:25:09 2024 +0200 More performance gains commit 7b4efa1f9af9722de1ab9ccfc27899825a0d12c4 Author: Sebastiano Tronto <sebastiano@tronto.net> Date: Fri Oct 25 15:53:20 2024 +0200 Alternative solver implementation, small performance gain
Diffstat (limited to 'src/solvers/h48/solve_multithread.h')
-rw-r--r--src/solvers/h48/solve_multithread.h350
1 files changed, 0 insertions, 350 deletions
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 @@
1#define MAX_QUEUE_SIZE 244
2#define BFS_DEPTH 2
3
4typedef struct {
5 dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE];
6 int front;
7 int rear;
8 int tasks_count;
9 int active;
10 pthread_mutex_t mutex;
11 pthread_cond_t cond;
12 pthread_cond_t active_cond;
13 atomic_bool terminate;
14 _Atomic long long nodes_visited_global;
15 _Atomic long long table_fallbacks_global;
16} task_queue_t;
17
18STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *);
19STATIC void init_queue(task_queue_t *);
20STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t);
21STATIC void copy_queue(task_queue_t *, task_queue_t *, int, _Atomic int64_t *);
22STATIC void *start_thread(void *);
23STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *, int8_t);
24STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *);
25STATIC int64_t solve_h48_multithread(cube_t, int8_t, int8_t, int8_t, uint64_t,
26 const void *, uint64_t, char *, long long [static NISSY_SIZE_SOLVE_STATS]);
27
28STATIC void
29solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq)
30{
31 pthread_mutex_lock(&tq->mutex);
32 int64_t strl = 0;
33 uint8_t invertedpremoves[MAXLEN];
34 char *solution = *arg->nextsol;
35
36 strl = writemoves(
37 arg->moves, arg->nmoves, arg->solutions_size, *arg->nextsol);
38
39 if (strl < 0)
40 goto solve_h48_appendsolution_thread_error;
41 *arg->nextsol += strl-1;
42 arg->solutions_size -= strl-1;
43
44 if (arg->npremoves)
45 {
46 **arg->nextsol = ' ';
47 (*arg->nextsol)++;
48 arg->solutions_size--;
49
50 invertmoves(arg->premoves, arg->npremoves, invertedpremoves);
51 strl = writemoves(invertedpremoves,
52 arg->npremoves, arg->solutions_size, *arg->nextsol);
53
54 if (strl < 0)
55 goto solve_h48_appendsolution_thread_error;
56 *arg->nextsol += strl-1;
57 arg->solutions_size -= strl-1;
58 }
59 LOG("Solution found: %s\n", solution);
60
61 **arg->nextsol = '\n';
62 (*arg->nextsol)++;
63 arg->solutions_size--;
64 (*arg->nsols)++;
65
66solve_h48_appendsolution_thread_error:
67 /* We could add some logging, but writemoves() already does */
68 pthread_mutex_unlock(&tq->mutex);
69}
70
71STATIC void
72init_queue(task_queue_t *queue)
73{
74 queue->front = 0;
75 queue->rear = 0;
76 queue->tasks_count = 0;
77 queue->active = 0;
78 queue->terminate = ATOMIC_VAR_INIT(false);
79 pthread_mutex_init(&queue->mutex, NULL);
80 pthread_cond_init(&queue->cond, NULL);
81 pthread_cond_init(&queue->active_cond, NULL);
82}
83
84STATIC void
85submit_task(task_queue_t *queue, dfsarg_solveh48_t task)
86{
87 pthread_mutex_lock(&queue->mutex);
88 queue->tasks[queue->rear] = task;
89 queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
90 queue->tasks_count++;
91 pthread_cond_broadcast(&queue->cond);
92 pthread_mutex_unlock(&queue->mutex);
93}
94
95STATIC void
96copy_queue(task_queue_t *src, task_queue_t *dest, int depth, _Atomic int64_t *nsols)
97{
98 pthread_mutex_lock(&dest->mutex);
99 for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE)
100 {
101 dest->tasks[i] = src->tasks[i];
102 dest->tasks[i].depth = depth;
103 }
104 dest->front = src->front;
105 dest->rear = src->rear;
106 dest->tasks_count = src->tasks_count;
107 pthread_cond_broadcast(&dest->cond);
108 pthread_mutex_unlock(&dest->mutex);
109}
110
111STATIC void *
112start_thread(void *arg)
113{
114 task_queue_t *queue = (task_queue_t *)arg;
115 while (1) {
116 pthread_mutex_lock(&queue->mutex);
117 while (queue->tasks_count == 0 && !queue->terminate) {
118 pthread_cond_wait(&queue->cond, &queue->mutex);
119 }
120 if (queue->tasks_count == 0 && queue->terminate) {
121 pthread_mutex_unlock(&queue->mutex);
122 break;
123 }
124
125 if (queue->tasks_count > 0) {
126 dfsarg_solveh48_t task = queue->tasks[queue->front];
127 queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
128 queue->tasks_count--;
129 queue->active++;
130 pthread_mutex_unlock(&queue->mutex);
131
132 solve_h48_single(&task, queue);
133 queue->nodes_visited_global += task.nodes_visited;
134 queue->table_fallbacks_global += task.table_fallbacks;
135
136 pthread_mutex_lock(&queue->mutex);
137 queue->active--;
138
139 if(queue->tasks_count == 0 && queue->active == 0)
140 pthread_cond_signal(&queue->active_cond);
141 }
142 pthread_mutex_unlock(&queue->mutex);
143 }
144 return NULL;
145}
146
147STATIC int64_t
148solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq, int8_t maxmoves)
149{
150 dfsarg_solveh48_t queue[MAX_QUEUE_SIZE];
151 int front = 0, rear = 0;
152 dfsarg_solveh48_t nextarg;
153 int depth = 0;
154 int nodes_at_current_depth = 1;
155 int nodes_at_next_depth = 0;
156 queue[rear++] = *arg_zero;
157
158 dfsarg_solveh48_t task_pool[MAX_QUEUE_SIZE];
159
160 while (front < rear){
161 dfsarg_solveh48_t arg = queue[front++];
162 nodes_at_current_depth--;
163
164 if (*arg.nsols == arg.maxsolutions)
165 return 1;
166
167 if (issolved(arg.cube)){
168 if (arg.nmoves + arg.npremoves >= arg.depth && arg.nmoves + arg.npremoves <= maxmoves)
169 solve_h48_appendsolution(&arg);
170 continue;
171 }
172
173 arg.nissbranch = MM_NORMAL;
174 uint32_t allowed = allowednextmove_h48(arg.moves, arg.nmoves, arg.nissbranch);
175
176 for (uint8_t m = 0; m < 18; m++){
177 if (allowed & (1 << m)){
178 nextarg = arg;
179 nextarg.nmoves = arg.nmoves + 1;
180 nextarg.moves[arg.nmoves] = m;
181 nextarg.cube = move(arg.cube, m);
182 nextarg.inverse = premove(arg.inverse, m);
183
184 if (nextarg.nmoves == BFS_DEPTH){
185 dfsarg_solveh48_t *task = &task_pool[rear % MAX_QUEUE_SIZE];
186 *task = nextarg;
187 submit_task(tq, *task);
188 } else {
189 queue[rear++] = nextarg;
190 nodes_at_next_depth++;
191 }
192 }
193 }
194 if (nodes_at_current_depth == 0){
195 nodes_at_current_depth = nodes_at_next_depth;
196 nodes_at_next_depth = 0;
197 LOG("Found %" PRId64 " solutions, searching at depth %" PRId8 "\n", *nextarg.nsols, depth++);
198 }
199 if (depth == BFS_DEPTH) return 0;
200 }
201 return 1;
202}
203
204STATIC int64_t
205solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq)
206{
207 dfsarg_solveh48_t nextarg;
208 int64_t ret;
209 uint8_t m;
210
211 if (*arg->nsols == arg->maxsolutions)
212 return 0;
213
214 if (solve_h48_stop(arg))
215 return 0;
216
217 if (issolved(arg->cube)){
218 if (arg->nmoves + arg->npremoves != arg->depth)
219 return 0;
220 solve_h48_appendsolution_thread(arg, tq);
221 return 1;
222 }
223
224 nextarg = *arg;
225 ret = 0;
226 uint32_t allowed;
227 if (arg->nissbranch & MM_INVERSE){
228 allowed = allowednextmove_h48(arg->premoves, arg->npremoves, arg->nissbranch);
229 for (m = 0; m < 18; m++){
230 if (allowed & (1 << m)){
231 nextarg.npremoves = arg->npremoves + 1;
232 nextarg.premoves[arg->npremoves] = m;
233 nextarg.inverse = move(arg->inverse, m);
234 nextarg.cube = premove(arg->cube, m);
235 ret += solve_h48_single(&nextarg, tq);
236 }
237 }
238 } else {
239 allowed = allowednextmove_h48(arg->moves, arg->nmoves, arg->nissbranch);
240 for (m = 0; m < 18; m++){
241 if (allowed & (1 << m)){
242 nextarg.nmoves = arg->nmoves + 1;
243 nextarg.moves[arg->nmoves] = m;
244 nextarg.cube = move(arg->cube, m);
245 nextarg.inverse = premove(arg->inverse, m);
246 ret += solve_h48_single(&nextarg, tq);
247 }
248 }
249 }
250
251 arg->nodes_visited = nextarg.nodes_visited;
252 arg->table_fallbacks = nextarg.table_fallbacks;
253 return ret;
254}
255
256STATIC int64_t
257solve_h48_multithread(
258 cube_t cube,
259 int8_t minmoves,
260 int8_t maxmoves,
261 int8_t maxsolutions,
262 uint64_t data_size,
263 const void *data,
264 uint64_t solutions_size,
265 char *solutions,
266 long long stats[static NISSY_SIZE_SOLVE_STATS]
267)
268{
269 _Atomic int64_t nsols = 0;
270 int p_depth = 0;
271 dfsarg_solveh48_t arg;
272 tableinfo_t info, fbinfo;
273 pthread_t threads[THREADS];
274
275 if (readtableinfo_n(data_size, data, 2, &info) != NISSY_OK)
276 goto solve_h48_multithread_error_data;
277
278 arg = (dfsarg_solveh48_t){
279 .cube = cube,
280 .inverse = inverse(cube),
281 .nsols = &nsols,
282 .depth = minmoves,
283 .maxsolutions = maxsolutions,
284 .h = info.h48h,
285 .k = info.bits,
286 .base = info.base,
287 .cocsepdata = (uint32_t *)((char *)data + INFOSIZE),
288 .h48data = (uint8_t *)data + COCSEP_FULLSIZE + INFOSIZE,
289 .solutions_size = solutions_size,
290 .nextsol = &solutions,
291 .nodes_visited = 0,
292 .table_fallbacks = 0
293 };
294
295 if (info.bits == 2) {
296 if (readtableinfo_n(data_size, data, 3, &fbinfo) != NISSY_OK)
297 goto solve_h48_multithread_error_data;
298 /* We only support h0k4 as fallback table */
299 if (fbinfo.h48h != 0 || fbinfo.bits != 4)
300 goto solve_h48_multithread_error_data;
301 arg.h48data_fallback = arg.h48data + info.next;
302 } else {
303 arg.h48data_fallback = NULL;
304 }
305
306 task_queue_t q;
307 init_queue(&q);
308 if (solve_h48_bfs(&arg, &q, maxmoves))
309 return nsols;
310
311 task_queue_t nq;
312 init_queue(&nq);
313
314 nq.nodes_visited_global = nq.table_fallbacks_global = 0;
315 for (int i = 0; i < THREADS; i++) {
316 pthread_create(&threads[i], NULL, &start_thread, &nq);
317 }
318
319 nsols = 0;
320 for (p_depth = minmoves > BFS_DEPTH ? minmoves : BFS_DEPTH;
321 p_depth <= maxmoves && nsols < maxsolutions;
322 p_depth++)
323 {
324 LOG("Found %" PRId64 " solutions, "
325 "searching at depth %" PRId8 "\n", nsols, p_depth);
326 copy_queue(&q, &nq, p_depth, &nsols);
327
328 pthread_mutex_lock(&nq.mutex);
329 while (nq.active > 0 || nq.tasks_count > 0)
330 pthread_cond_wait(&nq.active_cond, &nq.mutex);
331 pthread_mutex_unlock(&nq.mutex);
332 }
333
334 atomic_store(&nq.terminate, true);
335 pthread_cond_broadcast(&nq.cond);
336
337 for (int i = 0; i < THREADS; i++) {
338 pthread_join(threads[i], NULL);
339 }
340 **arg.nextsol = '\0';
341
342 stats[0] = nq.nodes_visited_global;
343 stats[1] = nq.table_fallbacks_global;
344 LOG("Nodes visited: %lld\nTable fallbacks: %lld\n",
345 nq.nodes_visited_global, nq.table_fallbacks_global);
346
347 return nsols;
348
349solve_h48_multithread_error_data: LOG("solve_h48: error reading table\n"); return NISSY_ERROR_DATA;
350}

Generated with cgit - Back to sebastiano.tronto.net