SudokuMP


Project Checkpoint

Work Completed

We are currently behind schedule. We have started implementing a brute force solver, and we have pseudocode for the humanistic solver. However, we are still on track for finishing comfortably on time because our original schedule allowed ample time for this project.

You can download the pseudocode here

Work Remaining

It is still likely that we will finish the goals stated in our proposal, although our stretch goal of creating a GUI for this project might be in jeopardy. We are in the process of extending our implementation for any sized boards, so at the very least we will achieve that stretch goal.

Parallelism Competition

At the parallelism competition, we are planning on showing graphs comparing speedup over various numbers of cores using the brute force solver and/or the humanistic solver. If we have time to create a GUI for the solver, we would like to demo that over sudoku puzzles of varying difficulty.

Issues

Besides other classes and assignments delaying our progress a bit, we have run into a bit of an issue because of the way OpenMP works. It is difficult to have nested parallelization in OpenMp (i.e. a thread creating subthreads), which might be necessary if we want to have two or more dimensions of parallelization. We have considered parallelizing over blocks as well as individual cells, which might be tricky in OpenMP. So, we have considered using CUDA.

There is also the danger that the humanistic solver will be too fast for parallelism to achieve measureable speedup. If that turns out to be the case, we would like to implement a completely brute force solver and compare that speedup to the speedup (or lack thereof) achieved by the humanistic solver.

Updated Schedule

Date Plan
4/22 Finalize brute force solver (Ben).
4/27 Implement sequential humanistic solver (Ariel).
5/1 Parallelize brute force and humanistic solvers (Ben and Ariel).
5/3 Tweak parallelization to achieve best results (Ben and Ariel).
5/7 Complete presentation (Ben and Ariel).