Author: Robert Hyatt
Date: 12:18:37 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. I would agree. Most theory books contain a proof to show that a 4-tape Turing machine gives no more "power" than a 1-tape turing machine. That is, anything you can do on a 4-tape machine, I can do on a 1-tape machine. It will run a lot longer, by necessity. But it will work. > >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. > I won't disagree. I always show a modified bubble-sort in my parallel programming course. It has no synchronization at all, and it produces a linear speedup for any N up to the size of the array to be sorted. However, as you back that algorithm back to smaller numbers of processors, the benefit drops. By the time you get back to 2 cpus, you get burned by a normal heap sort. Because with two cpus, you are (N^2)/2 operations, while heap is at N log(N) operations. So the original point _still_ remains. If a parallel algorithm is producing a super-linear speedup, it is just being compared to a very poor sequential algorithm. Either the parallel algorithm is simply better, or the parallel operations are covering up for some serial design flaw. >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. The question is, however, is "how does it do on 2 processors compared to the best sort algorithm on 1?" or "how does it do on 1 processor compared to the best sort algorithm on 1?" And none of this really has anything to do with chess. Alpha/Beta is a well- defined algorithm. There is no "flexibility" in how it is done, because it is a simple mathematical expression of a search space (the minimum search space) that must be traversed to produce a result. Nobody claims that someone might not one day develop a better algorithm to do searches in parallel. Something not based on alpha/beta at all. But right now we are all using the _same_ basic algorithm, whether serially or in parallel. And _that_ makes super-linear impossible to accept on a regular basis. It just won't happen.
This page took 0.06 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.