reiher@amethyst.Jpl.Nasa.Gov (Peter Reiher) (06/08/89)
In article <PJIJ-2815-4574@nasamail> awilkinson@nasamail.nasa.gov (ALLEN R. WILKINSON) writes: >> [...] >> 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!) > > Jade Simulations International has developed a parallel simulation >language based on David Jefferson's TimeWarp JPL has an implementation of Time Warp, as well. Some of the things said about the Jade version seem a little misleading to me, so I'd like to clarify some basic principles that apply to both the Jade and JPL 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. . . . >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*. >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, 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. Well, not really. There is overhead associated with doing things out of order. First, there is the overhead of the rollback mechanism. Second, if the incorrectly processed event sent out messages, any overhead effort spent by the system on handling them is wasted work. They may cause congestion of communications links, they may cause queues to fill unnecessarily, they may cause secondary incorrect processing at other objects, etc. So, sometimes, from a performance point of view, you would be better off not doing this work optimistically. You might be better off doing no work at all, which is the underlying idea behind conservative mechanisms. Generally speaking, in fact, if you magically knew that a piece of work will be rolled back and discarded later, you would always be better off doing nothing than incorrectly doing that work. While incorrectly done work may prove expensive, our experience with Time Warp has shown that usually it is cheaper than running conservatively, for the class of applications we are interested in. We get good speedups despite rollbacks. In fact, as more nodes are added to a computation, we typically get both more speedup and more rollbacks. On the other hand, for a given number of nodes but different assignment of simulation objects to each node, typically the configuration that performs the least rollbacks gets better speedup. One tempting approach to speeding up Time Warp systems is to try to distinguish between "good optimism" and "bad optimism". In other words, try to avoid optimistically executing work that will eventually be rolled back. The problem is to separate out the bad optimism. We've found no good way of determining whether a given piece of work is likely or unlikely to be undone later. Any attempts we've made to limit the optimism in our system have slowed the system down, or, at best, not helped it. One more point - this article stated that programs written in Sim++ for a single processor will run, without change, on a parallel processor. That's probably true. However, unless the application was written with parallelism in mind, they may extract little or no extra speed from the extra nodes. Our project has seen several examples of such cases. Sim++ may be far more sophisticated than I think, but it would have to be very smart indeed to parallelize an inherently sequential program. My current reading of the situation in optimistic computation is that it has not provided the ideal of automatically extracting speedup from programs written for sequential machines, and is not likely to in the near future, if ever. Peter Reiher reiher@amethyst.jpl.nasa.gov (DO NOT send to reiher@amethyst.uucp) . . . cit-vax!elroy!jato!jade!reiher