Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!simulation From: simulation@uflorida.cis.ufl.edu (Moderator: Paul Fishwick) Newsgroups: comp.simulation Subject: SIMULATION DIGEST V11 N8 Message-ID: <21001@uflorida.cis.ufl.EDU> Date: 9 Oct 89 13:47:55 GMT Sender: fishwick@uflorida.cis.ufl.EDU Reply-To: simulation@uflorida.cis.ufl.edu Lines: 217 Approved: fishwick@uflorida.cis.ufl.edu 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: 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 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: 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: 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 ************************