Author: Robert Hyatt
Date: 12:00:30 10/04/01
Go up one level in this thread
On October 04, 2001 at 02:25:11, Bruce Moreland wrote: > >The solution is always returned in one comparison in the second thread. If that is the case, it will always be returned in one comparison in the serial algorithm too, Because I will always start _there_. > >In the sequential case, with an array length of D, the number of compares >necessary is D. In the parallel case, assuming that both threads run at the >same rate, the number of comparisons is 2. With a sufficiently large value of >D, the difference between D and 2 will dominate the parallel overhead. > So. You are picking 1 out of N possible cases and saying "super-linear". Do you _know_ that case comes up every time? If so, I start the serial test there first and I get the answer in _one_ comparison. If you don't know where the key lies, then you have to analyze the algorithm for the "average" case. And there you always get <= 2.0 speedup. I don't understand why that is hard to grasp. >The data doesn't have to be average. We're talking about devising algorithms to >solve problems. You can create subset games that result in non-average data. >Supposedly perfect sequential alpha-beta doesn't work very well in those cases, >and it might work better in the parallel case. If the data isn't average, I will devise an algorithm that matches the data for optimal performance. > >What I see happening here is that people are saying that 1+1 cannot possibly be >more than 2, and then shutting their ears because they think that they've >essentially just achieved a beta-cutoff on this whole argument. This is not the >case. >\ Sorry but it _absolutely_ is the case. Just as surely as 1+1 = 2, and not something larger. >If it is possible to construct weird data that results in 1+1 being more than 2, >it is at least necessary to *consider* that there is more weird data out there >than people think, or that all of the strange things we dump on a practical >search could result in normal data turning weird, at least sometimes. Who cares about "weird data"??? In chess we have to search what we are given. That means "average data". I have already said that super-linear happens on oddball cases. But _not_ overall. > >This is why when someone says that they are getting a super-linear speedup with >parallel search, it is not sufficient to ridicule them because 1+1 cannot >possibly be more than 2. Sorry, but again, this _is_ impossible. > >This is an engineering issue, not a math or physics issue. 1+1 is sometimes >more than 2. It is therefore necessary to pay attention to people who claim >that 1+1 might be more than 2 a significant amount of the time, under some >circumstances. These claims are worth *investigating* at least. > >bruce Computer Sciences is a _math_ issue in this case. _not_ engineering. There is a simple mathematical proof for this in most any theory book...
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.