Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!purdue!mentor.cc.purdue.edu!l.cc.purdue.edu!cik
From: cik@l.cc.purdue.edu (Herman Rubin)
Newsgroups: comp.arch
Subject: Re: parallel systems vs. uni-processors
Summary: Computationally efficient Monte Carlo is VERY difficult in parallel.
Message-ID: <1667@l.cc.purdue.edu>
Date: 19 Oct 89 12:20:18 GMT
References: <35825@lll-winken.LLNL.GOV> <20336@princeton.Princeton.EDU> <308@argosy.UUCP>
Organization: Purdue University Statistics Department
Lines: 34

In article <308@argosy.UUCP>, ian@argosy.UUCP (Ian L. Kaplan) writes:
> In article <20336@princeton.Princeton.EDU> mg@notecnirp.edu (Michael Golan) writes:

			.......................

>   Even n-cube machines run applications like Monte Carlo simulation
> with _much_ better price performance than supercomputers.  Now it
> might be claimed that this is a special class of applications.
> However parallel processors are not limited to n-cubes.  The
> Connection Machine has beaten Cray machines on a number of classic
> vectorizable codes (e.g., fluid flow).  For reference see "Proceedings
> of the Conference on Scientific Applications of the Connection
> Machine", 1988, Edited by H. D. Simon, World Scientific press.  Note
> that the Connection Machine is probably less than half the cost of the
> Cray.  I am sure that even cheaper SIMD processors will appear in the
> near future.

			......................

All computationally efficient means of generating non-uniform random numbers
involve what are called acceptance-rejection or acceptance-replacement methods.
These are most easily done on stream vector machines, and next on machines 
which have at least (vector-register)-memory transfer with non-rigid vectors,
that is, moves in which the order of the items moved is fixed, but very
definitely not the locations.  Not all vector machines have this capability,
and replacement is not vectorizable.

The problem is worse with MIMD, although something is salvageable, but
SIMD suffers from intrinsic problems.  If the replacement procedure could
be added to hardware, SIMD would only suffer a moderate penalty.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907
Phone: (317)494-6054
hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP)