Parallel SudokuAugust 15, 2011
Following on from my previous post where I wrote a Sudoku solver in Clojure, I tried to improve the performance of the algorithm by having each branch of my search tree execute in a separate thread. I first tried using the ref construct and while it solved the easy puzzle, there was a non-trivial bug which went into some infinite loop with the hard one. I finally gave up on it and decided to use the agent construct to notify the main thread when the puzzle was solved. The main thread just hangs around waiting for the agent state to change to the right solution.
While performance between the two solutions is interchangeable on the easy puzzle, there is a noticeable difference in the performance on the hard one – the parallel solution is consistently 3.5-4 times slower! I have tried changing around some of the parameters (increasing thread pool size to 1000, decreasing it to 4 – the number of cores on my laptop, increasing the sleep interval on the main thread to try and reduce the amount of processor time it grabs etc), all to no avail. I can’t believe context switching between threads costs so much more than the benefits of a parallel search.
So, why is this slower (and by this magnitude)? Alternatively, how could I profile this application (it takes approximately 4 seconds to run) to get some hints?
Here is the relevant additional code:
(def executors (java.util.concurrent.Executors/newFixedThreadPool 100)) (defn solve-in-parallel-worker [grid counter solution-agent] (if (>= counter (* size size)) (send-off solution-agent conj grid) (if (grid counter) (solve-in-parallel-worker grid (inc counter) solution-agent) (let [row-number (quot counter size) col-number (rem counter size) sub-grid-number [(quot row-number sqrt) (quot col-number sqrt)] ] (loop [possibles (seq (missing (clojure.set/union (row grid row-number) (col grid col-number) (sub-grid grid (sub-grid-number 0) (sub-grid-number 1))))) dummy nil] (if (nil? (first possibles)) nil (recur (next possibles) (.submit executors (fn (solve-in-parallel-worker (assign grid row-number col-number (first possibles)) (inc counter) solution-agent)))))))))) (defn solve-in-parallel [grid] (let [solution-agent (agent )] (.submit executors (fn (solve-in-parallel-worker grid 0 solution-agent))) (while (= @solution-agent ) (Thread/sleep 1)) (first @solution-agent)))