Author: Miguel A. Ballicora
Date: 11:08:18 10/05/01
Go up one level in this thread
On October 05, 2001 at 12:28:34, Bruce Moreland wrote: >On October 04, 2001 at 20:14:30, Robert Hyatt wrote: > >>On October 04, 2001 at 18:41:14, Bruce Moreland wrote: > >>>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... > >Bob, I would be an idiot if I said that you couldn't get the same speedup by >modifying the serial algorithm. I'm not saying that. I'm saying that you might >be able to see improbable speedups when modifying a serial algorithm by making >it run in parallel. > >I'd be a fool to argue that a parallel algorithm will beat a serial algorithm >plus a guy with a compiler and some time to modify code. > >If you are now saying that a super-linear speedup could be possible, but that a >guy with a compiler could fix the serial algorithm to make it run better, we >aren't arguing about anything. There are several levels of discussion here and there were jumps from one level to another. That made the discussion impossible to follow. Level 1) given a problem and a sequential algorithm (accepted as good), once the algorithm is "parallelized" it is possible to observe a constant superlinear speedup. "parallelized" means to adapt the sequential algorithm so it will work in parallel (two threads with double the resources). Of course, technically now is a different algorithm, but let's say that changes were kept at a minimum no to break the spirit of the original sequential algorithm. Level 2a) Once this is observed, it is possible to change the original sequential algorithm to make it work better, learning from the parallel version. However, it is possible that this modification introduces new code that will make an overhead that is worse than the overhead caused by doubling the resources. Even though the modified sequential version is better than the original, it is possible that cannot remove completely the superlinear speedup leaving a residual but measurable difference. Level 2b) Even if rewriting the sequential version removes the superlinear speed up making it 2.0, the rewriting could be extremely inconvenient and in practice, it is better lo live with that. Considering that Level (3) might solve the issue. Level 3) Since rewriting the sequential algorithm might not speed it up or is very inconvenient, a suitable alternative could be to time-slice the CPU and run the parallelized version in one processor making the speed exactly 2.0 However, a balance of the overheads might make the speed up just above 2.0 So, these are the levels of the discussion and I believe i did not forget anyone. I believe that 1, 2a and 2b cannot be proven impossible. Regarding 3, Bob guarantees that the hardware of the future will never have those characteristics. I cannot read the future so I won't discuss this point any further and I will stick with 1 and 2 for now. Regards, Miguel > >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.