simulation@uflorida.cis.ufl.edu (Moderator: Paul Fishwick) (10/09/89)
Volume: 11, Issue: 8, Mon Oct 9 09:47:44 EDT 1989
+----------------+
| TODAY'S TOPICS |
+----------------+
(1) Need Address Traces
(2) Workstation Symposium
(3) SPICE Availability
(4) Optimality Considerations of Time Warp
(5) Conservative Parallel Simulation
* Moderator: Paul Fishwick, Univ. of Florida
* Send topical mail to: simulation@bikini.cis.ufl.edu OR
post to comp.simulation via USENET
* Archives available via FTP to bikini.cis.ufl.edu, login as
'ftp', use your last name as the password, change
directory to pub/simdigest.
* Simulation Tools available by doing above and changing the
directory to pub/simdigest/tools.
-----------------------------------------------------------------------------
Return-Path: <news@CS.UCLA.EDU>
To: comp-simulation@uunet.uu.net
Path: ucla-cs!kurisaki
From: kurisaki@CS.UCLA.EDU (Lance Kurisaki)
Newsgroups: comp.parallel,comp.simulation
Subject: Need address traces
Date: 5 Oct 89 20:47:43 GMT
Sender: news@CS.UCLA.EDU
Reply-To: kurisaki@CS.UCLA.EDU (Lance Kurisaki)
Organization: UCLA Computer Science Department
Hi,
I need to get a hold of some address traces generated
by applications running on a multiprocessor to use in
a simulator of a multistage interconnection network. Could
anyone point me in the righty direction? Thanks a lot.
Lance Kurisaki
kurisaki@cs.ucla.edu
------------------------------
Date: Fri, 6 Oct 89 09:17:38 EDT
From: kra@demon.siemens.com (Kenneth R Anderson)
To: fishwick@fish.cis.ufl.edu
Subject: Workstation Symposium
IEEE TUTORIALS & DESKTOP COMPUTING/WORKSTATIONS SYMPOSIUM
Design - Management - Office - Personal
October 24-26, 1989
October. 24 -- TUTORIALS:
I. Complex Software Success
II. VHDL
III. Expert Systems
IV. Desktop Management Tools (including"MAC PROJECT")
V. PC-Based DBMs
VI. Practical Shells, Databases, & Spreadsheets
October 25-26 -- WORKSTATIONS SYMPOSIUM:
* Design Automation Key to Innovation & Productivity
* CAE Workstations for the System Designer
* The Office Workstation: Putting the Tools to Work
* Desktop computing for Managers and Administrators
* MUCH MORE ...
LOCATION: Johns Hopkins/Applied Physics Lab, Laurel, MD
MORE INFO CONTACT: Carol Daly, Tel (301) 792-5365
JHU/APL, Johns Hopkins Road
Laurel, MD 20707
------------------------------
Date: 6 Oct 1989 15:20:19-WET
Subject: SPICE
From: Julian Daley <jdaley%UXG.UMDS.LON.AC.UK@nervm.nerdc.ufl.edu>
To: simulation@BIKINI.CIS.UFL.EDU
As a new subscriber to the list I would like to ask some
questions about SPICE.
What is the latest version ?
Can I get the source (C or Fortran) ?
Does anyone have models for *real* MOSFET devices, diodes etc ?
Julian.
Guys's Hospital, London.
jdaley@uk.ac.lon.umds.uxg
------------------------------
Date: Sat, 7 Oct 89 20:22:25 -0700
From: liny@june.cs.washington.edu (Yi-Bing Lin)
Return-Path: <liny@june.cs.washington.edu>
To: fishwick@bikini.cis.ufl.edu
Subject: Optimality considerations of Time Warp
The following paper is accepted by 1990 Distributed Simulation
Conference. The technical report (TR 89-07-05) can be requested via
e-mail: tech-report@june.cs.washington.edu
OPTIMALITY CONSIDERATIONS OF "TIME WARP" PARALLEL SIMULATION
Yi-Bing Lin and Ed. Lazowska
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
ABSTRACT
The critical path in the event-precedence graph of a simulation
application is a lower bound of execution time for any conservative
parallel simulation. We refer to any parallel simulation that achieves
this time as a conservative optimal simulation. This paper derives a
relationship between a conservative optimal simulation and the ``Time
Warp'' or ``optimistic'' parallel simulation, and compares the
performance of the Time Warp simulation with Chandy-Misra conservative
simulation.
We show that Time Warp simulation with aggressive cancellation is not
conservative optimal in general, even under the assumption that the
operational overhead (such as state saving/restoration and global
virtual time calculation) is 0. We do, however, derive a sufficient
condition for Time Warp to be conservative optimal, and we show some
simulation problems that meet this condition. (We refer to such
simulations as Time Warp simulations that satisfy the sufficient
conservative optimal condition or TWSO.) We show that by applying the
lazy cancellation technique to TWSO, Time Warp always outperforms a
conservative optimal simulation. Given what we feel are equivalently
favorable assumptions for both the Time Warp approach and the
Chandy-Misra approach, we show that the Time Warp approach outperforms
the Chandy-Misra approach in every feedforward network simulation.
For feedback networks without lookahead, we show that in most cases
Time Warp outperforms Chandy-Misra, even assuming that deadlock
detection/recovery overhead is 0 in the Chandy-Misra simulation.
------------------------------
Date: Sat, 7 Oct 89 20:24:50 -0700
From: liny@june.cs.washington.edu (Yi-Bing Lin)
Return-Path: <liny@june.cs.washington.edu>
To: fishwick@bikini.cis.ufl.edu
Subject: Conservative parallel simulation for systems with no lookahead
The following paper is accepted by 1990 Distributed Simulation
Conference. The technical report (TR 89-07-07) can be requested via
e-mail: tech-report@june.cs.washington.edu
CONSERVATIVE PARALLEL SIMULATION FOR SYSTEMS WITH NO LOOKAHEAD PREDICTION
Yi-Bing Lin, Ed. Lazowska and Jean-Loup Baer
Department of Computer Science and Engineering
University of Washington
Seattle, WA 98195
ABSTRACT
The most popular conservative parallel simulation approach is the
Chandy-Misra approach, referred to here as the Chandy-Misra basic
scheme (CMB). When a CMB simulation includes a feedback loop (i.e.,
when a message may ``circulate'' in a loop of processes), there is the
probability that deadlocks will occur. To deal with deadlocks in
Chandy-Misra simulations, two modified algorithms, the Chandy-Misra
deadlock avoidance (DA) and deadlock recovery (DR) algorithms, have
been proposed. The DA algorithm is widely used for simulating systems
with lookahead prediction. (In a system with lookahead prediction,
each feedback loop of the system contains at least one logical process
p with some lookahead value d such that if a message arrives at p at
timestamp t, there is no output message scheduled by p with timestamp
less than t+d) The DR algorithm has been recognized, up to this point,
as the only conservative approach for simulating systems with no
lookahead prediction. This paper shows that a better approach for
simulating systems with no lookahead prediction is to reconfigure the
system such that there is no feedback loop, and use the CMB algorithm
to perform the simulation. We identify the overheads of this
approach, and devise both an analytical model and a number of
simulation experiments to estimate its performance.
------------------------------
END OF SIMULATION DIGEST
************************