Author: Robert Hyatt
Date: 10:50:29 10/02/01
Go up one level in this thread
On October 02, 2001 at 12:16:48, Sune Fischer wrote: >Hi > >Just curious, does anyone know of a parallel algorithm which is faster than the >serial one, for any type of problem? Absolutely not. Except for "exceptional" circumstances. IE take a chess position with two moves at the root. One of the moves leads to a very deep and complex tree. The other leads to a simple mate in 2. If you search the first one first, and then the second, you do a lot of work. If you search both in parallel, the second will finish almost instantly, give you a much better value for alpha, and cause the first search to finish more quickly. Net result is a speedup that is > 2. But there is a way to do that same thing on one processor. Search a few nodes on move 1, then a few nodes on move 2, and bounce back and forth. You quickly find (again) that move 2 leads to a quick mate and use this to prune the other move. And that super-linear speedup goes away. So far, in all the parallel search literature I have read over the years, there has been absolutely no case of a super-linear speedup on anything other than an exceptional case here and there. And when there are such super-linear speedups, there are _always_ the inverse cases as well, where the 2-cpu speedup is significantly less than 2. I have _never_ seen an average speedup that is super-linear, ever. > >I know of many that can be done equally fast (in theory) at 2x half the power, >for example vector operations. Fortran 90 (and above) has some great support for >that. That isn't quite the same thing. The issue is using two "equal processors" to run > twice as fast. A vector processor is not the same. It isn't just 2x as fast, for example. It is a totally different architectural approach to computation. > >I have never ever heard of a parallel algorithm that was faster than the serial >one (on 1 CPU of cause). >It seems the communication and coordination between threads plus the increased >complexity will always cost you performance. For some applications, that are often called "embarassingly parallel" (ray-tracing is one simple example that comes to mind) 2x is easy. 4x is easy on 4 processors. But not >2x with 2, nor > 4x with 4. In ray tracing there is almost no communication/coordination. that is why is is called "embarassingly parallel". >I'm pretty sure one can design a formal proof, using... minimal entropy >principles?? The timeslicing argument/proof is good enough for me though. > >Even if such an algorithm existed, which I seriously doubt, then I don't believe >it would run >2x faster on a dual 1 Gig than on a single 1 Gig chip. >I have tried myself parallizing a FFT algorithm to about a 95% effciency, it ran >only 23% faster (dual celerons on an Abit BP6 mobo). I conclude there were other >bottlenecks, and most likely there will be on most PC-systems for a long time to >come. The BUS is not fast enough to supply two chips whith data all the time, it >can hardly keep up with 1 chip as it is. >That of cause is a different story, and may change in the future. Cache helps, of course. But memory bandwidth is an issue on PCs... > >-S.
This page took 0.03 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.