Author: Bruce Moreland
Date: 15:22:56 10/04/01
Go up one level in this thread
On October 04, 2001 at 17:36:55, Robert Hyatt wrote: >On October 04, 2001 at 15:14:34, Bruce Moreland wrote: > >>On October 04, 2001 at 14:55:32, Robert Hyatt wrote: >> >>>I don't follow any of that. If in your algorithm, the number you want is in >>>the first half of the list, you get no speedup whatsoever. That is exactly >>>1/2 the cases. If it is in the second half of the list, you get anywhere from >>>nothing to a huge speedup. If it is on the end of the second half, you get >>>nothing. If it is on the front, you get a huge speedup. >> >>You didn't read the algorithm carefully. The first thread searches sequentially >>forward to the middle. The second one searches sequentially backward to the >>middle. So if the one at the end of the data is always the one you want, you >>find it in optimal time. > > >So. My analysis still holds. For the 6-number dataset you get this instead >of the numbers I gave the first time > >position of key time to find seq time to find par > >1 1 1 >2 3 2 >3 5 3 >4 6 3 >5 4 2 >6 2 1 position of key sequential parallel 6 6 2 According to the data and algorithms I have described now several times. bruce > >The speedup is then (1/1 + 3/2 + 5/3 + 6/3 + 4/2 + 2/1) /6 = > >(1 + 1.5 + 1.66 + 2 + 2 + 2)/6 = 1.69 speedup > >Note that since you changed your algorithm, I copied it. I check the first >number, then the last number, then the second number, then the next-to-last >number, etc. > >And it is _still_ not super-linear. > >> >>>But compute the averge. >>> >>>If you want to say "but the average is no good, I know the number is always in >>>the second half" then we use the timeslicing approach and the super-linear >>>speedup goes away. Or even better, if we know it is in the second half of >>>the list more than 50% of the time, we just search the list backward and your >>>parallel algorithm gets _zero_ speedup. >>> >>>But if you _really_ don't know where the number you want is, if it is _really_ >>>uniformly distributed throughout the list, then the normal algorithm (front to >>>back or back to front) and the parallel version of that same algorithm will >>>_not_ produce a super-linear speedup. >>> >>>The "appeal" to knuth, aho, hopcroff, ulman, et all is dead serious and >>>right on target. This has been proven already to be impossible... >> >>If the problem is "find the minimum value in the array", you are right. A >>two-thread program will always be twice as fast as a one-thread program, because >>you split the work exactly in half, and neither thread can cut off early. >> >>If you do an alpha-beta searching task where your move ordering isn't 100% >>perfect, you aren't right. You end up fiddling around until you get a >>single-thread version working alright. But this isn't necessarily provably >>best, so there is room for improvement. You could have monkeys edit it at >>random and there is always a chance that it will get better. > > >I have never said otherwise. I have said that if you average the speedup over >a large set of positions, it is _impossible_ to get a super-linear speedup for >that average. As I showed in your example. In fact, unless I did something >ugly in the math, your new algorithm _never_ produces a super-linear speedup. >It does produce 2.0 three times. But it produces < 2.0 3 times as well. The >average is still <= 2.0 which it must be. > > > >> >>If monkeys editing code at random doesn't break Knuth and Newton, then Vincent >>doing the same thing doesn't, either. > > >apples and oranges. One position _can_ be super-linear. A large set of >positions can _not_ be. Nothing complicated about that, and nothing ambiguous >either. One super-linear case here and there is not only not unusual, it is >demanded in computer chess. Because we _know_ move ordering is not perfect. >And the odds are always present that we will find something quicker in a >parallel >search because we search two at a time. But that will be the exception, not >the rule. And that has been my only point from the beginning. I don't care >about exceptional cases. I want to know about the _typical_ case. Those are >the positions I am going to get _most_ of the time. >> >>bruce
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.