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
Solvitur Ambulando 