[chbot] Choc fish challenege 3 - Completely OT!)

[Charles Manning]

On Wednesday 31 August 2011 12:18:19 hamster wrote:
> On Wed, 31 Aug 2011 10:04:43 +1200, Hanno Sander <hanno at mydancebot.com>
>
> wrote:
> > The only part of the queens problem that lends itself to parallel
> > programming is checking to see if a solution is valid.
>
> It is very non-parallel, but couldn't an 8 cog system have each cog search
> with the queen at different spot on the top row? (ie. one of
> (0,0),(0,1),(0,2)... (0,7)).
>
> For anybody who hasn't twigged, the search space isn't 64!/56! (7e+74)
> that you get if you out 8 queens anywhere on the board and test for
> correctness, or even 8^8 1.6e7 if you place a queen on each row and test.
>
> It's only 8! = 40,320, and that works out as 5,040 test per cog....

Indeed. parellelising the search would be more interesting than just the 
position checking.

The ultimate way to perform search parallelism in a multi-processor 
environment is probably to use something like LINDA. 
http://en.wikipedia.org/wiki/Linda_%28coordination_language%29

This has multiple agents feeding on a tuple space. The agents pick up a 
partial solution, chew on it a bit, then spit out further partial solutions 
into the tuple space.

Each agent (approximately a thread) has an algorithm of the form:
  while(1) {
	grab tuple (ie a list of positions for the partial solution)
  If the partial solution is length 8 then it is a full solution, print out
  otherwise {
	if the solution is length n, generate the 8 possible partial solutions of 
length n+ 1
	check each of these partial solutions. Throw the good ones back into the 
tuple space fir other agents to work on. Discard the bad ones.
 }

The system starts with a single empty tuple.


LINDA was a big deal in experimental CS in some South African universities 
during apartheid-era. At the time there were concerns that South Africa would 
be heavily embargoed and would not be able to buy top-end CPUs. However, 
South Africa had sufficient technology to make 8 and maybe even 16-bit CPUs 
(albeit rather lame ones) and multi-processing was seen as a way to get a bit 
of performance if the embargoes ever happened.

-- Charles