Grid'5000 experiment

Jump to: navigation, search

Go states computation (Programming)

Conducted by

Thomas Herault, Michal Koucky


The goals of the project are two-fold: 1) application one - to compute the exact number of legal positions on a Go game board which is of size 19x19 (the standard size). This is a considerable computational challenge which was so far solved for boards only up-to the size 17x17 and it would be of certain interest to Go community. As opposed to say "computing the number Pi for yet another zillion digits" which can go on indefinitely this is a one time computation on the border of what is computable with our current computer technology. Mathematically, the problem is essentially to compute a product of a vector by 361 matrices. The dimension of the vector and matrices is 2^64. Luckily, everything is sparse so there are only about 350G non-zero entries in any intermediate or final vector and each of the matrices is given implicitly. The entries are of size about 100B so overall one needs to process approx. 12 Peta bytes of data. 2) programming one - the scale of the computation is such that reliability of hardware and software becomes an issue. As a distributed application seems to be the only possibility how to carry out such a large computation issues coming from unreliability and failure of particular nodes come into play (beside the usual load balancing issues). As the data and the overall state of the computation has to be distributed over many nodes the question of a node failure recovery needs to be addressed. Hence designing and testing a high performance system that could reliably run over somewhat reliable nodes is one of the goals of this experiment. The target parameters of the system is to be able to process continuously and semi-synchronously on order of 1000 nodes order of 10MB/s of data per node in the "map-and-reduce" fashion.




  • Nodes involved: >1000
  • Sites involved: >3
  • Minimum walltime: 24h
  • Batch mode: yes
  • CPU bound: yes
  • Memory bound: no
  • Storage bound: yes
  • Network bound: yes
  • Interlink bound: yes

Tools used



Not yet

More information here

Shared by: Thomas Herault, Michal Koucky
Last update: 2008-08-15 17:25:57
Experiment #493