Author: Bruce Moreland
Date: 14:47:07 10/04/01
Go up one level in this thread
On October 04, 2001 at 15:00:30, Robert Hyatt wrote: >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. In the case of my simple algorithm, if you had been told to write a parallel algorithm to process it, and a serial algorithm to process it, you may have written both the algorithms the way I suggested. Perhaps you wouldn't have gone backwards with the second thread, but in a group of 1000 students, I bet a few would have. If you had done this, and then I had dumped some "mystery data" on you, which happened to be a series of null-terminated strings, you would have noticed that the parallel algorithm would have experienced a super-linear speedup. I think that there are some people who read this group who, if they hadn't bothered to figure out why this had happened, would insist that the student had a bug, because such a performance increase was impossible. Both the serial and parallel algorithms are fine. The problem was with the data. If the student had avoided getting stomped to death by the teacher for being a computer science apostate, and had taken the trouble to understand the super-linear speedup, rather than shutting his eyes denying its possibility, he would have noted the obvious pattern in the data, understood it fully, and changed the serial algorithm so it would work better on this data. Maybe. It would actually work worse on other data, since going backwards is less efficient than going forwards. Perhaps this would have stimulated a discussion about how to write such an algorithm, in order to avoid pathologies while retaining performance in more entropic cases. Perhaps the serial algorithm should have been modified to check the first and last elements first, a change that would be a waste of time if all data was perfectly entropic. Perhaps as a result, someone would have learned something, and some progress would have been made along some axis. If the student is labelled an idiot, and Isaac Newton is invoked against him, no progress is made and nobody learns anything. The pathological data had a very heavy and obvious pattern in it. It is possible that other patterns exist in real-world data, and there is an algorithm other than the initial sequential algorithm (which has got to be provably perfect if the data is entropic) would work better. The key is understanding the data, but this is not always completely possible. A game tree is not completely entropic either, and I doubt it is well understood by the people who manipulate them. It may have some patterns in it as well, which might be eploited either intentionally or unintentionally, by changes in an algorithm. Taking a serial alpha-beta algorithm (with pruning and extensions and hash tables and all that) and adding parallelism to it is a change that could result in an improvement in performance, because the new algorithm does not search the same tree in the same order as the old one does. This is why I think that someone who claims to have found a super-linear speedup when doing a parallel search should not be labeled a computer science apostate. A chess tree probably has enough entropy in it that the claim is due to a bug, random chance, or bad performance measurement technique, but it is always possible that some common orderliness inside the tree has been found and exploited. bruce >>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.