Author: Robert Hyatt
Date: 07:09:09 05/16/98
Go up one level in this thread
On May 16, 1998 at 04:02:00, Ingo Althofer wrote: >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 suppose this varies with where you read. In the literature I read, the term "linear" generally means that speedup factor a= cpus used, where a= means "approximately equal". IE a speedup could be mathematically linear by the way you defined the word, but two processors could give a total speedup of 1.01, four could be 1.02, 8 could be 1.04... which is not exactly what I'd call "linear" even though if you plot the data on normal graph paper it is obviously from a straight line... with a slope of almost zero. Most "linear" algorithms have a slope of 1 (or 45 degrees..) >>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. Again, we have to agree on a definition of "linear" first. if the algorithm doesn't run 2x faster on 2 processors, it doesn't meet the "linearity test" that most use... The problem here is that alpha/beta is simply sequential in nature. And, as a result, linear speedup (slope=1) is impossible without perfect move ordering. And we will *never* have perfect move ordering... >>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 agree... although it is impossible... >>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. yes, although most "theoretical" studies are somewhat flawed, because they make assumptions about move ordering that are often not possible. IE I know that my move ordering is about 90% correct... but that 10% is a *huge* limiting factor... and there is no way to make it better.
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.