Author: Robert Hyatt
Date: 06:40:18 05/11/98
Go up one level in this thread
On May 11, 1998 at 06:12:30, Ingo Althofer wrote: >On May 10, 1998 at 00:52:18, Keith Ian Price wrote: >>Sorry for the delay. Here is Part III of my Deep Blue Report: > >First of all again many thanks to Keith Price for his informative >report ! If all CCC-contributions were of this calibre ... > >Then, please excuse the strange format of this reply. It is my poor >hardware >and software equipment, which does not allow formating. > >Concerning the quote (very) below I simply want to mention that there >is a diplom thesis written by Juergen Harting at the University of >Bielefeld in 1991, in which he analyses such a two-level parallel >algorithm for game tree search with quadratically many processors. He >was able to prove a linear speedup. > >Ingo Althoefer. > > > > > I hate to comment on something I haven't read, but there is a wide gap between "theory" and "practice". Alpha/beta is inherently sequential, because the first move establishes a bound that can be used to refute successive moves quickly. Any parallel search that produces "linear" speedup has to have one of two characteristics: (1) moves are arranged in worst-to-best order, so that the tree is essentially minimax, which is *easy* to search with linear speedup; (2) moves are arranged in best-to-worst order, because we also know how to search perfectly ordered alpha/beta trees and produce a linear speedup. But searching typical chess trees makes this impossible. Searching with 16 processors, the very best speedup I have ever seen is the 11.7 produced by Cray Blitz, as reported in the JICCA last year sometime. That's a long way from linear, and, in fact, the curve is flattening quite badly. I ran a few tests on a 32 processor machine and saw results like 18.x or so, which is getting very bad... I've seen no results that don't get somewhat worse with more processors, excepting for Feldman's "young brothers wait" which starts off fairly badly but doesn't get worse. (by badly I mean that with 2 processors, It may only be 1.5-1.7 times faster, where Cray Blitz was almost dead on 2x faster...) > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > >>Other differing reports about how >>many processors DB used were also answered. Deep Blue employed 30 SP2 >>Scalable Processors. The frames were capable of holding sixteen each, >>and there were two frames, but in each frame, two processors were tied >>together to form a master processor, which meant a total of 30 instead >>of thirty-two. Each SP2 had 16 chess processors attached, so that meant >>a total of 480 chess processors. Up until this point I had only heard >>256 or 512. Hsu said that Deep Blue used "two-level parallelism" to >>process positions. He described this as the method of the master >>processor evaluating the first 4 moves, then sending the 1000 or so >>positions involved to the other SP2s, which would carry it out for >>another 4 moves, and then turn over the positions to the chess >>processors, which would go on for 4-5 more moves. ...
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.