Re: [gnugo-devel] Parallelizing GNU Go

[John Paul Rodman]

On Tue, 1 Apr 2003, Dave Denholm wrote:

> It has been mentioned in the past...
>
> First question is whether to address
>
> a) multi cpu machines

I have access to some 64 CPU machines at the university where I would be
running the software.
I will probably be using MPI or OpenMP.
Does anyone know if there is an open-source version of either of these,
so that I could distribute the code?

> b) network of single-cpu machines

I also have access, through the university, to the distributed (Seti at
Home style) software developed by United Devices.  Unfortunately, there
are some problems with using this with GNU Go, that make me lean towards
the multi cpu machine idea.

> c) Intel's new scheme (hyper threading..?) for scaling up single cpu.

I don't know anything about this.

> a) multi-cpu machines are sufficiently rare that the benefit
>  is limited. A factor-of-2 speedup doesn't seem big enough
>  to go after.

There is a version of MPI that runs distributed over a set of Linux
machines.

>  The main process could, say, build a list of moves to consider, and
>  spawn a child process to look at each one.

This is just what I was thinking of doing.
Here are a couple of methods I was considering for the master process to
pick which moves to send to the child processes to evaluate.
1) Breadth search
Evaluate *every* possible move from the current position.
2) Depth search
Have the master process evaluate the position, and pick the 10 best
moves, then pick the 10 best responses to each of those.

Unfortunately, I'm not sure how to evaluate positions that are several
moves deep.  Can the valuations of moves in two different game variations
be legitimately compared?  Could a score estimation be used to compare the
moves?

I doubt I'll be able to do some of the things suggested like having the
Owl code run in parallel, since there is some analysis of the algorithm I
have to do that could be very difficult in such a case. I may still look
into it.

> b) is an opportunity to scale up to a large extent, provided the
>  comms overhead is not too great. ie when asking a remote machine to
>  answer a question, the compute effort needs to justify the
>  round-trip cost.

Is there a way to significantly increase the amount of time GNU Go takes
to decide on a move, such as increasing the level above 10?  Does doing so
have much effect on how well GNU Go plays?


Thanks,
JP Rodman