Author: Bruce Moreland
Date: 23:25:11 10/03/01
Go up one level in this thread
On October 03, 2001 at 23:52:00, Robert Hyatt wrote: >On October 03, 2001 at 18:53:31, Dave Gomboc wrote: > >>On October 02, 2001 at 16:49:03, Bruce Moreland wrote: >> >>>On October 02, 2001 at 13:50:29, Robert Hyatt wrote: >>> >>>>Absolutely not. Except for "exceptional" circumstances. IE take a chess >>>>position with two moves at the root. One of the moves leads to a very deep >>>>and complex tree. The other leads to a simple mate in 2. If you search the >>>>first one first, and then the second, you do a lot of work. If you search both >>>>in parallel, the second will finish almost instantly, give you a much better >>>>value for alpha, and cause the first search to finish more quickly. Net result >>>>is a speedup that is > 2. But there is a way to do that same thing on one >>>>processor. Search a few nodes on move 1, then a few nodes on move 2, and >>>>bounce back and forth. You quickly find (again) that move 2 leads to a quick >>>>mate and use this to prune the other move. And that super-linear speedup goes >>>>away. >>> >>>"Exceptional circumstances" is good enough. You declare this possibility to be >>>against the laws of physics, and then you find a counter-example yourself, but >>>rather than admitting that this destroys your argument, you put a box around it >>>and say that this doesn't count -- just because. >>> >>>Imagine a game where mates in one are found with very high frequency thoughout >>>the (binary) tree. >>> >>>It makes sense to write your sequential algorithm so that it checks for them >>>before searching more deeply, assuming they are easy to check for. >>> >>>If you don't bother to do this, the parallel algorithm could be faster, because >>>in essence it makes this optimization. >>> >>>It is certainly true that you can make a sequential algorithm that solves this >>>problem, but if you hadn't thought to do this, the parallel algorithm could be >>>faster. >>> >>>The reason the parallel algorith could be faster is that the parallel algorithm >>>is not the same algorithm as the sequential algorithm. Making it parallel >>>changes it significantly, and without knowing enough about the game being >>>examined, it can't be predicted which algorithm is faster. >>> >>>There is no crushingly important difference between chess and this other game. >>>If you didn't know much about the nature of chess, you might think that chess >>>could work this way, too. That chess doesn't work this way has something to do >>>with chess, not with atomic particles and laws of thermodynamics. >>> >>>This doesn't sound like something that is violating any laws of physics, to me. >>>You have two similar games, and one would result in a super-linear speedup if >>>you take a certain algorithm and run it in parallel. The other *might* not. >>>Whether it does or not has nothing to do with laws of physics, it has to do with >>>the nature of the algorithms you use, and the nature of the game itself. >>> >>>If you think the table case is bad, make a plywood box the size of a >>>foot-locker, with no handles, and fill it with bricks to the point where you >>>can't lift it. Now push that through dry sand for a mile. I don't know if >>>you've ever pushed a heavy rectangular box through dry sand, but it's hell. >>> >>>Now get another person, each grab an end, and carry it through the sand for two >>>miles. This won't be any fun but at least you won't have a heart attack. This >>>must be a much better way to do it, however you care to measure. >>> >>>>So far, in all the parallel search literature I have read over the years, there >>>>has been absolutely no case of a super-linear speedup on anything other than >>>>an exceptional case here and there. And when there are such super-linear >>>>speedups, there are _always_ the inverse cases as well, where the 2-cpu speedup >>>>is significantly less than 2. I have _never_ seen an average speedup that is >>>>super-linear, ever. >>> >>>It would be possible if the sequential algorithm did a bad job, and the parallel >>>algorithm not only resulted in work-sharing, but improved the algorithm in some >>>fashion. >>> >>>Here is an example. >>> >>>You have an array of arbitrary (big) length L. You want to write an algorithm >>>that determines if there is a value in the array that is less than or equal to >>>N. >>> >>>An obvious sequential algorithm traverses the array from 1..L, searching for a >>>value less than N. If it finds one, it stops. >>> >>>An obvious parallel algorithm, designed to run on two processors, puts one of >>>them to work searching 1..L/2, and the other searching backwards from the end >>>(L..L/2+1). If either processor finds a value less than N, both stop. >>> >>>The parallel algorithm would exhibit a super-linear speedup if the array >>>contained null-terminated strings, the array-length was the length of the string >>>+ 1, and N was 1. The second processor would always cut off on the first >>>element it looked at, so with a sufficiently large L, this algorithm would >>>destroy the sequential algorithm no matter how much parallel overhead was >>>involved. >>> >>>This would be a dumb way to process this data, but the issue here is not to find >>>a SMART algorithm that returns a super-linear speedup, but rather to find ANY >>>algorithm that does it, since you are being so "laws of physics" and "all the >>>parallel search literature" about this. >>> >>>And even though it's dumb way to do this, you might not have known it was a dumb >>>way when you wrote it. You might not have known what kind of data you were >>>going to be dealing with beforehand. >>> >>>In this case, the average speedup is probably super-linear. Note that >>>sequential algorithms exist, but that doesn't matter. We're talking about an >>>obvious sequential algorithm modified to work in parallel, like what we do with >>>alpha-beta. >>> >>>What does this mean? It means that when some crazy person suggests that they've >>>found a super-linear speedup in a chess program, you should at least LISTEN >>>before you call them crazy (or stupid). >>> >>>Is Vincent crazy? Maybe we should take a poll. One thing that is sure is that >>>the laws of physics don't demand that he must be. >>> >>>bruce >> >>Observing that the parallel algorithm was super-linearly quicker immediately >>gives rise to a superior sequential algorithm: alternate checking from the front >>of the array and the back of the array for the zero. It would quickly be >>observed that the parallel algorithm does not have super-linear speedup over >>this superior sequential algorithm. In addition, the sequential algorithm may >>be further optimized by ignoring the front of the array altogether, which would >>reduce the parallel speedup further. >> >>To ignore the superior sequential algorithm and instead publish results >>comparing only the original, poor sequential algorithm with the parallel >>algorithm is not merely disingenuous but simply bad science. >> >>Dave > > >Don't forget that this algorithm did not present super-linear performance for >all cases. I gave a 6-case analysis, where the speedup for two processors was >1, 1, 1, 2, 2.5 and 4.0... when you average the speedup for all 6 possible >places the desired number can be, you get a speedup of just under 2.0. Which >is not super-linear. Nobody says you can't have super-linear speedup on >special cases where the normal algorithm is horrible. But for an average over >all possible cases, super-linear is simply not going to happen. The solution is always returned in one comparison in the second thread. 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. 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. 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. 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. 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. 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
This page took 0.02 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.