Newsgroups: comp.arch
Path: utzoo!utgpu!watserv1!watmath!watmsg!sccowan
From: sccowan@watmsg.uwaterloo.ca (S. Crispin Cowan)
Subject: Re^2: Superlinear Speedup (was Re: Scalability?)
Message-ID: <1990Jun3.145408.2472@watmath.waterloo.edu>
Sender: daemon@watmath.waterloo.edu (Owner of Many System Processes)
Organization: University of Waterloo
References: <1990May3.203405.23456@ecn.purdue.edu> <2075@naucse.UUCP> <6897@odin.corp.sgi.com> <49622@lanl.gov> <1990May1.154558.24009@cs.rochester.edu> <1990Jun2.080658.12651@oracle.com>
Date: Sun, 3 Jun 90 14:54:08 GMT
Lines: 42

csimmons@jewel.oracle.com (Charles Simmons) writes:

>I'm curious as to what extent researchers have observed real superlinear
>speedups.  For example, consider a chess program.  On an old-fashioned
>single processor architechture, the program will examine multiple
>alternatives one at a time.  The results of each alternative can trim
>the amount of searching required in subsequent alternatives.  (The
>alpha-beta cutoffs become closer together.)  Now we might imagine that
>a version of the program written for a parallel machine might be able
>to benefit from examining multiple alternatives in parallel.  For example,
>if one alternative is highly advantageous, it might cause the alpha-beta
>cutoff values to get lots closer lots faster.
>-- Chuck

It's a theorum that (theoretically, anyway) super-linear speedup cannot
occur.  In practice, it may occur marginally, but this is due to the
fact that P processors have:
	-P times as much cache
	-P times as many data lines to their local main memory (modulo
	shared memory)
And therefore approximately P times the memory bandwidth.

As some may have noticed, high-performance RISC processors are reducing
even compute-bound problems to memory BW-bound problems.  Not because
RISCs are memory pigs, but because they run so fast that they saturate
the memory bandwidth.  So the major win of multiple processors is
becoming the increase in bandwidth to memory.

Crispin
----------------------------------------------------------------------
(S.) Crispin Cowan, CS grad student, University of Waterloo
Office:		DC3548	x3934		Home phone: 570-2517
Post Awful:	60 Overlea Drive, Kitchener, N2M 1T1
UUCP:		watmath!watmsg!sccowan
Domain:		sccowan@watmsg.waterloo.edu

"You can have peace.  Or you can have freedom.  Don't ever count on
having both at once."
	-Lazarus Long
"You can't separate peace from freedom because no one can be at peace
unless he has his freedom."
	-Malcolm X