Author: Ingo Althofer
Date: 01:02:00 05/16/98
Go up one level in this thread
On May 11, 1998 at 09:40:18, Robert Hyatt wrote: >On May 11, 1998 at 06:12:30, Ingo Althofer wrote: >>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. Misunderstandings are something quite natural, when practice and theory meet. I have made experiences with this over many years in the field of game tree search and especially parallel game tree search. First of all a clarification. When theorists speak of linear speedup they mean that a system with n processors needs only time c/n in cases where one processor needs time 1. c has to be a positive constant, independently of n, but not necessarily c=1. In case of c=1 the speedup is called "full" instead of linear. >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. That is not true. There are three results for uniform game trees with arbitrary move ordering. (However, they all concern 0,1-valued trees only. ) In 1988 I was able to prove an average linear speedup with n processors in trees of depth constant*n*log(n). Shortly later and independently Richard Karp and Yanjun Zhang gave an algorithm with a linear speedup in all trees ( so a worst case result ). Their algorithm used n+1 processors in trees of depth n. "Finally" (in 1991) Juergen Harting (my diplom student) extended their result to polynomially many processors ( polynomial in the tree depth ). A special case of his is the two-level-algorithm with quadratically many processors in the tree depth. >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. From the view point of theory 11.7 with 16 would be very pleasing, if you also got 117 with 160 processors, speedup 1170 with 1600 processors, speedup 11700 with 16000 processors, and so on ( so a linear speedup ). >I ran >a few tests on a 32 processor machine and saw results like 18.x or so, >which >is getting very bad... I am well aware on the gap between theory and practice. Nevertheless the theoretical investigations help to give a better understanding of the principal problems. Ingo Althoefer.
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.