BSc
Parallel Sudoku solver
Two parallel Sudoku solvers in C, benchmarked honestly: the Pthread version gains 5% at two threads and then gets slower, and the OpenMP version never beats its own serial run.
Three C solvers for 9×9 Sudoku, written with Gaetano Conti for a concurrent-programming course: a Pthread depth-first search with task delegation, a variant that can delegate several branches at once to push the search toward breadth-first, and an OpenMP level-by-level breadth-first solver.
- Context
- Concurrent programming course, January 2021
- With
- Gaetano Conti
- Benchmark
- 100 puzzles · 1–32 threads · 2-core i7-6500U
- Repository
- VincenzoImp/parallel-sudoku-solver
What it was
The Pthread design has three thread roles. Idle threads block on their own semaphore; a thread that generates several candidate boards checks a shared FIFO of idle threads, becomes a delegator, and hands one board to one sleeper while keeping the rest. The OpenMP solver instead expands a whole level of the search tree at a time, with the append into the next level serialised inside a critical section.
The result is negative, and the report says so. The Pthread solver’s best mean is 0.0073 seconds per puzzle at two threads against 0.0077 serial – about 5% – after which it degrades steadily to 0.0146 seconds at thirty-two threads, roughly twice as slow as not parallelising at all. The OpenMP solver’s fastest configuration is its one-thread run.
Two more things the report admits and most reports would not. The hybrid variant was excluded from the benchmarks entirely because of a race condition that appears under a particular thread schedule after the solution is found, and was never fixed. And the 100-puzzle test set was chosen easy enough for the OpenMP solver to finish, which biases the comparison toward the weaker implementation.
What I took from it
The benchmark hardware was a laptop with two physical cores, so measuring at eight, sixteen and thirty-two threads was measuring contention. That is the lesson that stuck: a scaling curve without the machine next to it is not a result, and an honest negative finding – including a failed optimisation, where shuffling the fill order lost to filling cells linearly – is worth more than a speedup number nobody can reproduce.