You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
a23b65c0b0
|
10 months ago | |
|---|---|---|
| .. | ||
| CMakeLists.txt | 10 months ago | |
| LICENSE | 10 months ago | |
| Makefile | 10 months ago | |
| README.md | 10 months ago | |
| main-10-thread.c | 10 months ago | |
| main-20-thread.c | 10 months ago | |
| main.c | 10 months ago | |
README.md
m-queens
Multi-queens, a very fast solver for the general eight queens problem with OpenMP support.
Based on code from https://rosettacode.org/wiki/N-queens_problem#C but much more optimized.
If you find a way to make the code even faster, please let me know. Also feel free to open a Pull Request to add your own benchmarks.
Benchmarks
Single-Thread
Compiled with gcc-7 -o m-queens.bin main.c -O2 -march=native -mtune=native -std=c99 and
run with ./m-queens 18.
| CPU | N | Time to solve |
|---|---|---|
| Intel(R) Core(TM) i7-4600M CPU@ 3.5 GHz (single core) | 18 | 129.56s |
Multi-Thread
Compiled with gcc-7 -o m-queens.bin main.c -O2 -march=native -mtune=native -std=c99 -fopenmp and
run with ./m-queens 18.
| CPU | Cores (real/virtual) | N | Time to solve | Speedup from Single-Thread |
|---|---|---|---|---|
| Intel(R) Core(TM) i7-4600M CPU@ 3.4 GHz (all cores) | 2/4 | 18 | 52.56s | 2.46 |
Future Improvements
Use the optimized placement mentioned in https://github.com/preusser/q27 to reduce symmetries.
probably very hard to do with the current implementation
Use OpenCL to make use of GPUs
Work in progress in the sieves, split2_debug and ringbuffer branches.