This is a great post, and some good observations. I agree with your conclusions that CPU power is increasing faster than memory and memory bandwidth. Let me give you my take on this.
In a nutshell, I believe memory will increasingly become the limiting factor no matter what direction we go. The only thing I would add to what you said is that we should recognize that there are no workarounds - heavy playouts won't solve the problem but may be the pathway we have to go down to mimimze the problem. This is because it's the tree that has been the source of our recent breakthroughs. When the tree stops scaling due to memory limitations, so will our programs. When we are forced to focus on heavier playouts because we cannot build bigger trees, then we are back to the problem of trying to solve the game statically. At this point we have regressed to our old non-scalable methods that have not served us very well over the decades. That is not to say that we won't continue to make progress, taking advantage of ever increasing hardware. The memory will continue to get larger, just not at the same rate as processing power. We will be forced to find ways to trade off CPU power for memory, and so on. We will no doubt be pretty clever about this. We may be forced to consider other kinds of tree search that do not require maintaining the entire tree in memory. However, there is no tree search that does not benefit from memory and memory bandwidth, so we will always have the memory bottleneck to deal with, however this ends up going. - Don 2009/5/12 Brian Sheppard <sheppar...@aol.com> > Summary: The trend in computer systems has been for CPU power to grow > much > faster than memory size. The implication of this trend for MCTS computer go > implementations is that "heavy" playouts will have a significant cost > advantage > in the future. > > I bought a Pentium D 3GHz system a few years back. It was equipped with 2 > GB > of memory. This was a good CPU at that time (second fastest available) with > a > maximum memory configuration. A comparable system nowadays would be an > i7-940, with 6GB of memory. > > Now, comparison of those systems shows the trend. The Pentium D has a > Passmark rating (an industry standard measure of comuter power) of 770, > and > the i7-940 has a rating of 6095. The CPU is 7.9 times as fast, but the > memory > configuration is only 3 times as large. > > This is only one memory configuration. You can buy larger memory > configurations > at higher cost, but that's the point: the CPU is accelerating faster than > memory > is growing. > > The trend seems likely to intensify. Intel has already announced 6-core and > 8-core > systems for release later this year. It is not known what memory > configuration will > ship in such a system, but we cannot expect it to be double what ships in a > quad-core. > > In 2010 we have the Larrabee architecture, which puts a much larger number > of > cores on the chip. Intel isn't saying how many, but you can count on 16 > cores > at a minimum, with rapid doublings thereafter. Memory density seems > unlikely > to keep pace. > > I will be watching this trend very closely, as one who has to pay for his > own > computer equipment. > > The implication for MCTS and computer go: it pays to trade off CPU power to > keep > memory usage low. > > The most direct way to keep memory low is to represent the tree using as > few bytes > as possible. The literature refers to techniques for "promoting" nodes > after some > number of trials, and I recall that perhaps Fuego gives an implementation. > But I > doubt that we know the limits. Here is a thought experiment: if you run the > bzip > compressor on your tree, would you get 10% compression? My guess is more > like 95% compression. > > The nodes in my own program are horribly fat. But I blame Mogo; they > haven't > published how they represent the tree! Joking aside, there is a lot of > potential here. > > Another approach is to play well using a smaller tree size, which means > using more > CPU power on each trial. This is the "heavy playouts" conclusion. I > speculate that > adding knowledge to the tree search and trials will pay off, and can be > beneficial even > if the program is not stronger, because smaller memory usage means that the > program > has a higher limit at longer time controls. > > Note that benchmarking programs in "lightning" games on CGOS can bias our > decisions in the wrong direction. If we use memory to make our programs > faster then > it looks like a big win. But at tournament time controls that choice merely > saturates > RAM more quickly, at a smaller tree size. > > So that's all I have to say. Just something to think about, and if you > think of a good > way to represent the tree, I hope you will return the favor. > > Best, > Brian > > _______________________________________________ > computer-go mailing list > computer-go@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ >
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
