aboutsummaryrefslogtreecommitdiff
path: root/src/solvers/h48
diff options
context:
space:
mode:
Diffstat (limited to 'src/solvers/h48')
-rw-r--r--src/solvers/h48/h48.h2
-rw-r--r--src/solvers/h48/solve.h4
-rw-r--r--src/solvers/h48/solve_multithread.h (renamed from src/solvers/h48/thread.h)23
3 files changed, 14 insertions, 15 deletions
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 @@
4#include "gendata_h48.h" 4#include "gendata_h48.h"
5#include "stats.h" 5#include "stats.h"
6#include "solve.h" 6#include "solve.h"
7#include "thread.h" 7#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 {
4 int8_t nmoves; 4 int8_t nmoves;
5 int8_t depth; 5 int8_t depth;
6 uint8_t moves[MAXLEN]; 6 uint8_t moves[MAXLEN];
7 int64_t *nsols; 7 _Atomic int64_t *nsols;
8 int64_t maxsolutions; 8 int64_t maxsolutions;
9 uint8_t h; 9 uint8_t h;
10 uint8_t k; 10 uint8_t k;
@@ -167,7 +167,7 @@ solve_h48(
167 char *solutions 167 char *solutions
168) 168)
169{ 169{
170 int64_t nsols; 170 _Atomic int64_t nsols;
171 dfsarg_solveh48_t arg; 171 dfsarg_solveh48_t arg;
172 tableinfo_t info; 172 tableinfo_t info;
173 173
diff --git a/src/solvers/h48/thread.h b/src/solvers/h48/solve_multithread.h
index fb5ccbc..86171a9 100644
--- a/src/solvers/h48/thread.h
+++ b/src/solvers/h48/solve_multithread.h
@@ -1,7 +1,6 @@
1#include <stdatomic.h>
2
3#define MAX_QUEUE_SIZE 244 1#define MAX_QUEUE_SIZE 244
4#define BFS_DEPTH 2 2#define BFS_DEPTH 2
3
5typedef struct { 4typedef struct {
6 dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE]; 5 dfsarg_solveh48_t tasks[MAX_QUEUE_SIZE];
7 int front; 6 int front;
@@ -17,11 +16,11 @@ typedef struct {
17STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *); 16STATIC void solve_h48_appendsolution_thread(dfsarg_solveh48_t *, task_queue_t *);
18STATIC void init_queue(task_queue_t *); 17STATIC void init_queue(task_queue_t *);
19STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t); 18STATIC void submit_task(task_queue_t *, dfsarg_solveh48_t);
20STATIC void copy_queue(task_queue_t *, task_queue_t *, int, int64_t *); 19STATIC void copy_queue(task_queue_t *, task_queue_t *, int, _Atomic int64_t *);
21STATIC void *start_thread(void *); 20STATIC void *start_thread(void *);
22STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *); 21STATIC int64_t solve_h48_bfs(dfsarg_solveh48_t *, task_queue_t *, int8_t);
23STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *); 22STATIC int64_t solve_h48_single(dfsarg_solveh48_t *, task_queue_t *);
24STATIC int64_t solve_h48_parent(cube_t, int8_t, int8_t, int8_t, const void *, char *); 23STATIC int64_t solve_h48_multithread(cube_t, int8_t, int8_t, int8_t, const void *, char *);
25 24
26STATIC void 25STATIC void
27solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq) 26solve_h48_appendsolution_thread(dfsarg_solveh48_t *arg, task_queue_t *tq)
@@ -76,7 +75,7 @@ submit_task(task_queue_t *queue, dfsarg_solveh48_t task)
76} 75}
77 76
78STATIC void 77STATIC void
79copy_queue(task_queue_t *src, task_queue_t *dest, int depth, int64_t *nsols) 78copy_queue(task_queue_t *src, task_queue_t *dest, int depth, _Atomic int64_t *nsols)
80{ 79{
81 pthread_mutex_lock(&dest->mutex); 80 pthread_mutex_lock(&dest->mutex);
82 for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE) 81 for (int i = src->front; i != src->rear; i = (i + 1) % MAX_QUEUE_SIZE)
@@ -126,7 +125,7 @@ start_thread(void *arg)
126} 125}
127 126
128STATIC int64_t 127STATIC int64_t
129solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq) 128solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq, int8_t maxmoves)
130{ 129{
131 dfsarg_solveh48_t queue[MAX_QUEUE_SIZE]; 130 dfsarg_solveh48_t queue[MAX_QUEUE_SIZE];
132 int front = 0, rear = 0; 131 int front = 0, rear = 0;
@@ -146,8 +145,7 @@ solve_h48_bfs(dfsarg_solveh48_t *arg_zero, task_queue_t *tq)
146 return 1; 145 return 1;
147 146
148 if (issolved(arg.cube)){ 147 if (issolved(arg.cube)){
149 if (arg.nmoves + arg.npremoves != arg.depth) 148 if (arg.nmoves + arg.npremoves >= arg.depth && arg.nmoves + arg.npremoves <= maxmoves)
150 continue;
151 solve_h48_appendsolution(&arg); 149 solve_h48_appendsolution(&arg);
152 continue; 150 continue;
153 } 151 }
@@ -233,7 +231,7 @@ solve_h48_single(dfsarg_solveh48_t *arg, task_queue_t *tq)
233} 231}
234 232
235STATIC int64_t 233STATIC int64_t
236solve_h48_parent( 234solve_h48_multithread(
237 cube_t cube, 235 cube_t cube,
238 int8_t minmoves, 236 int8_t minmoves,
239 int8_t maxmoves, 237 int8_t maxmoves,
@@ -241,7 +239,7 @@ solve_h48_parent(
241 const void *data, 239 const void *data,
242 char *solutions) 240 char *solutions)
243{ 241{
244 int64_t nsols = 0; 242 _Atomic int64_t nsols = 0;
245 int p_depth = 0; 243 int p_depth = 0;
246 dfsarg_solveh48_t arg; 244 dfsarg_solveh48_t arg;
247 tableinfo_t info; 245 tableinfo_t info;
@@ -256,6 +254,7 @@ solve_h48_parent(
256 .cube = cube, 254 .cube = cube,
257 .inverse = inverse(cube), 255 .inverse = inverse(cube),
258 .nsols = &nsols, 256 .nsols = &nsols,
257 .depth = minmoves,
259 .maxsolutions = maxsolutions, 258 .maxsolutions = maxsolutions,
260 .h = info.h48h, 259 .h = info.h48h,
261 .k = info.bits, 260 .k = info.bits,
@@ -265,7 +264,7 @@ solve_h48_parent(
265 264
266 task_queue_t q; 265 task_queue_t q;
267 init_queue(&q); 266 init_queue(&q);
268 if (solve_h48_bfs(&arg, &q)) 267 if (solve_h48_bfs(&arg, &q, maxmoves))
269 return nsols; 268 return nsols;
270 269
271 task_queue_t nq; 270 task_queue_t nq;

Generated with cgit - Back to sebastiano.tronto.net