Author: Robert Hyatt
Date: 17:14:30 10/04/01
Go up one level in this thread
On October 04, 2001 at 18:41:14, Bruce Moreland wrote: >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. Nope. I modify my serial algorithm to match your parallel algorithm. Then it is not super-linear at all. I find it after two compares, one on the first element, one on the last. The parallel algorithm finds it after two compares also, but they are done in parallel in one cycle. Speedup = 2.0... > >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. You are making a classic mistake however. you are looking for data that will cause an anomoly and then using that to justify regular behavior. Think of all the ways that 6-number set can be permuted. And for 1/2 of them, you get no speedup of any kind. For the rest, you get some good results, but when averaged with that first 1/2, the total is always <= 2.0 in every case... > >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 If that were true, the time-sliced approach would correct it perfectly. And for _every_ case you try, you would be maybe 2x faster than the serial version at best. Both would have "search overhead". Both would find the same "synergy" to use an overworked term... And both would actually be less efficient than the real sequential algorithm for normal cases, because I _know_ that a parallel search will search more nodes than the sequential case over many positions...
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.