While re-reading the parallelization papers, I tried to formulate why I thought that they couldn't be right. The issue with Mango reporting a super-linear speed-up was an obvious red flag, but that doesn't mean that their conclusions were wrong. It just means that Mango's exploration policy needs tweaking.
I have three objections. First, root parallelization does not fully exploit the RAM attached to each compute node. If I have N compute nodes then I would like to search a tree that is N times as large. But in root parallelization I cannot actually do that because lower layers of the tree are duplicated across compute processes. Second, root parallelization does not share information about how to explore away from the root. Tactics necessary to refute variations must be discovered across all N processes. This seems wasteful of CPU resources. Third, it seems wasteful of network bandwidth. In particular, the root node is shared because of a side-effect: it makes N processes independently agree on how to distribute attention across root moves. If you count up the bytes required to represent a node, and how many bytes are required to specify a distribution of attention, you will find that the node is much, much larger. These reservations might not be significant. For example, most of a tree is stored near the leaves, so the cost of duplicating nodes near the root might be small. And the network bandwidth might not be a bottleneck. But I do believe that the second objection is a killer. Theory says that it is just as hard to choose replies to our moves as it is to choose our moves. So a strategy that splits only at the root cannot be optimal. One obvious alternative to root parallelization is "deep parallelization" in which we share the root node and children of already shared nodes that have at least N trials. Deep parallelization should asymptotically solve the problem of sharing deep tactics. But this approach worsens the drawbacks from my first and third objections. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
