Author: Robert Hyatt
Date: 10:38:20 10/11/01
Go up one level in this thread
On October 10, 2001 at 17:12:37, Miguel A. Ballicora wrote: >On October 08, 2001 at 14:59:12, Robert Hyatt wrote: > >>On October 08, 2001 at 13:52:56, Olaf Jenkner wrote: >> >>>I'm mathemathician. I believe that every student of informatics learnt something >>>about this topic. Maybe we can construct a turing machine to prove the >>>impossibilaty of SS. Is this the case? If it is, why does Dr. Hyatt waste his >>>time to convince people about it? >>> >>>OJe >> >> >>Simply because I have become a "teacher" over the past 31 years of my life >>as a university faculty member. And such "myths" need to be corrected when >>they show up, else they become self-propogating 'truths' that are anything >>but that... >> >>I have given the simple approach to proving this that is given in most every >>book I have seen (the time-slicing approach). I have referenced the formal >>proof in theory books that show "A two-tape (which is really a two-instruction >>stream) Turing machine has no more computational power than a one-tape (one >>instruction stream) computer." I have taken _every_ suggested algorithm that > >I am going to be a good boy and go to the library that is few blocks from here >(I have to go anyway). >Can you give the exact reference so I can read that theorem? If possible, >the name of the theorem or much better the name of a book and page number. >I think I should be able to find it. > >Regards, >Miguel Here are a few reference choices: Parallel programming by Barry Wilkinson and Michael Allen page 27, "superlinear speedup" in italics. they give the same "refutation" to the idea that I have mentioned dozens of times. Middle of the page. ISBN 0-13-671710-1. Parallel Algorithms and Architectures by Michel Cosnard and Denis Trystram. Bottom of page 32. ISBN 0-534-94607-0. If you have access to the journal "Parallel Computing" then you might check "V. Faber, O. Lubeck and A. White. Superlinear speedup of an efficient parallel algorithm is not possible." Parallel Computing, 3:259-260, 1986. I have seen (somewhere) one author that said Super-linear speedup was possible. But with one major constraint: "You must first write the serial algorithm, and then parallelize it, and then after running it you might get a super-linear speedup. However it is not permissable to note that in this case the original serial algorithm is not the most efficient one, and to rewrite it into a more efficient version that will negate the super-linear speedup." Which only supports the position most of us hold that if you get a super- linear speedup, the serial algorithm is no good and can be improved. If in no other way than by running multiple threads on a serial architecture. This kind of "fix" only applies to problems related to "searching" of course, which is a small percentage of all known parallel algorithms. Purely computational models like ray-tracing and so forth don't produce super-linear speedups _ever_. And search only does it in anomalous cases that would be solved by parallel searches on a serial machine. I can give more references if you need them. Those are all fairly recent books except for the 1986 paper. Lubeck, by the way, worked at Los Alamos and we had lots of interesting conversations about this topic when I was visiting Los Alamos every summer for several years... > > >>supposedly exhibits super-linear speedup and shown through simple mathematical >>analysis that the average is _never_ super-linear. >> >>I'm not sure what else can be done.
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.