Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: New crap statement ?

Author: Dann Corbit

Date: 11:52:19 09/26/01

Go up one level in this thread


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.

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.



This page took 0.12 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.