I had read previously that Mogo used MPI, but I didn't know
if could work on clusters without sharing the whole tree. I have been
formulating such an algorithm for the past week or so, so I would like
to make sure that it hasn't already been done. Has anything been
written about Mogo's parallel algorithms? Or could you give a brief
run-down? How does it scale on such large numbers of processors?
MoGo's parallelization has been published, but with
moderate results because at that time we were only using ethernet. The
same algorithm with good networks provide good results in 9x9 and very
good results in 19x19. The trick is just that sharing only nodes of the
tree with at least 5% of the total number of simulations, say 20 times
per second, is enough for a nice speed-up. This is not possible with
ethernet, but it is possible with myrinet, infiniband, or things like
taht. With
32 nodes, you get
95% winning rate against the one-node baseline, and this can be
implemented using MPI within just a few lines (recursive sharing of the
nodes in the tree). The reference (conference icinco2008)
is on my web page (http://www.lri.fr/~teytaud/cv/cv.html), but the results
in the paper are disappointing
as the results on this paper were with ethernet only. We'll publish
the new speed-up curves soon (preliminary results below). In 9x9, it's far
less impressive, unfortunately; but perhaps improvements are possible.
Note that these results are with very good networks, but better hardware
exists... if you have plenty of money :-)
Also I think that just combining the improvements in various current best
implementations could provide something much stronger. For example, mogo
is still below the state of the art in terms of patterns in the tree (but,
this is increasing :-) ). Some other implementations have no MPI
parallelization, or no RAVE values - combining all that in one code could
be quite nice. It's just a huge work :-)
Olivier
MPI success rate ===
19x19 with 32 machines
against 1 machines:.95102040816326530612+-.01378857726307400759\\
against 2 machines:.82383419689119170984+-.02742218504725679587\\
against 4 machines:.73493975903614457831+-.03425658934275012162\\
against 8 machines:.63076923076923076923+-.04232651544690520753\\
against 16 machines:.63157894736842105263+-.05533236663556282245\\
against 32 machines:.4800+-.09991996797437437129\\
9x9
against 1 machines:.72542372881355932203+- .02598462012440167557
against 2 machines:.63082437275985663082+- .02889140360869044365
against 4 machines:.61231884057971014492+- .02932726868615559501
against 8 machines:.53526220614828209764+- .02120922113498994710
against 16 machines:.50541516245487364620+- .02124171853985291158
___
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/