Author: Dave Gomboc
Date: 15:17:41 10/04/01
Go up one level in this thread
On October 04, 2001 at 17:47:07, Bruce Moreland wrote: >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. If the sample data is representative of the population data (rather than being outlier data) then the serial algorithm is not fine, it is terrible. >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. But if the parallel algorithm is consistenly better than the sequential one, then you can implement a sequential algorithm to simulate the parallel one, which will also search the tree in the new, better order. >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. I already suggested to Vincent that he look for phenomena similar to what is described in "Rapid Random Restart". I have privately speculated about this happening in game trees for some time already.
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.