[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [gnugo-devel] parallel GNU Go (was: TODO revisions)
From: |
David G Doshay |
Subject: |
Re: [gnugo-devel] parallel GNU Go (was: TODO revisions) |
Date: |
Tue, 14 Sep 2004 08:16:12 -0700 |
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