Author: Robert Hyatt
Date: 20:57:37 10/04/03
Go up one level in this thread
On October 04, 2003 at 03:41:39, Sune Fischer wrote: >On October 03, 2003 at 22:14:53, Robert Hyatt wrote: > >>>Your last statement is inconsistent with your "If efficiency continues to climb, >>>it is unbounded." >>> >> >>It isn't if you remain "in context". >> >>You picked an equation with a simple limit. > >I think Vincent only said the efficiency would rise, this doesn't imply it's >unbounded. I too got the impression that this was what he meant though. He has _clearly_ said (many times) that it rises beyond N where N is the number of processors. Since the entire question of parallel search depends on N, and if N doesn't serve as a bound, I can't see what would... > >>Vincent's "equation" has no known limit yet, because the obvious limit >>for N processors is <= N, but he has (for years) claimed efficiency > N >>for N processors. Since N is the controlling term in any equation based >>on N, and since N is not a limit, the speedup (to me) appears to be >>unbounded, plain and simple. Any speedup whatsoever that is >N means it >>must be unbounded. >>And we already have the >N claim in writing, many times. >> >>(not from me or anybody that knows what they are doing, however). > >Anyone who understands the basics of alpha-beta knows it's absurd. >The funny thing is it can happen in practise, unfortunately it's nothing to be >happy about, it just means that your serial search isn't "optimal". Careful in how you word that. >2 is possible in _some_ positions. But _not_ in an average set of positions. That's probably what screws up Vincent's numbers, using a single position. I have several that produce > 2 speedup with 2 processors. I have several that produce <1.5 speedup with 2 processors as well. I've _never_ produced an average speedup > 2.0 for any reasonable set of positions... >I guess a program using reversed move ordering would be quite capable of >consitently producing >2 speedups? :) Yes, but then there is a way to make the serial algorithm faster. Search two root moves, one node at a time on move one, one node on move two, bouncing back and forth with a single thread. That will run faster than the bad serial algorithm, and then the parallel algorithm won't go > 2x faster than that. > >However Vincent did have an interesting point, that with N threads he can do N >probes to the hash table 'in parallel'. Possibly, but very unlikely. That assumes that for N processors, each hash probe goes to a _different_ memory bank. How likely is that? For a large number of processors, it is nearly not going to happen at all. >Seems this would lower the latency relative to running just one thread on twice >as fast a processor where the latency (counting clocks) would just go up. >That factor has got to be peanuts relative to the parallel overhead though. > >-S. Not to forget the _cost_ of probing in another processor's memory.
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.