Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!uwm.edu!uwvax!beaner.cs.wisc.edu!sls
From: sls@beaner.cs.wisc.edu (Steve Scott)
Newsgroups: comp.arch
Subject: Re: Superlinear Speedup (was Re: Scalability?)
Message-ID: <10525@spool.cs.wisc.edu>
Date: 4 Jun 90 19:31:47 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> <1990Jun2.080658.12651@oracle.com>
Sender: news@spool.cs.wisc.edu
Organization: U of Wisconsin CS Dept
Lines: 23

In article <1990Jun2.080658.12651@oracle.com> csimmons@oracle.com 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

Not that this is related to architecture,  but alpha-beta search actually
displays just the opposite sort of behavior.  Since pruning is so effective,
exploring multiple branches of the search tree in parallel results in a
tremendous amount of wasted search because the cutoffs from previous
branches are not available yet.  Many people (myself included) have
attempted to alter the algorithm in various ways to lessen this affect, but
no one has been able to approach even linear speedup.

--Steve