Author: Robert Hyatt
Date: 20:52:00 10/03/01
Go up one level in this thread
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.
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.