Author: Bruce Moreland
Date: 15:41:14 10/04/01
Go up one level in this thread
On October 04, 2001 at 18:25:46, Robert Hyatt wrote: >On October 04, 2001 at 18:22:56, Bruce Moreland wrote: > >>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. >> > > >Did I misunderstand that you said "one thread starts at the front, the >other starts at the end?" If so, then 1 is correct. Because both tests >will be done in the first cycle. You have done 2 total cycles of work, but >one real cycle since you use two processes. > >Or did I misinterpret what you said somehow??? The thing you are looking for is, by coincidence, always at the end. So you will always find it the first time the second thread looks at something, since it starts at the end. Meanwhile, the first thread has looked at the first thing at the head. So I'd counted this as two units of work. Two units of work is more than twice as fast as six units, so this particular case is super-linear, barely. You can make it more so by making the arrays longer. This is obviously pathological. I don't think it matters. It shows that if you code two similar ways, one can be vastly better because of differences in the kind of crap you pump into it, and this may not be knowable at the time you code. If you didn't know anything about a chess tree, the same kinds of thing could happen there. But you've tuned things to the point where this kind of thing is extremely unlikely. Maybe things aren't tuned all the way though, or maybe this kind of thing happens enough that it could indicate that some small improvement to the sequential algorithm is possible. There could be other game trees where this happened more often -- where a two-processor search could work qualitatively better than a one-processor search, since you haven't discovered everything you need to know about the tree. 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.