Path: utzoo!attcan!uunet!lll-winken!ames!rex!uflorida!gatech!hubcap!wen-king
From: wen-king@csvax.caltech.edu (Wen-King Su)
Newsgroups: comp.parallel
Subject: Re: Distributed simulation (Discrete Event)
Message-ID: <5311@hubcap.clemson.edu>
Date: 27 Apr 89 20:03:37 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 50
Approved: parallel@hubcap.clemson.edu

In article <5276@hubcap.clemson.edu> matloff%mole.Berkeley.EDU@ucbvax.Berkeley.EDU (Norman Matloff) writes:
>
<It has always seemed to me that [distributed] methods are inherently wasteful.
>Each processor is going to have a substantial amount of idle time.
<
>Moreover, it seems to me that the best method is also the simplest  --
<just have all P processors run the uniprocessor version of the program...
>
<This method gives 100% utilization for all processors...

Since you are not worried about the elapse time of the simulation runs,
which may is itself the most important consideration in some simulations,
I will assume that throughput is the single most important consideration
here.  Even with this assumption, however, it still depends on how you
compute the cost of hardware.

If the cost is proportional to the number of processors, running one
sequential simulation on each processor clearly is optimal.  Since 100%
of the processors are in use at all time, as the number of processors
doubles, the throughput doubles as well.  Nothing can do better than that.

However, if the cost is proportional to the amount of hardware involved,
distributed simulation can be more efficient.  For the purpose of this
discussion, let us first assume that:

	1) Hardware used == the amount of memory involved.
	2) Simulation requires the same amount of memory
	   no matter how many processors are used.

Now, if we further assume that the simulation shows no speedup, it will
still be as efficient as the sequential simulation.  However, if we assume
that the speedup is linear, every time we double the processors and half
the memory per processor, we also half the elapse time.  We doubled the
throughput using essentially the same amount of hardware.  Although the
truth is somewhere in between, if the distributed simulation shows any
speedup at all, it will be more efficient than the sequential simulation.  

In reality, neither 1) nor 2) are true, but the truth lies not far away
and the distributed simulation has to show some degree of speedup just
to break-even.  But if it does better than break-even, it will be more
efficient than the sequential simulation.

One may argue that in real life, the processor size can't change as we
use more and more processors.  In real life, however, neither can a
simulation that tightly fits a 100 processor multicomputer be run on
just one processor of the multicomputer.

/*------------------------------------------------------------------------*\
| Wen-King Su  wen-king@vlsi.caltech.edu  Caltech Corp of Cosmic Engineers |
\*------------------------------------------------------------------------*/