h1

Parallel Sudoku

August 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)))
About these ads

2 comments

  1. Finally got my Java version working. Not particularly happy with it. Does your evil in about 750ms.


  2. It would be nice to see your Java version – it seems to be approximately as fast as my first version.

    Any ideas why this second version is considerably slower? Or how I could profile / debug such a short-running app?



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: