Path: utzoo!attcan!uunet!cs.utexas.edu!tut.cis.ohio-state.edu!rutgers!gatech!hubcap!watmath!cpsc.ucalgary.ca!jsimellon From: watmath!cpsc.ucalgary.ca!jsimellon@uunet.UU.NET (Larry Mellon) Newsgroups: comp.parallel Subject: Re: A possible Linda application, Re: parallel make Summary: simulations via TimeWarp Keywords: parallel simulation, parallel make Message-ID: <5573@hubcap.clemson.edu> Date: 23 May 89 14:36:42 GMT Sender: fpst@hubcap.clemson.edu Lines: 91 Approved: parallel@hubcap.clemson.edu In article <5523@hubcap.clemson.edu>, ken@gvax.cs.cornell.edu (Ken Birman) writes: > In article <5512@hubcap.clemson.edu> landman@Sun.COM (Howard A. Landman) writes: > > >..... We are running massive gate-level simulations using > >simulator S on Sun workstations. We have two problems. (1) Our largest > >examples won't fit in 128 MB (maximum memory for the machines). (2) The > >simulation takes too long...... Is Linda a reasonable basis on which to > >build this system? > > While Linda probably IS a reasonable basis on which to build this > system, I want to suggest an alternative. > [...] > My group has developed a distributed computing technology called "ISIS" > that can be used to solve these kinds of problems, too. We believe that > ISIS has some important advantages over Linda in certain situations and > for certain architectures. (We are also convinced that Linda has > advantages over ISIS in some situations/architectures). > [...] > Offhand, I don't actually know of a 3rd approach that fits this > general framework, unless one includes Jefferson's time-warp work (you > simulation users will want to find out about that, too!) Hard to pass a lead-in like that! Jade Simulations International has developed a parallel simulation language based on David Jefferson's TimeWarp ('Virtual Time': ACM transactions on programming languages, 7(3), July 1885). This language, Sim++, is a superset of AT&T's C++, an object-oriented version of C. Sim++ allows you to develop and debug your simulations sequentially on a Sun workstation, using standard Sun tools, such as dbx, emacs, etc. Once your simulation is complete, it may be run in parallel across a network of Sun workstations or a high-speed multicomputer. No source code changes are required to execute in parallel. Currently, Sim++ runs on: - a single Sun3 workstation - a network of Sun3 workstations - the BBN Butterfly multicomputer (68020 based) - Meiko Transputer boards (RISC architecture) We are presently porting Sim++ to the Sun4 workstation, and several new multiprocessor systems. Jefferson's TimeWarp is intended to solve the problems of synchronizing simulation time across multiprocessors in the operating system, rather than in the user's code. It is best suited to descrete-event simulations; generally, the more compute time per event, the better your speedup. An incredibly brief description of TimeWarp follows. Basically, a simulation consists of entities which pass events between themselves, and take some action when an event is received. Each event has a time-stamp, which is when that event is to occur in simulation time. An entity acts on each event as soon as it is received, *with no attempt to verify that the event is in correct simulation time order*. This is called 'optimistic synchronization' by supporters, and 'silly' by opponents. Briefly, the rational is that if you verify the event order, you are wasting potential execution time and clogging your communication links with pointless queries. "But that's only true if the events happen to arrive in the correct order", the distractors cry in outrage. Well, true. That's why it's called optimistic, you see. If events arrive in order, we have a clear gain. If an entity happens to process an event at time X, then an event at time X-10 arrives, we simply 'rollback' the entity to a time before X-10, and start it up again. Thus, it will now process X-10, then X. "But, but, you've wasted processing time on event X!" stammer the distractors. Well, not really. If we had remained blocked until X-10 had arrived, that processing time was 'wasted' anyways. If fact, the worst case of TimeWarp, where all events arrive out of order, is exactly equivalent to the 'conservative' synchronization method; where entities remain blocked until event order has been verified. "And what is this 'rollback'?" you ask? That's a tricky one. While an entity is excuting, snapshots of it's state are taken from time to time. A snapshot consists of all static and automatic variables and events sent or received by the entity. A rollback consists of restoring an entity to one of it's previous states. Now, before everybody jumps on me, there are many things about TimeWarp I have not said, and details I have left vague. Please read Jefferson's paper; it is far better than anything I can write on the fly. I have other references as well, send email for a list. To people of the 'conservative mechanism' ilk: I concede there are applications better suited for conservative synchronization than TimeWarp, so please, no hate mail. I will go out on a limb and state that current research shows that optimistic beats out conservative in the general case. If you have any questions regarding Sim++ or TimeWarp, please contact me via email or telephone. Larry Mellon Jade Simulations International (403) 282-5711