With respect to the argument that an N-processor machine can't do better
than a factor of N speed improvement: the argument sounds airtight, but
it's not always correct. Instances of superlinear speedup occur, and not
merely as a theoretical possibility. While I was consulting at Compaq
(previously Digital) a customer reported such a case (I believe they feared
the numbers indicated the presence of a bug in their program or in the
operating system). This was on a multiprocessor Alpha system. Hennessy &
Patterson also noted an instance of it in their book (I'm referring to the
2nd edition).
There was no bug: superlinear speedup can happen when each processor has
its own cache, so the effective size of the cache grows as N is increased.
It is most likely to occur in programs with good locality of reference
where the problem size is considerably larger than the innermost local
cache size.
Knowing whether this really occurs for any particular processor will
require actually making the experiment (though a really careful model could
produce results which were likely to be accurate predictions). Achieving
the effect also requires that the binding of processors to threads is
sufficiently stable, either by explicit arrangement or by fortuitous
properties of the OS and/or threads software.
I have no time to recode the program myself, but the following is
addressed to the author of MacGIMPS if he is reading this: I will soon have
a 4-processor Daystar system bootable to BEOS, and I'm willing to have it
serve as a guinea pig.
Michael Yoder
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
