Author: Robert Hyatt
Date: 11:37:08 10/04/01
Go up one level in this thread
On October 04, 2001 at 02:01:59, Bruce Moreland wrote: >On October 03, 2001 at 18:53:31, Dave Gomboc wrote: > >>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 > >My sequential algorithm is just fine if you have no idea what the data looks >like. My parallel algorithm is also just fine if you have no idea what the data >looks like. > >The fact that the data encountered in real life creates a worst case for the >sequential algorithm and a best case for the parallel algorithm is a happy >coincidence. It also refutes the idea that a dual-processor algorithm cannot be >faster than 2x the speed of the single-processor algorithm that it is derived >from, which was the point of the exercise. I was trying to demonstrate that the >parallel algorithm is not equivalent to the single-processor algorithm running >on two processors -- it is a different algorithm. > >Of course, if you know what the data looks like, you can make a sequential >algorithm that solves the problem, but it is permissible to stipulate that you >don't know what the data looks like. > >Bob was saying that you can't get a more than 2x speedup with two processors no >way no how except in some pathological cases. And that is true. I analyzed your algorithm in detail and found that it does _not_ produce super-linear speedup over normal cases. Only in very special cases (where the value you want is in the second half of the list, and not at the end of that half). If you can prove that this case happens more than statistics suggest it does, then I change the serial algorithm to account for that and your super-linear speedup totally evaporates. But as your algorithm is stated, it does not produce a speedup > 2 when you test _every_ possible case of the input stream... > >I could have responded by suggesting that pathological cases could be common in >some domains, but I thought this might be too big a pill to swallow, so I tried >to come up with some examples that I thought everyone could understand and agree >on. > >Silly me. I don't see the need for that kind of comment. Your example was flawed. No big deal. Had you done the detailed analysis I did you would have seen that it was flawed. But in this case, you did what Vincent likes to do. "Aha, here is a case of super-linear speedup which proves that it can happen." I respond with "aha, here are N _other_ cases of input data where it does _not_ happen, and the overall average is not super-linear at all." > >The long argument about whether dragging something is necessarily *more* >efficient than carrying something is especially crazy, as anyone who has tried >to get a recalcitrant two year-old up a flight of stairs can tell you instantly. > Of course now I've changed that example slightly and I look forward to another >long argument about thermodynamics as applied to little kids. Or I should say, >I look forward to ignoring such an argument. > >I provided an overly simple but not completely crazy example of an algorithm >where you'd get way more than 2x speedup if you parallelized it in an obvious >way for two processors. Bob proceeded to discuss another algorithm entirely. > >I have better things to do than try to convince a mule that it is stubborn. The >mule will be stubborn no matter what I say, since that is its nature. I have >better things to do than spend time arguing with people who don't listen. > >bruce Aha. I point out a fatal flaw in your simple "number search" and now I am "stubborn as a mule?" Your algorithm was _not_ a super-linear algorithm. Unless you only consider 1/3 of the 6-number test set I gave you. Because 2 of 6 cases were super-linear. Is that good enough to make the claim? Even when the _average_ of all 6 is < 2.0??? I don't think so. And I don't think it makes me "stubborn as a mule" unless you put it in the context of "he is stubborn as a mule because he will not accept statements that are utter nonsense, and he continually does careful analysis to point out the flaws in those statements. I don't see why he won't let me take my one special-case example and claim super-linear performance, and shut up about it." Interesting definition of stubborn. I certainly await another attempt at super-linear. There has not been _one_ yet. not in over 50 years of computer science. There won't _ever_ be one either...
This page took 0.01 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.