Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: New crap statement ? Perpetuum mobile

Author: Robert Hyatt

Date: 14:36:55 10/04/01

Go up one level in this thread


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

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.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.