Author: Bruce Moreland
Date: 13:24:12 09/26/01
Go up one level in this thread
On September 26, 2001 at 14:52:19, Dann Corbit wrote: >On September 26, 2001 at 14:13:10, Bruce Moreland wrote: > >>On September 25, 2001 at 20:02:45, Dann Corbit wrote: >> >>>Superlinear speedup might be possible, even on average, but it would be due to a >>>change in algorithm. >>> >>>For instance, you can employ a completely different algorithm for parallel >>>sorting which will sort faster than any known serial algorithm. Even if you >>>divide up the work for the serial technique, the parallel algorithm will beat it >>>because the fundamental algorithm is superior. >> >>Any parallel algorithm can be expressed serially, assuming that you can make the >>hardware do the same thing both ways. >> >>I'm an engineer, not a math guy, but the math behind that is screaming so loudly >>that even I can hear it. >> >>If what I've said is false, something bad has just happened to the original >>Turing machine. > >The turing machine says nothing about efficiency. In fact, a serial tape reader >is probably just about the worst imagineable architecture. > >There are algorithms that are used only on parallel hardware. You can implement >the same thing on serial machines, but it would stink, because the fundamental >speedup comes from the parallel design. What I mean is that it should be that if you can do it on a computer, you could do it on a Turing machine, and a Turing machine is one thread. I'm not saying anything about efficiency either. >Consider the bitonic batcher sorting algorithm or the sample sorting algorithm. >They are lame on a serial machine -- you would not want to use them for any >sorting job. But for large batches of input, they are among the fastest known >sorting algorithms on a parallel machine. > >If you have a large enough collection of CPU's, you could conceivably sort a >data set in a single cycle on a dedicated parallel sorting machine. It would be >physically impossible to do that on a serial machine. > >Here is an analysis of Batcher's sort on a parallel machine: >SortingCost(N,P) = (a[i,j] C[i] + b[i,j] T j )*L[i] > >for var-hypercube C[i]=(log 2 N) and L[i]= N/P >a[i,j] and b[i,j] are system specific constants. > >It is clear that we can reduce the time to as small a value as we like by >increasing the number of processors. > >On a purely serial machine, you cannot achieve the same effect. I don't see why this should be the case. It should be like recursion, which can always be replaced by iteration. 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.