aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48/solve_multithread.h
diff options
context:
space:
mode:
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