diff options
| -rw-r--r-- | benchmarks/benchmarks.md | 97 | ||||
| -rw-r--r-- | benchmarks/img/17moves16threads.png | bin | 105137 -> 104342 bytes | |||
| -rw-r--r-- | benchmarks/img/17moves1thread.png | bin | 105843 -> 104609 bytes | |||
| -rw-r--r-- | benchmarks/img/17moves4threads.png | bin | 106968 -> 104584 bytes | |||
| -rw-r--r-- | benchmarks/img/18moves16threads.png | bin | 113796 -> 115032 bytes | |||
| -rw-r--r-- | benchmarks/img/18moves1thread.png | bin | 119054 -> 117902 bytes | |||
| -rw-r--r-- | benchmarks/img/18moves4threads.png | bin | 110846 -> 110291 bytes | |||
| -rw-r--r-- | benchmarks/img/19moves16threads.png | bin | 113456 -> 114582 bytes | |||
| -rw-r--r-- | benchmarks/img/19moves1thread.png | bin | 116385 -> 117000 bytes | |||
| -rw-r--r-- | benchmarks/img/19moves4threads.png | bin | 113611 -> 113747 bytes | |||
| -rw-r--r-- | benchmarks/img/20moves16threads.png | bin | 127744 -> 127705 bytes | |||
| -rw-r--r-- | benchmarks/img/20moves1thread.png | bin | 128805 -> 113466 bytes | |||
| -rw-r--r-- | benchmarks/img/20moves4threads.png | bin | 119709 -> 118980 bytes | |||
| -rw-r--r-- | benchmarks/results_h48.py | 48 | ||||
| -rw-r--r-- | src/solvers/h48/gendata_h48.h | 21 | ||||
| -rw-r--r-- | src/solvers/h48/solve.h | 36 |
16 files changed, 110 insertions, 92 deletions
diff --git a/benchmarks/benchmarks.md b/benchmarks/benchmarks.md index 33cd36e..adc3377 100644 --- a/benchmarks/benchmarks.md +++ b/benchmarks/benchmarks.md | |||
| @@ -70,32 +70,32 @@ Time per cube (in seconds, lower is better). | |||
| 70 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 70 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 71 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 71 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 72 | |vcube 212 |58.2 Gib| 0.11| 0.75| 3.43| 27.28| 19.30| | 72 | |vcube 212 |58.2 Gib| 0.11| 0.75| 3.43| 27.28| 19.30| |
| 73 | |H48 h11 |56.5 Gib| 0.15| 0.91| 4.08| 26.81| 26.90| | 73 | |H48 h11 |56.5 Gib| 0.14| 0.78| 3.74| 26.05| 20.27| |
| 74 | |vcube 404 |31.8 Gib| 0.23| 1.24| 6.10| 59.33| 268.26| | 74 | |vcube 404 |31.8 Gib| 0.23| 1.24| 6.10| 59.33| 268.26| |
| 75 | |H48 h10 |28.3 Gib| 0.27| 1.47| 6.75| 46.65| 60.55| | 75 | |H48 h10 |28.3 Gib| 0.25| 1.25| 6.33| 44.75| 48.70| |
| 76 | |vcube 308 |21.2 Gib| 0.17| 1.02| 6.20| 58.70| 604.35| | 76 | |vcube 308 |21.2 Gib| 0.17| 1.02| 6.20| 58.70| 604.35| |
| 77 | |H48 h9 |14.1 Gib| 0.38| 2.66| 12.21| | | | 77 | |H48 h9 |14.1 Gib| 0.36| 2.48| 11.73| | | |
| 78 | |vcube 208 | 7.3 Gib| 0.56| 4.36| 20.58| | | | 78 | |vcube 208 | 7.3 Gib| 0.56| 4.36| 20.58| | | |
| 79 | |H48 h8 | 7.1 Gib| 0.87| 6.61| 26.57| | | | 79 | |H48 h8 | 7.1 Gib| 0.79| 6.07| 25.58| | | |
| 80 | |H48 h7 | 3.5 Gib| 1.02| 8.21| 41.25| | | | 80 | |H48 h7 | 3.5 Gib| 1.06| 8.51| 42.97| | | |
| 81 | |vcube 112 | 2.4 Gib| 0.96| 9.29| 40.52| | | | 81 | |vcube 112 | 2.4 Gib| 0.96| 9.29| 40.52| | | |
| 82 | |H48 h6 | 1.8 Gib| 2.11| 15.95| 82.00| | | | 82 | |H48 h6 | 1.8 Gib| 2.11| 16.23| 81.30| | | |
| 83 | 83 | ||
| 84 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). | 84 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). |
| 85 | 85 | ||
| 86 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 86 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 87 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 87 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 88 | |vcube 212 |58.2 Gib| 6.43| 43.80| 199.38| 1587.43| 1122.73| | 88 | |vcube 212 |58.2 Gib| 6.43| 43.80| 199.38| 1587.43| 1122.73| |
| 89 | |H48 h11 |56.5 Gib| 8.73| 51.58| 230.38| 1514.85| 1520.10| | 89 | |H48 h11 |56.5 Gib| 8.11| 44.29| 211.50| 1471.86| 1145.45| |
| 90 | |vcube 404 |31.8 Gib| 7.40| 39.47| 194.01| 1887.94| 8535.87| | 90 | |vcube 404 |31.8 Gib| 7.40| 39.47| 194.01| 1887.94| 8535.87| |
| 91 | |H48 h10 |28.3 Gib| 7.70| 41.43| 190.75| 1317.96| 1710.78| | 91 | |H48 h10 |28.3 Gib| 7.03| 35.19| 178.96| 1264.32| 1375.96| |
| 92 | |vcube 308 |21.2 Gib| 3.51| 21.71| 131.50| 1245.26| 12819.94| | 92 | |vcube 308 |21.2 Gib| 3.51| 21.71| 131.50| 1245.26| 12819.94| |
| 93 | |H48 h9 |14.1 Gib| 5.31| 37.64| 172.53| | | | 93 | |H48 h9 |14.1 Gib| 5.09| 35.06| 165.70| | | |
| 94 | |vcube 208 | 7.3 Gib| 4.08| 31.74| 149.68| | | | 94 | |vcube 208 | 7.3 Gib| 4.08| 31.74| 149.68| | | |
| 95 | |H48 h8 | 7.1 Gib| 6.17| 46.72| 187.70| | | | 95 | |H48 h8 | 7.1 Gib| 5.60| 42.89| 180.75| | | |
| 96 | |H48 h7 | 3.5 Gib| 3.62| 29.01| 145.74| | | | 96 | |H48 h7 | 3.5 Gib| 3.74| 30.07| 151.82| | | |
| 97 | |vcube 112 | 2.4 Gib| 2.33| 22.53| 98.23| | | | 97 | |vcube 112 | 2.4 Gib| 2.33| 22.53| 98.23| | | |
| 98 | |H48 h6 | 1.8 Gib| 3.72| 28.19| 144.94| | | | 98 | |H48 h6 | 1.8 Gib| 3.73| 28.69| 143.70| | | |
| 99 | 99 | ||
| 100 | <img src="img/17moves1thread.png"> | 100 | <img src="img/17moves1thread.png"> |
| 101 | <img src="img/18moves1thread.png"> | 101 | <img src="img/18moves1thread.png"> |
| @@ -110,32 +110,32 @@ Time per cube (in seconds, lower is better). | |||
| 110 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 110 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 111 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 111 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 112 | |vcube 212 |58.2 Gib| 0.03| 0.27| 1.04| 7.70| (a) | | 112 | |vcube 212 |58.2 Gib| 0.03| 0.27| 1.04| 7.70| (a) | |
| 113 | |H48 h11 |56.5 Gib| 0.05| 0.26| 1.13| 7.60| 8.44| | 113 | |H48 h11 |56.5 Gib| 0.05| 0.23| 1.06| 7.07| 6.19| |
| 114 | |vcube 404 |31.8 Gib| 0.07| 0.30| 1.65| 16.17| (a) | | 114 | |vcube 404 |31.8 Gib| 0.07| 0.30| 1.65| 16.17| (a) | |
| 115 | |H48 h10 |28.3 Gib| 0.08| 0.39| 1.89| 13.07| 16.63| | 115 | |H48 h10 |28.3 Gib| 0.08| 0.37| 1.75| 13.54| 14.26| |
| 116 | |vcube 308 |21.2 Gib| 0.05| 0.35| 1.78| 16.61| (a) | | 116 | |vcube 308 |21.2 Gib| 0.05| 0.35| 1.78| 16.61| (a) | |
| 117 | |H48 h9 |14.1 Gib| 0.12| 0.77| 3.42| 24.72| 29.31| | 117 | |H48 h9 |14.1 Gib| 0.11| 0.74| 3.37| 24.44| 25.39| |
| 118 | |vcube 208 | 7.3 Gib| 0.16| 1.47| 5.86| | (a) | | 118 | |vcube 208 | 7.3 Gib| 0.16| 1.47| 5.86| | (a) | |
| 119 | |H48 h8 | 7.1 Gib| 0.26| 1.87| 7.84| | | | 119 | |H48 h8 | 7.1 Gib| 0.24| 1.71| 7.22| | | |
| 120 | |H48 h7 | 3.5 Gib| 0.30| 2.32| 11.74| | | | 120 | |H48 h7 | 3.5 Gib| 0.31| 2.40| 11.74| | | |
| 121 | |vcube 112 | 2.4 Gib| 0.29| 3.13| 11.95| | (a) | | 121 | |vcube 112 | 2.4 Gib| 0.29| 3.13| 11.95| | (a) | |
| 122 | |H48 h6 | 1.8 Gib| 0.63| 4.67| 24.67| | | | 122 | |H48 h6 | 1.8 Gib| 0.61| 4.65| 23.09| | | |
| 123 | 123 | ||
| 124 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). | 124 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). |
| 125 | 125 | ||
| 126 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 126 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 127 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 127 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 128 | |vcube 212 |58.2 Gib| 2.03| 15.69| 60.25| 447.97| (a) | | 128 | |vcube 212 |58.2 Gib| 2.03| 15.69| 60.25| 447.97| (a) | |
| 129 | |H48 h11 |56.5 Gib| 2.85| 14.76| 63.96| 429.69| 476.80| | 129 | |H48 h11 |56.5 Gib| 2.71| 13.18| 60.13| 399.70| 349.94| |
| 130 | |vcube 404 |31.8 Gib| 2.32| 9.50| 52.46| 514.50| (a) | | 130 | |vcube 404 |31.8 Gib| 2.32| 9.50| 52.46| 514.50| (a) | |
| 131 | |H48 h10 |28.3 Gib| 2.22| 11.01| 53.47| 369.40| 469.92| | 131 | |H48 h10 |28.3 Gib| 2.17| 10.32| 49.45| 382.53| 402.87| |
| 132 | |vcube 308 |21.2 Gib| 1.02| 7.52| 37.82| 352.36| (a) | | 132 | |vcube 308 |21.2 Gib| 1.02| 7.52| 37.82| 352.36| (a) | |
| 133 | |H48 h9 |14.1 Gib| 1.64| 10.83| 48.37| 349.20| 414.10| | 133 | |H48 h9 |14.1 Gib| 1.56| 10.45| 47.54| 345.21| 358.74| |
| 134 | |vcube 208 | 7.3 Gib| 1.18| 10.69| 42.63| | (a) | | 134 | |vcube 208 | 7.3 Gib| 1.18| 10.69| 42.63| | (a) | |
| 135 | |H48 h8 | 7.1 Gib| 1.81| 13.20| 55.35| | | | 135 | |H48 h8 | 7.1 Gib| 1.66| 12.08| 50.99| | | |
| 136 | |H48 h7 | 3.5 Gib| 1.07| 8.19| 41.47| | | | 136 | |H48 h7 | 3.5 Gib| 1.10| 8.46| 41.48| | | |
| 137 | |vcube 112 | 2.4 Gib| 0.69| 7.59| 28.97| | (a) | | 137 | |vcube 112 | 2.4 Gib| 0.69| 7.59| 28.97| | (a) | |
| 138 | |H48 h6 | 1.8 Gib| 1.11| 8.25| 43.60| | | | 138 | |H48 h6 | 1.8 Gib| 1.08| 8.21| 40.82| | | |
| 139 | 139 | ||
| 140 | (a) vcube cannot parallelize on a single scramble, the results for the | 140 | (a) vcube cannot parallelize on a single scramble, the results for the |
| 141 | superflip are going to be the same as in the single thread case. | 141 | superflip are going to be the same as in the single thread case. |
| @@ -153,32 +153,32 @@ Time per cube (in seconds, lower is better). | |||
| 153 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 153 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 154 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 154 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 155 | |vcube 212 |58.2 Gib| 0.02| 0.13| 0.45| 2.84| (a) | | 155 | |vcube 212 |58.2 Gib| 0.02| 0.13| 0.45| 2.84| (a) | |
| 156 | |H48 h11 |56.5 Gib| 0.02| 0.10| 0.37| 2.31| 3.47| | 156 | |H48 h11 |56.5 Gib| 0.02| 0.08| 0.35| 2.26| 2.49| |
| 157 | |vcube 404 |31.8 Gib| 0.04| 0.14| 0.65| 6.08| (a) | | 157 | |vcube 404 |31.8 Gib| 0.04| 0.14| 0.65| 6.08| (a) | |
| 158 | |H48 h10 |28.3 Gib| 0.03| 0.14| 0.62| 4.24| 7.07| | 158 | |H48 h10 |28.3 Gib| 0.03| 0.13| 0.60| 4.15| 5.62| |
| 159 | |vcube 308 |21.2 Gib| 0.03| 0.19| 0.78| 6.67| (a) | | 159 | |vcube 308 |21.2 Gib| 0.03| 0.19| 0.78| 6.67| (a) | |
| 160 | |H48 h9 |14.1 Gib| 0.04| 0.26| 1.15| 8.15| 12.18| | 160 | |H48 h9 |14.1 Gib| 0.04| 0.25| 1.10| 8.04| 10.71| |
| 161 | |vcube 208 | 7.3 Gib| 0.08| 0.79| 2.43| | (a) | | 161 | |vcube 208 | 7.3 Gib| 0.08| 0.79| 2.43| | (a) | |
| 162 | |H48 h8 | 7.1 Gib| 0.09| 0.64| 2.50| | | | 162 | |H48 h8 | 7.1 Gib| 0.08| 0.58| 2.42| | | |
| 163 | |H48 h7 | 3.5 Gib| 0.11| 0.79| 3.88| | | | 163 | |H48 h7 | 3.5 Gib| 0.11| 0.80| 3.87| | | |
| 164 | |vcube 112 | 2.4 Gib| 0.15| 1.63| 5.10| | (a) | | 164 | |vcube 112 | 2.4 Gib| 0.15| 1.63| 5.10| | (a) | |
| 165 | |H48 h6 | 1.8 Gib| 0.21| 1.48| 7.70| | | | 165 | |H48 h6 | 1.8 Gib| 0.21| 1.51| 7.67| | | |
| 166 | 166 | ||
| 167 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). | 167 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). |
| 168 | 168 | ||
| 169 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 169 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 170 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 170 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 171 | |vcube 212 |58.2 Gib| 0.95| 7.83| 26.04| 165.03| (a) | | 171 | |vcube 212 |58.2 Gib| 0.95| 7.83| 26.04| 165.03| (a) | |
| 172 | |H48 h11 |56.5 Gib| 1.20| 5.39| 21.09| 130.46| 195.92| | 172 | |H48 h11 |56.5 Gib| 1.17| 4.79| 19.66| 127.55| 140.45| |
| 173 | |vcube 404 |31.8 Gib| 1.21| 4.60| 20.76| 193.43| (a) | | 173 | |vcube 404 |31.8 Gib| 1.21| 4.60| 20.76| 193.43| (a) | |
| 174 | |H48 h10 |28.3 Gib| 0.87| 3.99| 17.52| 119.70| 199.79| | 174 | |H48 h10 |28.3 Gib| 0.85| 3.62| 16.96| 117.32| 158.83| |
| 175 | |vcube 308 |21.2 Gib| 0.67| 4.01| 16.48| 141.49| (a) | | 175 | |vcube 308 |21.2 Gib| 0.67| 4.01| 16.48| 141.49| (a) | |
| 176 | |H48 h9 |14.1 Gib| 0.61| 3.71| 16.23| 115.18| 172.04| | 176 | |H48 h9 |14.1 Gib| 0.61| 3.49| 15.57| 113.56| 151.37| |
| 177 | |vcube 208 | 7.3 Gib| 0.56| 5.78| 17.68| | (a) | | 177 | |vcube 208 | 7.3 Gib| 0.56| 5.78| 17.68| | (a) | |
| 178 | |H48 h8 | 7.1 Gib| 0.65| 4.50| 17.69| | | | 178 | |H48 h8 | 7.1 Gib| 0.59| 4.13| 17.07| | | |
| 179 | |H48 h7 | 3.5 Gib| 0.39| 2.81| 13.73| | | | 179 | |H48 h7 | 3.5 Gib| 0.40| 2.84| 13.68| | | |
| 180 | |vcube 112 | 2.4 Gib| 0.35| 3.95| 12.37| | (a) | | 180 | |vcube 112 | 2.4 Gib| 0.35| 3.95| 12.37| | (a) | |
| 181 | |H48 h6 | 1.8 Gib| 0.37| 2.62| 13.61| | | | 181 | |H48 h6 | 1.8 Gib| 0.38| 2.66| 13.57| | | |
| 182 | 182 | ||
| 183 | (a) vcube cannot parallelize on a single scramble, the results for the | 183 | (a) vcube cannot parallelize on a single scramble, the results for the |
| 184 | superflip are going to be the same as in the single thread case. | 184 | superflip are going to be the same as in the single thread case. |
| @@ -197,23 +197,24 @@ Time per cube (in seconds, lower is better). | |||
| 197 | 197 | ||
| 198 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 198 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 199 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 199 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 200 | |H48 h11 |56.5 Gib| 0.05| 0.46| 3.98| 33.27| 31.83| | 200 | |H48 h11 |56.5 Gib| 0.05| 0.42| 3.84| 32.35| 22.63| |
| 201 | |H48 h10 |28.3 Gib| 0.08| 0.78| 7.00| 59.77| 62.45| | 201 | |H48 h10 |28.3 Gib| 0.07| 0.72| 6.71| 58.57| 48.90| |
| 202 | |H48 h9 |14.1 Gib| 0.13| 1.39| 13.35| | | | 202 | |H48 h9 |14.1 Gib| 0.12| 1.28| 12.76| | | |
| 203 | |H48 h8 | 7.1 Gib| 0.27| 3.00| 29.13| | | | 203 | |H48 h8 | 7.1 Gib| 0.24| 2.75| 27.44| | | |
| 204 | |H48 h7 | 3.5 Gib| 0.36| 4.19| 46.77| | | | 204 | |H48 h7 | 3.5 Gib| 0.36| 4.20| 46.64| | | |
| 205 | |H48 h6 | 1.8 Gib| 0.69| 8.32| 91.89| | | | 205 | |H48 h6 | 1.8 Gib| 0.69| 8.15| 91.47| | | |
| 206 | 206 | ||
| 207 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). | 207 | Time per cube adjusted for table size (in seconds \* GiB, lower is better). |
| 208 | 208 | ||
| 209 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| | 209 | | Solver | Size |17 moves|18 moves|19 moves|20 moves|Superflip| |
| 210 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| | 210 | |:---------|:-------|-------:|-------:|-------:|-------:|--------:| |
| 211 | |H48 h11 |56.5 Gib| 2.84| 26.16| 224.81| 1879.97| 1798.27| | 211 | |H48 h11 |56.5 Gib| 2.68| 23.87| 217.09| 1828.13| 1278.88| |
| 212 | |H48 h10 |28.3 Gib| 2.19| 22.11| 197.79| 1688.62| 1764.41| | 212 | |H48 h10 |28.3 Gib| 2.03| 20.22| 189.49| 1654.79| 1381.67| |
| 213 | |H48 h9 |14.1 Gib| 1.80| 19.59| 188.61| | | | 213 | |H48 h9 |14.1 Gib| 1.71| 18.05| 180.28| | | |
| 214 | |H48 h8 | 7.1 Gib| 1.89| 21.16| 205.79| | | | 214 | |H48 h8 | 7.1 Gib| 1.69| 19.45| 193.88| | | |
| 215 | |H48 h7 | 3.5 Gib| 1.28| 14.79| 165.25| | | | 215 | |H48 h7 | 3.5 Gib| 1.28| 14.85| 164.81| | | |
| 216 | |H48 h6 | 1.8 Gib| 1.23| 14.70| 162.42| | | | 216 | |H48 h6 | 1.8 Gib| 1.22| 14.40| 161.68| | | |
| 217 | |||
| 217 | </details> | 218 | </details> |
| 218 | 219 | ||
| 219 | ## Comments on the results | 220 | ## Comments on the results |
diff --git a/benchmarks/img/17moves16threads.png b/benchmarks/img/17moves16threads.png index 59ca195..156f3a4 100644 --- a/benchmarks/img/17moves16threads.png +++ b/benchmarks/img/17moves16threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/17moves1thread.png b/benchmarks/img/17moves1thread.png index fe91ca8..9df38c4 100644 --- a/benchmarks/img/17moves1thread.png +++ b/benchmarks/img/17moves1thread.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/17moves4threads.png b/benchmarks/img/17moves4threads.png index d6bcd16..ea666f8 100644 --- a/benchmarks/img/17moves4threads.png +++ b/benchmarks/img/17moves4threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/18moves16threads.png b/benchmarks/img/18moves16threads.png index aa1bc3c..38545bc 100644 --- a/benchmarks/img/18moves16threads.png +++ b/benchmarks/img/18moves16threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/18moves1thread.png b/benchmarks/img/18moves1thread.png index 5f9d7fd..462c4dc 100644 --- a/benchmarks/img/18moves1thread.png +++ b/benchmarks/img/18moves1thread.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/18moves4threads.png b/benchmarks/img/18moves4threads.png index ce28518..30a8d8a 100644 --- a/benchmarks/img/18moves4threads.png +++ b/benchmarks/img/18moves4threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/19moves16threads.png b/benchmarks/img/19moves16threads.png index 51a6368..f13ccd5 100644 --- a/benchmarks/img/19moves16threads.png +++ b/benchmarks/img/19moves16threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/19moves1thread.png b/benchmarks/img/19moves1thread.png index a843fef..3bf6567 100644 --- a/benchmarks/img/19moves1thread.png +++ b/benchmarks/img/19moves1thread.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/19moves4threads.png b/benchmarks/img/19moves4threads.png index e1c79e4..d60ce85 100644 --- a/benchmarks/img/19moves4threads.png +++ b/benchmarks/img/19moves4threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/20moves16threads.png b/benchmarks/img/20moves16threads.png index 7c83689..46e80fc 100644 --- a/benchmarks/img/20moves16threads.png +++ b/benchmarks/img/20moves16threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/20moves1thread.png b/benchmarks/img/20moves1thread.png index 4b8b613..97fc0d8 100644 --- a/benchmarks/img/20moves1thread.png +++ b/benchmarks/img/20moves1thread.png | |||
| Binary files differ | |||
diff --git a/benchmarks/img/20moves4threads.png b/benchmarks/img/20moves4threads.png index f61e1ab..47c2268 100644 --- a/benchmarks/img/20moves4threads.png +++ b/benchmarks/img/20moves4threads.png | |||
| Binary files differ | |||
diff --git a/benchmarks/results_h48.py b/benchmarks/results_h48.py index db8a3a5..a2db06c 100644 --- a/benchmarks/results_h48.py +++ b/benchmarks/results_h48.py | |||
| @@ -1,36 +1,36 @@ | |||
| 1 | h48_single_thread = { | 1 | h48_single_thread = { |
| 2 | 6: {17: 52.6781, 18: 398.7213, 19: 2049.9640}, | 2 | 6: {17: 52.7302, 18: 405.7879, 19: 2032.4602}, |
| 3 | 7: {17: 25.6133, 18: 205.2683, 19: 1031.1970}, | 3 | 7: {17: 26.4977, 18: 212.7314, 19: 1074.2251}, |
| 4 | 8: {17: 21.8331, 18: 165.3185, 19: 664.2050}, | 4 | 8: {17: 19.8239, 18: 151.7597, 19: 639.6197}, |
| 5 | 9: {17: 9.4036, 18: 66.6141, 19: 305.3164}, | 5 | 9: {17: 9.0082, 18: 62.0400, 19: 293.2197}, |
| 6 | 10: {17: 6.8148, 18: 36.6565, 19: 168.7843, 20: 1166.2200, "superflip": 60.5523}, | 6 | 10: {17: 6.2190, 18: 31.1395, 19: 158.3581, 20: 1118.7513, "superflip": 48.7016}, |
| 7 | 11: {17: 3.8640, 18: 22.8206, 19: 101.9301, 20: 670.2421, "superflip": 26.9025}, | 7 | 11: {17: 3.5879, 18: 19.5970, 19: 93.5762, 20: 651.2212, "superflip": 20.2721}, |
| 8 | } | 8 | } |
| 9 | 9 | ||
| 10 | h48_4_threads = { | 10 | h48_4_threads = { |
| 11 | 6: {17: 15.6631, 18: 116.6983, 19: 616.6293}, | 11 | 6: {17: 15.2794, 18: 116.1387, 19: 577.3595}, |
| 12 | 7: {17: 7.5627, 18: 57.9755, 19: 293.4441}, | 12 | 7: {17: 7.7522, 18: 59.8914, 19: 293.4824}, |
| 13 | 8: {17: 6.3879, 18: 46.6986, 19: 195.8814}, | 13 | 8: {17: 5.8807, 18: 42.7619, 19: 180.4499}, |
| 14 | 9: {17: 2.9011, 18: 19.1689, 19: 85.5939, 20: 617.9417, "superflip": 29.3115}, | 14 | 9: {17: 2.7609, 18: 18.4867, 19: 84.1350, 20: 610.8914, "superflip": 25.3932}, |
| 15 | 10: {17: 1.9637, 18: 9.7415, 19: 47.3158, 20: 326.8692, "superflip": 16.6325}, | 15 | 10: {17: 1.9215, 18: 9.1287, 19: 43.7573, 20: 338.4877, "superflip": 14.2593}, |
| 16 | 11: {17: 1.2589, 18: 6.5298, 19: 28.2996, 20: 190.1169, "superflip": 8.4383}, | 16 | 11: {17: 1.1997, 18: 5.8332, 19: 26.6060, 20: 176.8453, "superflip": 6.1932}, |
| 17 | } | 17 | } |
| 18 | 18 | ||
| 19 | h48_16_threads = { | 19 | h48_16_threads = { |
| 20 | 6: {17: 5.2001, 18: 37.0525, 19: 192.4323}, | 20 | 6: {17: 5.3639, 18: 37.6695, 19: 191.8620}, |
| 21 | 7: {17: 2.7835, 18: 19.8514, 19: 97.1157}, | 21 | 7: {17: 2.8213, 18: 20.1045, 19: 96.7922}, |
| 22 | 8: {17: 2.3060, 18: 15.9383, 19: 62.6004}, | 22 | 8: {17: 2.0779, 18: 14.6013, 19: 60.4149}, |
| 23 | 9: {17: 1.0799, 18: 6.5733, 19: 28.7205, 20: 203.8189, "superflip": 12.1779}, | 23 | 9: {17: 1.0796, 18: 6.1831, 19: 27.5530, 20: 200.9519, "superflip": 10.7149}, |
| 24 | 10: {17: 0.7715, 18: 3.5307, 19: 15.4995, 20: 105.9181, "superflip": 7.0716}, | 24 | 10: {17: 0.7511, 18: 3.2061, 19: 15.0046, 20: 103.8125, "superflip": 5.6217}, |
| 25 | 11: {17: 0.5313, 18: 2.3848, 19: 9.3324, 20: 57.7204, "superflip": 3.4673}, | 25 | 11: {17: 0.5173, 18: 2.1196, 19: 8.6965, 20: 56.4344, "superflip": 2.4857}, |
| 26 | } | 26 | } |
| 27 | 27 | ||
| 28 | h48_all_solutions = { | 28 | h48_all_solutions = { |
| 29 | 6: {17: 17.3451, 18: 207.8877, 19: 2297.1491}, | 29 | 6: {17: 17.1940, 18: 203.6879, 19: 2286.7364}, |
| 30 | 7: {17: 9.0715, 18: 104.6421, 19: 1169.2355}, | 30 | 7: {17: 9.0219, 18: 105.0559, 19: 1166.1059}, |
| 31 | 8: {17: 6.6934, 18: 74.8913, 19: 728.2341}, | 31 | 8: {17: 5.9919, 18: 68.8215, 19: 686.0935}, |
| 32 | 9: {17: 3.1790, 18: 34.6734, 19: 333.7746}, | 32 | 9: {17: 3.0192, 18: 31.9398, 19: 319.0297}, |
| 33 | 10: {17: 1.9342, 18: 19.5612, 19: 175.0206, 20: 1494.2053, "superflip": 62.4507}, | 33 | 10: {17: 1.7972, 18: 17.8931, 19: 167.6695, 20: 1464.2636, "superflip": 48.9035}, |
| 34 | 11: {17: 1.2574, 18: 11.5760, 19: 99.4671, 20: 831.7873, "superflip": 31.8256}, | 34 | 11: {17: 1.1838, 18: 10.5628, 19: 96.0518, 20: 808.8516, "superflip": 22.6335}, |
| 35 | } | 35 | } |
| 36 | 36 | ||
diff --git a/src/solvers/h48/gendata_h48.h b/src/solvers/h48/gendata_h48.h index 15b7589..ef8a854 100644 --- a/src/solvers/h48/gendata_h48.h +++ b/src/solvers/h48/gendata_h48.h | |||
| @@ -18,6 +18,8 @@ STATIC_INLINE uint8_t get_h48_pval(const unsigned char *, uint64_t); | |||
| 18 | STATIC_INLINE void set_h48_pval(unsigned char *, uint64_t, uint8_t); | 18 | STATIC_INLINE void set_h48_pval(unsigned char *, uint64_t, uint8_t); |
| 19 | STATIC_INLINE uint8_t get_h48_pvalmin(const unsigned char *, uint64_t); | 19 | STATIC_INLINE uint8_t get_h48_pvalmin(const unsigned char *, uint64_t); |
| 20 | STATIC_INLINE void set_h48_pvalmin(unsigned char *, uint64_t, uint8_t); | 20 | STATIC_INLINE void set_h48_pvalmin(unsigned char *, uint64_t, uint8_t); |
| 21 | STATIC_INLINE uint8_t get_h48_pval_and_min( | ||
| 22 | const unsigned char *, uint64_t, uint8_t [static 1]); | ||
| 21 | 23 | ||
| 22 | STATIC long long | 24 | STATIC long long |
| 23 | gendata_h48_dispatch( | 25 | gendata_h48_dispatch( |
| @@ -526,3 +528,22 @@ set_h48_pvalmin(unsigned char *table, uint64_t i, uint8_t val) | |||
| 526 | t = table[H48_INDEX(i)]; | 528 | t = table[H48_INDEX(i)]; |
| 527 | table[H48_INDEX(i)] = (t & UINT8_C(0xF)) | (v << UINT8_C(4)); | 529 | table[H48_INDEX(i)] = (t & UINT8_C(0xF)) | (v << UINT8_C(4)); |
| 528 | } | 530 | } |
| 531 | |||
| 532 | STATIC_INLINE uint8_t | ||
| 533 | get_h48_pval_and_min( | ||
| 534 | const unsigned char *table, | ||
| 535 | uint64_t coord_noext, | ||
| 536 | uint8_t pval_min[static 1] | ||
| 537 | ) | ||
| 538 | { | ||
| 539 | uint64_t iext, imin; | ||
| 540 | uint8_t t, tmin; | ||
| 541 | |||
| 542 | iext = H48_LINE_EXT(coord_noext); | ||
| 543 | imin = H48_LINE_MIN(coord_noext); | ||
| 544 | t = table[H48_INDEX(iext)]; | ||
| 545 | tmin = table[H48_INDEX(imin)]; | ||
| 546 | |||
| 547 | *pval_min = tmin >> UINT8_C(4); | ||
| 548 | return (t & H48_MASK(iext)) >> H48_SHIFT(iext); | ||
| 549 | } | ||
diff --git a/src/solvers/h48/solve.h b/src/solvers/h48/solve.h index 5fd3dd9..2920fa7 100644 --- a/src/solvers/h48/solve.h +++ b/src/solvers/h48/solve.h | |||
| @@ -108,9 +108,9 @@ STATIC_INLINE bool | |||
| 108 | solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) | 108 | solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) |
| 109 | { | 109 | { |
| 110 | uint32_t data, data_inv; | 110 | uint32_t data, data_inv; |
| 111 | int64_t coord, coordext, coordmin; | 111 | int64_t coord; |
| 112 | int8_t target, nh, n; | 112 | int8_t target, nh, n; |
| 113 | uint8_t pval_min, pval_eoesep; | 113 | uint8_t pval, pval_min, pval_eoesep; |
| 114 | 114 | ||
| 115 | arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES; | 115 | arg->movemask_normal = arg->movemask_inverse = MM18_ALLMOVES; |
| 116 | arg->nodes_visited++; | 116 | arg->nodes_visited++; |
| @@ -132,25 +132,23 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) | |||
| 132 | /* Inverse probing */ | 132 | /* Inverse probing */ |
| 133 | 133 | ||
| 134 | if (!arg->use_lb_inverse) { | 134 | if (!arg->use_lb_inverse) { |
| 135 | arg->table_lookups++; | ||
| 136 | arg->use_lb_inverse = true; | ||
| 135 | coord = coord_h48_edges( | 137 | coord = coord_h48_edges( |
| 136 | arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h); | 138 | arg->inverse, COCLASS(data_inv), TTREP(data_inv), arg->h); |
| 137 | coordext = H48_LINE_EXT(coord); | 139 | pval = get_h48_pval_and_min(arg->h48data, coord, &pval_min); |
| 138 | arg->lb_inverse = get_h48_pval(arg->h48data, coordext); | ||
| 139 | arg->table_lookups++; | ||
| 140 | 140 | ||
| 141 | if (arg->lb_inverse == 0) { | 141 | if (pval == 0) { |
| 142 | arg->table_fallbacks++; | 142 | arg->table_fallbacks++; |
| 143 | 143 | ||
| 144 | coordmin = H48_LINE_MIN(coord); | ||
| 145 | pval_min = get_h48_pvalmin(arg->h48data, coordmin); | ||
| 146 | pval_eoesep = get_eoesep_pval_cube( | 144 | pval_eoesep = get_eoesep_pval_cube( |
| 147 | arg->h48data_fallback_eoesep, arg->inverse); | 145 | arg->h48data_fallback_eoesep, arg->inverse); |
| 148 | arg->lb_inverse = MAX(pval_min, pval_eoesep); | 146 | pval = MAX(pval_min, pval_eoesep); |
| 149 | } else { | 147 | } else { |
| 150 | arg->lb_inverse += arg->base; | 148 | pval += arg->base; |
| 151 | } | 149 | } |
| 152 | 150 | ||
| 153 | arg->use_lb_inverse = true; | 151 | arg->lb_inverse = pval; |
| 154 | } | 152 | } |
| 155 | 153 | ||
| 156 | if (arg->lb_inverse > target) | 154 | if (arg->lb_inverse > target) |
| @@ -161,25 +159,23 @@ solve_h48_stop(dfsarg_solve_h48_t arg[static 1]) | |||
| 161 | /* Normal probing */ | 159 | /* Normal probing */ |
| 162 | 160 | ||
| 163 | if (!arg->use_lb_normal) { | 161 | if (!arg->use_lb_normal) { |
| 162 | arg->table_lookups++; | ||
| 163 | arg->use_lb_normal = true; | ||
| 164 | coord = coord_h48_edges( | 164 | coord = coord_h48_edges( |
| 165 | arg->cube, COCLASS(data), TTREP(data), arg->h); | 165 | arg->cube, COCLASS(data), TTREP(data), arg->h); |
| 166 | coordext = H48_LINE_EXT(coord); | 166 | pval = get_h48_pval_and_min(arg->h48data, coord, &pval_min); |
| 167 | arg->lb_normal = get_h48_pval(arg->h48data, coordext); | ||
| 168 | arg->table_lookups++; | ||
| 169 | 167 | ||
| 170 | if (arg->lb_normal == 0) { | 168 | if (pval == 0) { |
| 171 | arg->table_fallbacks++; | 169 | arg->table_fallbacks++; |
| 172 | 170 | ||
| 173 | coordmin = H48_LINE_MIN(coord); | ||
| 174 | pval_min = get_h48_pval(arg->h48data, coordmin); | ||
| 175 | pval_eoesep = get_eoesep_pval_cube( | 171 | pval_eoesep = get_eoesep_pval_cube( |
| 176 | arg->h48data_fallback_eoesep, arg->cube); | 172 | arg->h48data_fallback_eoesep, arg->cube); |
| 177 | arg->lb_normal = MAX(pval_min, pval_eoesep); | 173 | pval = MAX(pval_min, pval_eoesep); |
| 178 | } else { | 174 | } else { |
| 179 | arg->lb_normal += arg->base; | 175 | pval += arg->base; |
| 180 | } | 176 | } |
| 181 | 177 | ||
| 182 | arg->use_lb_normal = true; | 178 | arg->lb_normal = pval; |
| 183 | } | 179 | } |
| 184 | 180 | ||
| 185 | if (arg->lb_normal > target) | 181 | if (arg->lb_normal > target) |
