Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!csd4.milw.wisc.edu!bbn!gatech!hubcap!chandra%loligo
From: chandra%loligo@gatech.edu (Usha Chandra)
Newsgroups: comp.parallel
Subject: Distributed simulation
Message-ID: <5344@hubcap.clemson.edu>
Date: 1 May 89 12:10:45 GMT
Sender: fpst@hubcap.clemson.edu
Lines: 60
Approved: parallel@hubcap.clemson.edu

>I'm glad you brought up the subject, because I would like to raise a
>question.
>
>Here is the setting.  It's discrete-event simulation, which many or most 
>of your references are concerned with, on multiple-processor systems
>(tightly or loosely coupled).  Let P be the number of processors and T
>be the amount of run time needed to get the desired statistical accuracy.
>
>The usual approach in these papers is to have different processors handle
>different parts of this program.  E.g. one processor might manage the
>event list, another might do the statistics collection, etc.  Or, in
>process-oriented simulators like Simula or csim (or, for that matter,
>Modula II applied to simulation), each processor might handle a different
>process.
>
>It has always seemed to me that these methods are inherently wasteful.
>Each processor is going to have a substantial amount of idle time.

Thanks to the advances in parallel hardware, this method has exhibited
good performance.  Please refer the recent publications by Chandy and 
Sherman, Jefferson et al, Reed and Malony and Fujimoto.  

Some of the papers that you may want to lood at are:

1. K.M. Chandy, R. Sherman, The conditional event approach to distibuted 
   simulation, .....(I do not remember where it was published)
   But you may be able to contact R. Sherman at the following address:
   USC/Information Sciences Institute
   4676 Admiralty Way Suite 1001
   Marina Del Rey, CA 90292
   
2. D.A. Reed, A.D. Malony, Parallel discrete event simulation:......,
   Proc. of the conf on Distributed Simulation, 19,3, 1987.

3. R.M. Fujimoto, Performance measurements....., Proc. of the conf.
   of distributed simulation, 19, 3, 1987.

You may be able to find the most recent papers in proceedings of the
Winter Simulation Conference, Eastern Simulation Conference, 
SCS Multiconference ???, and Summer Computer Simulation Conference.

>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,
>but for T/P amount of run time, instead of T.  [Of course, each processor 
>needs to use a different random number seed.]
>

Some work has been done by John Comfort.  He distributed the support 
functions such as the random number generation, queue handling, 
statistics collection, event processing etc on multiple processors and 
got some performance out of it but not quite enough.

It is not that simple.  A uniprocessor version will use some form of 
event list (a sequential list) and assigning the first n events to n
processors may indeed lead to incorrect simulation.  For example, 
consider an event-list with time stamps, t1,t2,t3 ... t1 <= t2 <= t3.  
Processing the event with time stamp t1 may cause an event to be 
inserted between t1 and t2.

Usha Chandra