Re: [gnugo-devel] parallel GNU Go (was: TODO revisions)

[David G Doshay]

On Sep 13, 2004, at 5:32 AM, Alain Baeckeroot wrote:

> Le mardi 7 Septembre 2004 04:42, David G Doshay a écrit :
> > On Sep 6, 2004, at 10:38 AM, Arend Bayer wrote:
> >
> > > On Wed, 25 Aug 2004, David G Doshay wrote:
> > >
> > > > As per my previous offer, if anyone wants to think about how to
> > > > parallelize the engine we may be able to offer part of our cluster
> > > > for testing and development. We are open to suggestions and
> > > > proposals.
>
> Hello gnugo world
>
> Thanks for the nice program.
> I m a rather weak go player (6k) and i just discover gnugo code, but i
> am interested in parrallel/cluster code, i practiced some years ago
> for fluid dynamics (2d + time like gnugo :). I ll soon have a dual-CPU 
> available
> for testing, and i plan to put on a tiny 3 machines mosix-cluster for 
> testing :)

We got a long ways with 4 mac G4 towers before we got the big G5 
cluster,
so you should be able to get a reasonable start with 3 machines in a 
cluster.

> My approach is a physicist point of view:
> - a 2D phenomenon (on 19x19 grid)  so maybe we can parralelise on space

How this is done is critical to efficient use of the cluster. IMO, 
doing this the
obvious way will turn out to be a waste of CPUs. And then you will 
waste more
time inspecting the input from lots of those CPUs and deciding to toss 
their
results.

> - time dependant (and time constraint).
> - very small data to transmit, (less than 500 moves)
>
> I think that some changes (not necessarily big) are needed:
> - on time use
> - on threads (spacial threads or functionals threads?)

GNU Go is not a threaded program. To rewrite it that way will be
a major restructuring job. But I would not try to slow you down if
you are motivated.  ;^)

> For the moment i just dicover the code, but i noticed few points 
> concerning
> parrallelization:
> - My first idea is that the go programmers should take care of go, and 
> let the
> Operating System do the job (multi thread, SMP or NUMA or cluster or 
> grid-computing ...)

Everybody's dream, but not the way things work today.

> But i know that a code doesn't behave well on multiCPU machines if it 
> wasn't written
> for that !

Indeed.

> I noticed some points which AFAIK show problems in the code:
> - The code seems to be one big function, and not at all multi thread.

Not really one big function, but the programming model is based upon
normal function calls, not launching threads.

> - Thinking during opponent time (it is in TODO :)
>  This is probably linked to the persistent cache of analysis,( i read 
> something on that).
>
> - gnugo wastes a lot of time: on 9x9 it take less than 30seconds of 
> thinking.
>  At least the time manger should use all (90%) of the available time, 
> and do deeper
>  reading if necessary.
>
> - Naive intuition says that the code should size well on a 361 CPU, 
> but it
> is probably not the case.

I think that any code that starts with the concept that there should be 
361 CPUs,
one for each point on the board, is going about it the wrong way. That 
is why
we developed some networking infrastructure on top of MPI. The 
infrastructure's
purpose is to raise to the network and cluster level the things a 
thread manager
in a RTOS does on a single cpu.

>  I have not understood how things are managed in gnugo
> but i think at least there could be one thread per color, one thread 
> per connected-group,
> or one thread per potential move.

I think that if you were to start over with a threaded model that it 
could be
interesting to think in terms of a thread for each of several different 
structures.
But that is no small task. It is not a simple patch to GNU Go, it is a 
major
rewrite.

> - Analysis is  not symetrical : Gnugo is stronger in attack than in 
> defense
> (gnugo 3.4 on 7x7 it kills itself in 10 seconds :)
>  I think that means that when Black tries to defend, it doesn't 
> considers the White attacks, at least
> with the same depth of reading. I thought that gnugo was playing both 
> B and W for its own analysis, it
> doesnt seem to be the case.

SlugGo does this explicitly, asking GNU Go to generate moves for both 
Black and
White from the same board position. Each genmove takes place on a 
separate CPU,
so there is no wall-time hit for doing this.

> Well , maybe my mail is a bit confused for the moment, but if i can 
> help ...

At the very least thoughts and discussion are interesting.

Cheers,
David