Queen of the Races

The Queens N puzzle has lots of opportunity for parallelism so I thought I’d see what my dual core Windows system could do. Using the code from the previous post, pretty much what I’d expect: Two cores, two threads is as good as it gets, adding more threads doesn’t do any good if there aren’t any cores to support them.

724 solution(s) : 1 threads : 15 seconds
724 solution(s) : 2 threads : 9 seconds
724 solution(s) : 3 threads : 10 seconds
724 solution(s) : 4 threads : 10 seconds
724 solution(s) : 5 threads : 9 seconds

_____________________________________________

The code is simple:

  • Two job queues: pending and solutions
  • Start a thread:
    – The thread reads from the pending queue and solves a queens n puzzle, starting at the second row (thus multiple threads are solving different puzzles).
    – Write the solution the solutions queue.
    – Repeat
  • Write N puzzles to the pending queue.
  • Wait for N solutions to show up in the solutions queue (each “solution” is a list of zero or more solutions for the starting board position).
  • Print some stats
  • Start another thread and repeat

While it is possible, with this code, for one thread to do all the work (by hogging the input queue), that is unlikely (the thread would have to solve a puzzle really fast to read the next puzzle before another thread got it).

N := 10; pin := Thread.Pipe(); pout := Thread.Pipe();
do(5){  // test with one to five threads
   fcn(pin,pout) { // create a puzzle solving thread
      foreach job in (pin) { pout.write(job()); }
   }.launch(pin,pout);

   time := Time.Clock.time;
   foreach c in ([1..N])
       { pin.write(queensN.fp(N,2,T(T(1,c)))); }
   Atomic.waitFor(fcn(len,n)
          { len() == n }.fp(pout.len,N));
   pout.close();
   queens := pout.walker().cat();

   println(“%s solution(s) : %s threads : %s seconds”
         .fmt(queens.len(),vm.numThreads,
              Time.Clock.time-time));
   pout.open();         // reopen output queue
}
pin.close();    // let the threads exit

This entry was posted in Uncategorized. Bookmark the permalink.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s