Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!apple!oracle!news
From: csimmons@jewel.oracle.com (Charles Simmons)
Newsgroups: comp.arch
Subject: Re: Superlinear Speedup (was Re: Scalability?)
Message-ID: <1990Jun2.080658.12651@oracle.com>
Date: 2 Jun 90 08:06:58 GMT
References: <1990May3.203405.23456@ecn.purdue.edu> <2075@naucse.UUCP> <6897@odin.corp.sgi.com> <49622@lanl.gov> <1990May1.154558.24009@cs.rochester.edu>
Sender: news@oracle.com
Reply-To: csimmons@oracle.com
Organization: Oracle Corp
Lines: 20

In article <1990May3.203405.23456@ecn.purdue.edu>,
hankd@ee.ecn.purdue.edu (Hank Dietz) writes:
> Not really.  Superlinear means better than O(n) for n processors...  hence,
> even though the case of n=1 might be a bit strange, even k*n| k>1 isn't
> superlinear.  For example, HJ Siegel has pointed out that for appropriate
> pipelined SIMD machines (read: PASM) the overlap of the CU and PEs can
> achieve an apparent speedup of 2*n...  but that is O(n), i.e., linear.

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