Author: Bruce Moreland
Date: 12:14:34 10/04/01
Go up one level in this thread
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. >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. If monkeys editing code at random doesn't break Knuth and Newton, then Vincent doing the same thing doesn't, either. bruce
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.