Darren Cook: <4aecdf3e.7010...@dcook.org>: >>>>> Parallelization *cannot* provide super-linear speed-up. >>>... >>> The result follows from a simulation argument. Suppose that you had a >>> parallel process that performed better than N times a serial program. >>> Construct a new serial program that simulates the parallel process. There is >>> a contradiction. >>> ... > >The paper suggests the cause of the super-linear speed-up is that a >thread gets caught in local optima (which it doesn't escape from within >the designated thinking time). It also says if each thread was given >more time then the speed-up factor may become less. > >It sounds like it is definitely worth exploring the parameters of root >parallelization some more. > >> At the risk of belaboring the obvious, extra memory associated with >> each processor or node (cache, main memory, hard disk, whatever) is >> one reason adding nodes can in practice give a speedup greater than >> the increase in processing power. > >That is an interesting idea. The paper says: "experiments were performed >on the supercomputer Hyugens, which has 120 nodes, each with 16 cores >POWER5 running at 1.9Ghz and having 64Gb of memory per node." > >Experiments were done from 1 to 16 threads, but I cannot see mention in >the paper whether 16 threads means one nodes using 16 cores, or 16 nodes >using one core of each. Perhaps Guillaume can tell us.
In that paper, clearly Guillaume used only shared-memory parallel, not network. So the former must be collect. >The experiment to decide if a hardware or algorithm cause of the >super-linear speed-up is to try the single thread version by having it >run 4 searches one after another, and merging results. I.e. if that >gives a performance boost over one long search then the cause must be >algorithmic? (?) The PRNG (pseudo random number generator) can cause the super-linear speed-up, for example. For deteministic computations Brian is correct but since MCTS is a stocastic process, there could be other possibilities... Hideki -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
