CA2048140A1 - Unified distributed simulation process - Google Patents
Unified distributed simulation processInfo
- Publication number
- CA2048140A1 CA2048140A1 CA 2048140 CA2048140A CA2048140A1 CA 2048140 A1 CA2048140 A1 CA 2048140A1 CA 2048140 CA2048140 CA 2048140 CA 2048140 A CA2048140 A CA 2048140A CA 2048140 A1 CA2048140 A1 CA 2048140A1
- Authority
- CA
- Canada
- Prior art keywords
- simulation
- objects
- time
- gvt
- egvt
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Abandoned
Links
Landscapes
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
Abstract A computer simulation system and method for creating complex simulations for a large number of objects. Each object in the simulation is assigned a local virtual time (LVT) and a global virtual time (GVT) as well as being assigned a variable aggressiveness Ai, where 0 ? Ai? ?, and a variabls risk Ri where 0 ? Ri? ? , Ai is the number of time units an object is capable of looking ahead to define a receive window within which an object is capable of receiving and processing messages. Ri is the number of time units into the global future that an object is capable of sending messages to define a send window for each of the objects.
This provides a unified distribution simulation system that allows variable asynchronous message passing with the synchrony between objects being varied by adaptable aggressiveness Ai and risk Bi parameters for each object in the simulation with each parameter being adjusted depending on circumstances in the simulation. This results in a system which is more flexible and one that is able to take better advantage of available computing resources than those presently available.
This provides a unified distribution simulation system that allows variable asynchronous message passing with the synchrony between objects being varied by adaptable aggressiveness Ai and risk Bi parameters for each object in the simulation with each parameter being adjusted depending on circumstances in the simulation. This results in a system which is more flexible and one that is able to take better advantage of available computing resources than those presently available.
Description
2t `? ~
Field of the Invention The present invention relates to computer simulation algorithms with improvements which results in a more powerful environment for creating complex simulations and which is more flexible as well as being able to take better advantage of available computing resources.
Background o~ the Inventions Computer simulation is becoming an increasingly important computational tool. However, it is becoming more difficult to provide adequate formal specifications for experimental systems as their size and complexity increase. The component's interactions in larger and complex systems appear more random and complex with highly dynamic system topologies. In order to provide adequate simulations of these larger and complex systems simulation mechanisms must become more flexible and take better advantage of available computing resources.
In simulations, a model is a description of a real-world or a proposed system and can be expressed in different ways depending on its intended use. A model of a bank from the point of view of customer service, for example, would describe the behaviour of various queues and servers in the bank. However, a transaction bank model would model the bank as a series of transactions where each transaction must be processed atomically as in a real transaction system. The interactions in the service model are predominantly sequential with the services not being interrelated.
The transaction model, on the other hand, is a highly asynchronous distributed system which requires a detailed description of the :: ~ . . .
processing system's operation and concurrency control. Combining the two bank models into one type of simulation is difficult due to the dissimilar behaviour o~ the components. The simulation system which is best suited to the service model is not well suited to the transaction model and vice versa. Combining these models requires that one or the other is re-implemented in an inappropriate environment and subsequently reverified and revalidated. The costs of verification and validation increase rapidly as the quantity and complexity of models and their interactions rises~ The capability to combine behaviourally differ~nt models would lower cost by allowing more model reuse while reducing the requirement for reimplementation.
Time plays a significant role in almost all simulation systems, either directly or indirectly. The role of time may be anything from that of a simple history ordering mechanism (e.g.something happened at time T), to a constraining sequencer (e.g. event A must occur before event B) or to a proactive agent in the system (e.g. at time T some event occurs). The timing mechanisms used in simulation are of the utmost importance which determines what models can be simulated and the performance of the simulation as well as the models design and implementation.
Uniprocessor time maintenance ~e.g. time-and e~ent-driven simulation) is strai~htforward because the entire system is centralized and only one object can be simulated at any given time.
Time is implemented as a global variable in these systems which is unacceptable for distribution simulation. Distributed computing has become recognized as a good architecture for attacking large .
~ v . . l ~.~
computational problems since it offers high performance, flexibility and scaleability at a reasonable cost. However, distributed computing concepts cannot ~e immediately applied to the simulation of complex systems. Current simulation technology is either inadequate for modelling complex systems or cannot utilize the power of distributed computers.
A distributed simulation system must explicitly co-ordinate the advance of time in order to maintain temporal consistency between the components i.e. it must define how time is advanced when, according to the models, the time should be advanced. Time maintenance can be divided into two distinct tasks, (1) the movement of time and (2) the co-ordination of time movement. Each component in the system should specify its own method of synchronizing with the rest of the simulation in order to provide co-ordination of time advances betwean concurrent simulation components.
~ o distributed simulation algorithms that typify the state-of-the-art in distribution simulation are the Chandy-Misra (CM) simulation and Time Warp (TW) simulation. The term Chandy-Misra is used herein for convenience although that algorithm is theresult of several different groups and is described in the articles "Distributed simulation using a network of processors" in Computer Networks 3, North-Holland Publishing, pages 44-56 (1979) by J.K.
Peacock et al and "Asynchronous Distributed Simulation via a Sequence of Parallel Computations" in Communications of the ACM, 24(4) pages 198-205 in 1981, by K.M..Chandy and J. Misra. Time Warp algorithms are described in an article entitled "Fast '~: , : . :
. . ~
.: :-, :.
~, , ; .;.. .
. .
Concurrent Simulation Using the Time Warp Mechanism" in the Proceedings of the Conference on Distributed Simulation 1985, San Diego, pages 63 to 69 (January) by D.R. Jefferson et al in 1985 and in an article by D.R. Jefferson entitled "Virtual time" in ACM
Transactions on Programming Languages and Systems, 7(3), July, (1985). An article by D.R. Jefferson et al (1987) entitled "Distribut~d Simulation and the Time ~arp Operating Systems" in Operating Systems Review, 21(5), pages 77-93 further describe Time Warp algorithms.
Both CM and TW techniques use the same notion of local and global virtual time. The local virtual tima tLVT) of an object is defined as the time up to which that object has simulated. An object's LVT is 238, for example, if that object has completed all of the operations assigned to it up to time 238. A particular LVT
may be monotonic or non-monotonic depending on the time co-ordination technique used. The global virtual time (GVT) o~ a simulation is analogous to the LVT of a component. The GVT is the point in simulation time up to which al~ components have successfully simulated. In other words, the GVT at a particular point in-the simulation is equal to the minimum of all the LVTs in the system. It is said that some component M defines the GVT when that component M has an LVT which is equal to the GVT.
The Chandy-Misra (CM) simulation was the first distributed simulation and is a form of pessimistic simulation.
The simulation mechanism holds back processing because it assumes that components will communicate out of sequence. CM simulation can be viewed as a token passing mechanism in which an object with .:- . : : .
': : : ~
a token is free to communicate with any other object in the simulation while ~hose without tokens may only do local processing.
An object gets a token when it defines the GVT i. e. when its LVT
equals the GVT. More than one object can have a token since more than one object can define the GVT. When there are no more objects with tokens, the GVT is updated to be the minimum LVT of all objects in the simulation and the tokens are redistributed. The GVT is guaranteed, in this way, to equal the least LVT of all interacting objects in the simulation.
Synchronous message passing is used to co-ordinate concurrent components in CM simulations. Messages cannot be received until the receiver's LVT=GVT, i.e. the message's sender remains blocked until the receiver defines the GVT, which restriction guarantees that messages are received in the correct order. Forcing objects to wait for LVT=GVT can result in excessive time delays. However, since most objects interact with only a limited set of neighbors, a receiver need only wait to process a message until its neighbor's times are greater than the message times. This, requires that all components maintain lists of neighbors. The use of such lists, unfortunately, restricts the ability of the simulation system to model complex dynamic systems.
If the list is static, it will contain all possible neighbors and will force an object to do excessive synchronizations. Maintenance of dynamic neighbor lists is complicated and requires additional synchronization whenever the graph topology is changed.
The basic CM algorithm does not prevent simulation induced deadlock i.e. deadlock which is due solely to the .
- - :
:' ~$~
simulation process. Deadlock detection, avoidance and recovery is a difficult problem and has received a lot of attention in both the simulation and general distributed/concurrent computing literature.
These methods include null message passing, demand-driven null message passing and a detection-recovery scheme. The null message passing method is described by K.M. Chandy and J. Misra in an article " Distributed Simulation: A Case Study In Design And Verification Of Distributed Programs" in IEEE Transactions on Software Engineering, SE-5 pages 440-452 (1979). The demand-driven null message passing method is described by J. Misra in an article "Distributed Discrete-Event Simulation" in Computing Surveys, 18(1~, pages 39-65, March 1986. The detection-recovery scheme is described in an article "Asynchronous Distributed Simulation via a Sequence of Parallel Computations" in Communications of the AC~, 24(4), pages 198-205 (1981) by K.M. Chandy and J. Nisra and in a further article by J. Misra in 1983 entitled "Detecting Termination of Distributing Computations Using Markers" in the Proceedings of the 2nd ACM Principles of Distributed Computing, Montreal, pages 290 to 293.
The CN algorithm works best in tightly coupled simulations which are highly connected i.e. simulations in which ob;ects are highly synchronous. Communicating obj~cts in these type of systems are usually synchronized and seldom have to wait for their messages to be delivered. The performance of CM
simulations is bounded above by the critical path af concurrency present in the simulated model. It is not possible for events . .
. ::
.
: ~:
which are synchronous in the real system to be processed asynchronously in the CM simulation of that system.
Time Warp (TW) is sometimes referred to as optimistic . simulation and relies on the ability of an object to rollback its present state to that of some previous time. Objects using Time Warp, in contrast to Chandy-Misra, simulate and communicate ~reely with other components until they re~eive a message. An object receiving a message in Time Warp simulations must synchronize with the message sender. When the received message is from the receiver's future (i.e the message timestamp is greatar than the receiver's LVT), the receiver increases its LVT to the message timestamp value and processes the message. If that message is from the objects past, however, then the receiver must undo trollback) any processing it did or messages it sent between its current LVT
and the new message's time. This would initially give the impression that a simulation based on the concept of Time Warp may take nine steps forward only to then take eight steps back. The previously mentioned article "Fast Concurrent Simulation Using the Time Warp Mechanism" by Jefferson et al (1985~ takes the position that the time spent projecting an object's future is not really wasted since in other schemes, such as Chandy-Misra, the interaction would be blocked for synchronization and the simulation would not progress. In actual fact, only objects involved in that particular interaction will be bloc~ed and the processors simulating those objects will still be available to run the other ~-objects in the simulation. Time Warp is entirely free of simulation induced deadlock since all message passing is .: - . - : . . : , , :
:. -~, , . ' ! , ~
asynchronous. This simplifies algorithms and eliminates the overhead previously required in other systems in order to detect or avoid deadlosk. Time Warp is good for loosely coupled, highly asynchronous systems but is inefficient when the models have mixed time scales or diverse interaction behaviours.
The rollback process in TW simulations can be improved through the use of lazy cancellation in which antimessages are sent only when it is clear that the corresponding messages should never have been sent. A Ph.D. Dissertation by O. Berry at the University of Southern California, Los Angeles, CA in 1986 entitled "Performance Evaluation of the Time Warp Distributed Simulation Mechanism" proved that the performance of Time Warp using lazy cancellation is not bounded by the critical path of synchronization. This result is demonstrated in an article by O.
Berry et al presented at the Second International Conference on Computers and Applications in Beijing, China in June 1987 entitled "The potential speedup in the optimistic Time Warp mechanism for distributed simulation" (pages 694-698).
Simulations written using optimistic techniques, such as TW, are quite different from those written using pessimistic methods. Several systems have attempted to address the middle ground between optimism and pessimism but none have been fully successful up to present. P.F. Reynolds at the Proceedings of the 1988 Winter Simulation Conference in San Diego, CA on pages 325 to 332 (Dec. 1988) presented nine design variables which can be used to characterize current distributed simulation systems in an article entitled "A spectrum of options for parallel simulation".
-:~
These variables are Partitioning, Adaptability, Aggressiveness, Accuracy, Risk, Knowledge embedding, Knowledge dissemination, Knowledge acquisition and Synchrony. It is agreed with Reynolds that there is a range or spectrum of different possibilities and that it is worth considering points in this range which are between the two extremes of optimistic and pessimistic methods.
Furthermore, it is believed that transitions between points in this spectrum should be seamless and that components functioning at difrerent points should be compatible, i.e. optimistic and pessimistic simulation should be unified.
Only Risk and Aggressiveness of the nine variables are considered in a method according to the present invention along with a new variable Compatibility. Aggressiveness is the property of processing messages based on conditional knowledge, i.e.
relaxing the requirement that messages be processed in a strict monotonic order with respect to message times. Risk is passing messages which have been processed based on aggressiveness or inaccurate processing assumptions in a simulation component.
Compatibility is the ability of components in a simulation to have different bindings for their design variables e.g. one model can be aggressive while there are others in the simulation which are not.
Chandy-Misra simulations are non-aggressive while Time Warp simulations are maximally aggressive. These two simulations treat risk as a discrete variable with only one of two values, O or respectively~
Current technology is incapable of simulating dynamic, complex systems which contain a mixture of synchronous and ' ' ~
. . ~ ., . -i r ~
asynchronous components so ~hat simulationalists are, as a result,forced to work around the simulation tools in order to implement their models. However, much of this ef~ort could be avoided by unifying the simulation techniques by creating a system which is adaptable, which allows continuous and in~inite levels of aggressiveness and risk and which allows individual models to determine how they will interact. In addition, the simulation should include a sound model of concurrency and all models must be compatible.
It is an object of the present invention to create a tool for building logical, flexible, simulations which can be run efficiently on a distributed computer system~
A simulation system, according to the present invention, comprises assigning to each object in the simulation a local virtual time (LVT) and a global virtual time (C~VT) as well as assigning to each object a variable aggressiveness A; where O~ Aj~
A; being the nu~ber of time units an object is capable of looking ahead, and a variable risk Rj, where O 'RjC~O, Rj being the number of time units into the global future that an object is capable of sending messages. This will provide a unified distributed simulation system which allows variable asynchronous message passing, the synchrony between objects being varied by adaptable aggressiveness A; and risk Rj parameters.
The inventions will now be described in more detail with reference to the accompanying drawings in which:
Fig. 1 shows a message queue time window for a model in which aggressiveness A=O, -- 10 -- :
:~ :
:: : :
~d ~ 3 Fig. 2 shows a message queue time window for a model in which the aggressiveness A=30, Fig. 3 shows a message queue time window for a model in which the aggressiveness A=OO, Fig. 4 illustrates a concurrent meta-object structure implemPnted using actors along with their communications pattern and Fig. 5 illustrates the insertion of a duplicate element.
The Unified Distributed Simulation (UDS) algorithm according to the present invention is loosely based on the Time Warp algorithm. The UDS algorithm can consistently model both optimistic and pessimistic components as well as models with limited bidirectionality. UDS parameterizes each component's level of optimism by its aggressiveness Aj and risk Rj.
The aggressiveness Aj (O~Aj~) of a component Mj is the number of time units that the component Mj is capable of looking ahead. The range [GVT, GVT+Aj~ defines a receive window within which Mj is capable of receiving and processing messages.
Therefore, M; is responsible for rolling back any non-committed actions taken during this period i.e. simulation for times after GVT.
The risk Rj (O~R;~0c~ of a component Mj lS the number of time units into the global future Mj is capable of sending messages.
The range [GVT, GVT+R;] defines a send window within which Mj is capable of sending messages although it is up to the destination to determine if the message will be received.
:
`:
Each Mj has an aggressiveness Aj and risk Rj that can be varied depending on circumstances in the simulation. For instance, in a traffic system if a car M; enters a ferry it is synchronous at that time and the Aj goes to O until the ferry docks. After the ferry docks, the car can again enter the traffic system and the aggressiveness Aj increases depending on the arrangement of the traffic system and other cars in that system.
In the UDS algorithm, a model's processing capabilities are regulated by the size and position of its send and receive windows. Each model Mj is provided with a continuously updated GVT
estimate or EGVT(Mj) which defines the origin of its windows. The inequality EGVT~Mj)~GVT always holds.
The aggressiveness Aj and risk Rj parameters allow the UDS
algorithm to use variably asynchronous message passing. That is, the message <Tse~, T~rrive~ Mj, Ml>, Mj and Mj being the sender and receiver respectively, can only be sent if time Tse~ is in Mj's send window and received if time TarrjVe is in Mj's receive window.
Otherwise, Mj will block on either the send or receive of the message. This is illustrated in Figures 1 to 3 which show message queues for models with different sized time windows.
In Figures 1 to 3, the arrow indicates the next message to be read ~rom the queue. In these figures, the messages have 3 states i.e. processed (white), received (cross-hatched from left to right) and sender blocked (cross-hatched from right to left).
The component X in Fig. 1 has a local virtual time LVTX of 20, an EGVTX of 20 and aggressiveness AX=O. The EGVTX+Ax defines the time that a message can be received, up to 20 in Fig. 1, although r ~ 12 ~
:, ~J ~3 no messages shown have been processed since the LVTX is also 20 i.e.
the same as that of the lowest shown messages. Note that any EGVT
is always C GVT and that the GVT is equal to the minimum of all the LVT's in the system as previously mentioned.
The component Y in Fig. 2 has a LVTy of 24, an EGVTy of 18 and is provided with an aggressiveness Ay of 30 so that all messages with a time stamp less than EGVTy+Ay, which is 30+18=~8, can be received. Therefore, messages with time stamps of 19, 22 and 24 can all be received with the last received message not yet having been processed. The earlier received messages with time stamps of 19 and 22 have been processed. The message with a time stamp 49 is blocked and cannot be received by Y since this is larger than 48, the value of EGVTy+*. However this is due to the inaccuracy of EGVTy and the message with a time stamp 49 would be received if EGVYy~GVTy~20 so ~hat EGVTy~GVTy+~=20+30=50. Note that the number of messages processed in the projected future increases as the aggressiveness increases.
The component Z in Fig. 3 is provided with a LVTz of 87, and EGVT~ of 17 and an aggressiveness Az of c~o so that all messages can be received.
The UDS algorithm allows Aj and Rj to vary dynamically and has the property that as A; and Rj decrease, the required accuracy of EGVT (M;) increases. If EGVT(Mj) is sufficiently inaccurate, then it is possible that Mj's message queue will be erroneously empty and Mj will stop processing. Simulation induced deadlock can occur if this were to happen to all the models simultaneously.
However, if for some reason the simulation does deadlock, the .
GVTEstimator will generate an exact value for the GVT to resolve the deadlock.
The GVTEstimator is an actor that polls the components in the simulation for estimates of the current GVT and sets each component's EGVT to the minimum of these values. This technique is suitable since the UDS algorithm requires only that the EGVT be less than or equal to the real GVT. The accuracy of the GVTEstimator's result is inversely proportional to the amount of simulation which takes place during one round of polling. The simulation has the property that as the GVT estimate decreases in accuracy, more components will suspend processing resulting in that more processor time will be available to the GVTEstimator. These two properties balance each other and keep the simulation running at a reasonable rate while avoiding deadlock. If deadlock does occur, thsn the GVTEstimator is given exclusive use of the processors by default and will generate an exact value for the GVT
by checking all the components which will resolve the deadlock. It should be noted that the more optimistic a component is, the larger its time window and the less accurate the EGVT must be to keep the simulation running.
If at all times the origin of all time windows is equal to the GVT (e.g. EGVT(Mj)=GVT for all j) and there exists no messages~ <Tserld~ Tarrive~ MSOurce~Mde5t>~ such that Msource~Mdes~ a~d Tarrive~Tser,d~ Adest where Adest is the aggressiveness of the destination, then fatal simulation induced deadlock cannot occur.
Because the GVT is dynamic and distributed, the algorithm for calculating the EGVT cannot guarantee that EGVT(Mj)=GVT at all :.
times. In practice, it is enough that the EGVT algorithm be capable of calculating the exact GVT when deadlock occurs. In general, EGVT(Mj) can be inaccurate by as much as (GVT~Aj)-TarrjVe and messages at time TarrjVe will be received and processed by M;.
SmalltalX/ ~ has been used to implement the UDS
algorithm. In Smalltalk everything is an object and every object is an instance of some class which is also an object. Classes describe the structure and behaviour of their instances while the instances contain the data. An object's behaviour is the set of methods or procedures which the object can execute. Methods are invoked by sending a message containing the method's salector, the method name and any required arguments to an object. If the behaviour of the object receiving the message defines that method then the message is processed, otherwise an error occurs. Since messages are sent to objects rather than sending objects to procedures, a variable's class is irrelevant as long as it can understand the specified messa~e. Another important part of Smalltalk is the inheritance or subclassing mechanism. Subclasses inherit and refine the structure and behaviour of their superclasses. The structure of a subclass is the accumulation of the structures defined by itself and its superclasses while the behaviour of a subclass is given by the union of the methods defined by itself and its superclasses.
The UDS algorithm belongs to a class of computation Xnown as "speculative computation" which is a computation that is initiated before it is known that the result will be required.
Conversely, "mandatory computation" is computation which is known ' -' :
~' ~
to be required. Using speculation, idle processor time in non-speculative systems is used to compute possible future results.
Unified Distributed Simulation is a speculative algorithm in which the amount of speculation possible is proportional to the aggressiveness and risk of various objects in the simulation. The previously discussed Chandy-Misra simulation is non-speculative whereas Time Warp is fully speculative.
Speculative systems, lik~ the UDS alyorithm, falls into one of three categories. These are (1) algorithmic, (2) code-based and (3) system-based speculation. The present UDS system performs algorithmic speculation although code-based or system-based speculation could be used. Each object in the present ~DS
simulation is a separate algorithm which projects its own future based on the common data set provided by the other components.
Therefore, each algorithm speculates and contributes to the final result of the simulation. The main problem is that the data set is dynamic and all components have global side-effects. UDS can limit the number of side-effects by restricting the spread of speculation (i.e. reducing the risk) or limiting the initiation of speculation ti.e. reducing the aggressiveness). However, a reduction of either parameter will also reduce the potential for parallelism.
The Smalltalk implementation of UDS, called RIVAL is motivated by ideas from computational reflection and actor theory.
Computational reflection is the process of doin~ computation about computation. Typical computations model some real or abstract entity, for instance a database, which is called the application.
The application in a reflective system is t~e computation itself.
, : .
.
, ,,.:
In other words, reflection is the capability to look at the computation from the level of tha machine which is running it.
This capability can be used to dynamically modify the behaviour of the system. One system which has reflective capabilities is ABCL/R
which is described in an article "Reflection in an Object-Oriented Concurrent Language" by T. Watanabe et al in the Proceedings of ~OPSLA 88, San Diego, CA on pages 306-315 (Sept. 1988).
Actor theory is described by G. Agha et al in '~Concurrent Programming Using Actors"l Object-Oriented Concurrent Programming (Yonezawa and Tokoro eds.) from MIT Press, Cambridge, MA on pages 35 to 53 (1987). An actor is a Smalltalk object with additional mechanisms for multiprocessing and communications. The message passing protocol used is based on the send, receive, reply primitive set found in Harmony. The behaviourial similarities of actors to objects and the simplicity of their protocol results in a powerful programming environment which can be used to create an ABCL/R style model of concurrency. For the present case, an actor is a group of co-operating objects which f~mction independently of, and asynchronously to, the other actors in the system.
ABCL/R is a concurrent object-oriented language which supports the notion of meta-objects. For each object, A, there is a one-to-one mapping to a meta-object, ~A. That is, ~A describes A just as A describes some entity in the problem domain. A is called the "denotation" of ~A. Meta-objects are similar to Smalltalk classes in that they define both the struct~ral and computational aspects of their denotation. However, they differ in that A and ~ A execute in parallel and that there is a meta-' ~ tr~ r ~
object for each object. Therefore, ~ A can change the behaviour of A while A is executing. Because both A and ~A are objects, there also exists an ItA which is the meta-object for ~A. This infinite chain of meta-objects is similar to the infinite tower of interpreters found in 3 Lisp as described by J. des Rivieres et al in a report "The Implementation of Procedurally Reflective Languages" Report CSLI-84-9, Center for the Study of Language and Information, Stanford University, CA (1984). Level shifting between the interpreters is done automatically when a meta-object receives a message. Thus, reflective procedures for an object are implemented in its meta-object. The utility of computational reflection is demonstrated in the previously mentioned article entitled "Reflection in an Object-Oriented Concurrent Language" by Watenabe et al 88, in which they describe a simple implementation of Time Warp in ABCL/R is described. The entire mechanism is implemented by redefining, in the meta-object, the way an object receives messages.
Every component in a Rival simulation, the Smalltalk implementation of UDS, is an actor with Fig. 4 showing a concurrent meta-ob;ect structure implemented using actors. Fig. 4 shows two objects with their associated meta-objects and illustrates their communications patterns. Objects communicate by sending synchronous actor messages to each other's meta-objects and tha meta objects dictates how objects send and receive messages. A
single message from B to A requires three actor messages, one from B to ~ B, one from t B to ~A and one between ~ A and A.
- . .: : -.::
- ,: . :.
. , . .: .,.. :
:. :: - ~ : : :
- : : :: .-: :- :
Unlike fully reflective systems, Rivals reflective capabilities are limited to inter-object communication and thus a level shifting interpreter is not required. Components are highly reusable because each can define its own concurrent behaviour and external protocol. Models can be exchanged between simulations even if their internal definitions are vastly different.
The class hierarchy of the complete Rival system is shown below. Classes printed with æ~do~s are new and are required for actors while those in boldface implement the Unified Distributed lG Simulation system. All other classes are supplied by Smalltalk.
Object Collection . . .
Sorted Collection IndexedSortedCollection Process A~or GVTEstimator NetaObject SimulationO~ject SimulationMessage The GVTEstimator was discussed previously. The remaining classes in the class hierarchy specifically related to the UDS
algorithm will now be described in more detail.
The instance variables in SimulationMessge are:
and , , :
~ ~ `` `,'; .il ~.
~ . To interact in a simulation, objects send "request"
messages (i.e. SimulationMessages with ~ ) to each other. The ~ of a request is the time, local to the destination, at which processing of the request began. Similarly, the ~ ffl~ is when the destination finished processing the request. Accordingly, the start and end times are undefined if the request has not been processed. These time fields are used by components to d~tect if a rollback is required and, if so, the time to which they should rollback.
Instances of IndaxedSortedCollection (ISC) are used to implement the time-bounded infinite message queues in which request messages are stored in ascending ~ -order. An ISC's index points to the next request to be read. The protocol of the ISC
~à~ method is very important here. The algorithm used to inserk elements guarantees that when a duplicate element (e.g. a message with an ~r~iv~L~ the same as a message already in the queue) is added, it will be added after those elements to which it is equal.
This is illustrated in Fig. 5 which shows an example where a message E, having a timestamp 25, is added to a queue. The sorted position of message E is immediately following message B which also has a timestamp 25. This positioning is guaranteed by the algorithm. Note that the queue's index or next element has been moved to E, making it the next message in the queue. In this example, ~ ~ will return true.
Simulation Objects have the following instance variables:
and ~ . Each object in the simulation is modelled by an instance o~ a subclass of SimulationObject(SO~. A SimulationObjsct ~.
describes the domain specific behaviour of a particular component.
Each SimulationObject has an associated meta-object which is an instance of MetaObject. When the SimulationObject is ready to process a request, it invokes the ~ ~ ~ method defined by its MetaO~ject and processes the return request. If there are no requests the object is blocked, otherwise supplies the next requests.
SimulationObjects support the Restoration phase of rollback by maintaining the ~ . Whenever, its EGVT is updated, a SO garbage collects the ~ xand ensures that the ~ always contains an entry with timestamp equal to the EGVT. When a rollback is triggered, the SO restores itself from the snapshot with the latest timestamp less than or equal to the rollback tima.
In Rival, each SimulationObject has an associated MetaObject(MO) through which all messages are sent and received.
MO's are also responsible for garbage collection, maintenance of the EGVT, co-ordination of rollbacks and maintaining the receive and send windows. The following are the instance variables of MetaObject which are relevant to UDS, ~
~i~ and ~?~. The protocol for MetaObject which is of interest here is~
~`en?~`?~ ~ and ~x~ ~ x~
When a MetaObject, for instance "M", receives a request 'IR", its ;~ ~ ethod first checks if the ~ is within its receive window and, if it is, then "M" accepts "R" by sending the ~s.~.u. ~ essage to the request's sender. If the is not within M's receive window, then the sender is ~- , s ~
blocked until M's receive window advances to include "R", "M" then adding "R" to the ~ which is an instance of IndexSorted Collection . If when "R" is added, it is inserted before the next request in the queue (i.e., if ~ returns true) then l'RII is out of sequence and should have been received and processed earlier in simulation time. "M" must then rollback to the latest possible time for which "R" can be processed consistently. Note that this rollback time is the ,~,'"~,5~ of the previous request after the new request is added to the ~ ` ~ , not necessarily the of 'IR'l.
In the Cancellation phase of a rollback, MOs undo messages by sending an ~ message for each request in the ~Q~ which was sent after the rollback time. This may cause other components to rollback. The cascade of rollbacks, which may result, will terminate if the rollback of one component cannot cause a rollback of some other component to an earlier time. In other words, the rollback of some object, such as A, to 30 cannot cause any other object to rollback to a time earlier than 30. This termination of rollback is guaranteed and it is implicit in the UDS
algorithm. If lazy cancellation is being used then the requests to be undone are simply marked as cancelled and are undone, if required, at a later time.
The MetaObject method, ~` ~ , performs a blocking receive waiting for a message to enter the receive window.
Under normal conditions the MO returns the next available request but it returns a rollback request containing the rollback time if the MO has detected a rollback condition. The MO carries out the ,-, ` . : '' ,. . ~ `
cancellation phase while the SO is restoring its state. The object then Coasts Forward by rewinding the ~` ~ o the appropriate time and reprocessing the requests.
The MetaObject's ~ ~ protocol is used when SOs want to send reque~ts to other components. The reguest is first logged in the o~ and then it is sent immediately if the request's sendtime, i.e. the current lvt, fits into the send window.
Otherwise, the re~uest is marked as pending and is forwarded to the receiver when the send window advances to include the requast's send time.
A MetaObject's receive and send windows are kept up to date by the GVTEstimator~ The GVTEstimator supplies a new value of the EGVT and requests the MO's estimate of the new EGVT . A MO
calculates its estimate based on the elements in its ~ and the state of its associated SO. The MO then uses the new EGVT to move the receive window and accept more requests, unblocking their senders. It also moves the send window and sends any pending messages. Note that in general there will be at most one pending message because the sender must block until the message is accepted by the destination.
Many of these operations can be carried out in parallel since a SimulationObject and its MetaObject are concurrent. Note that even if the SO part of a component is blocked, the corresponding MetaObject is still available to send and receive messages and contribute to the estimate of the GVT.
An example of a simple simulation system whose component's interactions are diverse and non-deterministic is a : ~
traffic system which contains both highways and city streets. This particular traffic system model has the following basic properties:
(1) There are thousands of simple cars which require littls processor power to simulate.
Field of the Invention The present invention relates to computer simulation algorithms with improvements which results in a more powerful environment for creating complex simulations and which is more flexible as well as being able to take better advantage of available computing resources.
Background o~ the Inventions Computer simulation is becoming an increasingly important computational tool. However, it is becoming more difficult to provide adequate formal specifications for experimental systems as their size and complexity increase. The component's interactions in larger and complex systems appear more random and complex with highly dynamic system topologies. In order to provide adequate simulations of these larger and complex systems simulation mechanisms must become more flexible and take better advantage of available computing resources.
In simulations, a model is a description of a real-world or a proposed system and can be expressed in different ways depending on its intended use. A model of a bank from the point of view of customer service, for example, would describe the behaviour of various queues and servers in the bank. However, a transaction bank model would model the bank as a series of transactions where each transaction must be processed atomically as in a real transaction system. The interactions in the service model are predominantly sequential with the services not being interrelated.
The transaction model, on the other hand, is a highly asynchronous distributed system which requires a detailed description of the :: ~ . . .
processing system's operation and concurrency control. Combining the two bank models into one type of simulation is difficult due to the dissimilar behaviour o~ the components. The simulation system which is best suited to the service model is not well suited to the transaction model and vice versa. Combining these models requires that one or the other is re-implemented in an inappropriate environment and subsequently reverified and revalidated. The costs of verification and validation increase rapidly as the quantity and complexity of models and their interactions rises~ The capability to combine behaviourally differ~nt models would lower cost by allowing more model reuse while reducing the requirement for reimplementation.
Time plays a significant role in almost all simulation systems, either directly or indirectly. The role of time may be anything from that of a simple history ordering mechanism (e.g.something happened at time T), to a constraining sequencer (e.g. event A must occur before event B) or to a proactive agent in the system (e.g. at time T some event occurs). The timing mechanisms used in simulation are of the utmost importance which determines what models can be simulated and the performance of the simulation as well as the models design and implementation.
Uniprocessor time maintenance ~e.g. time-and e~ent-driven simulation) is strai~htforward because the entire system is centralized and only one object can be simulated at any given time.
Time is implemented as a global variable in these systems which is unacceptable for distribution simulation. Distributed computing has become recognized as a good architecture for attacking large .
~ v . . l ~.~
computational problems since it offers high performance, flexibility and scaleability at a reasonable cost. However, distributed computing concepts cannot ~e immediately applied to the simulation of complex systems. Current simulation technology is either inadequate for modelling complex systems or cannot utilize the power of distributed computers.
A distributed simulation system must explicitly co-ordinate the advance of time in order to maintain temporal consistency between the components i.e. it must define how time is advanced when, according to the models, the time should be advanced. Time maintenance can be divided into two distinct tasks, (1) the movement of time and (2) the co-ordination of time movement. Each component in the system should specify its own method of synchronizing with the rest of the simulation in order to provide co-ordination of time advances betwean concurrent simulation components.
~ o distributed simulation algorithms that typify the state-of-the-art in distribution simulation are the Chandy-Misra (CM) simulation and Time Warp (TW) simulation. The term Chandy-Misra is used herein for convenience although that algorithm is theresult of several different groups and is described in the articles "Distributed simulation using a network of processors" in Computer Networks 3, North-Holland Publishing, pages 44-56 (1979) by J.K.
Peacock et al and "Asynchronous Distributed Simulation via a Sequence of Parallel Computations" in Communications of the ACM, 24(4) pages 198-205 in 1981, by K.M..Chandy and J. Misra. Time Warp algorithms are described in an article entitled "Fast '~: , : . :
. . ~
.: :-, :.
~, , ; .;.. .
. .
Concurrent Simulation Using the Time Warp Mechanism" in the Proceedings of the Conference on Distributed Simulation 1985, San Diego, pages 63 to 69 (January) by D.R. Jefferson et al in 1985 and in an article by D.R. Jefferson entitled "Virtual time" in ACM
Transactions on Programming Languages and Systems, 7(3), July, (1985). An article by D.R. Jefferson et al (1987) entitled "Distribut~d Simulation and the Time ~arp Operating Systems" in Operating Systems Review, 21(5), pages 77-93 further describe Time Warp algorithms.
Both CM and TW techniques use the same notion of local and global virtual time. The local virtual tima tLVT) of an object is defined as the time up to which that object has simulated. An object's LVT is 238, for example, if that object has completed all of the operations assigned to it up to time 238. A particular LVT
may be monotonic or non-monotonic depending on the time co-ordination technique used. The global virtual time (GVT) o~ a simulation is analogous to the LVT of a component. The GVT is the point in simulation time up to which al~ components have successfully simulated. In other words, the GVT at a particular point in-the simulation is equal to the minimum of all the LVTs in the system. It is said that some component M defines the GVT when that component M has an LVT which is equal to the GVT.
The Chandy-Misra (CM) simulation was the first distributed simulation and is a form of pessimistic simulation.
The simulation mechanism holds back processing because it assumes that components will communicate out of sequence. CM simulation can be viewed as a token passing mechanism in which an object with .:- . : : .
': : : ~
a token is free to communicate with any other object in the simulation while ~hose without tokens may only do local processing.
An object gets a token when it defines the GVT i. e. when its LVT
equals the GVT. More than one object can have a token since more than one object can define the GVT. When there are no more objects with tokens, the GVT is updated to be the minimum LVT of all objects in the simulation and the tokens are redistributed. The GVT is guaranteed, in this way, to equal the least LVT of all interacting objects in the simulation.
Synchronous message passing is used to co-ordinate concurrent components in CM simulations. Messages cannot be received until the receiver's LVT=GVT, i.e. the message's sender remains blocked until the receiver defines the GVT, which restriction guarantees that messages are received in the correct order. Forcing objects to wait for LVT=GVT can result in excessive time delays. However, since most objects interact with only a limited set of neighbors, a receiver need only wait to process a message until its neighbor's times are greater than the message times. This, requires that all components maintain lists of neighbors. The use of such lists, unfortunately, restricts the ability of the simulation system to model complex dynamic systems.
If the list is static, it will contain all possible neighbors and will force an object to do excessive synchronizations. Maintenance of dynamic neighbor lists is complicated and requires additional synchronization whenever the graph topology is changed.
The basic CM algorithm does not prevent simulation induced deadlock i.e. deadlock which is due solely to the .
- - :
:' ~$~
simulation process. Deadlock detection, avoidance and recovery is a difficult problem and has received a lot of attention in both the simulation and general distributed/concurrent computing literature.
These methods include null message passing, demand-driven null message passing and a detection-recovery scheme. The null message passing method is described by K.M. Chandy and J. Misra in an article " Distributed Simulation: A Case Study In Design And Verification Of Distributed Programs" in IEEE Transactions on Software Engineering, SE-5 pages 440-452 (1979). The demand-driven null message passing method is described by J. Misra in an article "Distributed Discrete-Event Simulation" in Computing Surveys, 18(1~, pages 39-65, March 1986. The detection-recovery scheme is described in an article "Asynchronous Distributed Simulation via a Sequence of Parallel Computations" in Communications of the AC~, 24(4), pages 198-205 (1981) by K.M. Chandy and J. Nisra and in a further article by J. Misra in 1983 entitled "Detecting Termination of Distributing Computations Using Markers" in the Proceedings of the 2nd ACM Principles of Distributed Computing, Montreal, pages 290 to 293.
The CN algorithm works best in tightly coupled simulations which are highly connected i.e. simulations in which ob;ects are highly synchronous. Communicating obj~cts in these type of systems are usually synchronized and seldom have to wait for their messages to be delivered. The performance of CM
simulations is bounded above by the critical path af concurrency present in the simulated model. It is not possible for events . .
. ::
.
: ~:
which are synchronous in the real system to be processed asynchronously in the CM simulation of that system.
Time Warp (TW) is sometimes referred to as optimistic . simulation and relies on the ability of an object to rollback its present state to that of some previous time. Objects using Time Warp, in contrast to Chandy-Misra, simulate and communicate ~reely with other components until they re~eive a message. An object receiving a message in Time Warp simulations must synchronize with the message sender. When the received message is from the receiver's future (i.e the message timestamp is greatar than the receiver's LVT), the receiver increases its LVT to the message timestamp value and processes the message. If that message is from the objects past, however, then the receiver must undo trollback) any processing it did or messages it sent between its current LVT
and the new message's time. This would initially give the impression that a simulation based on the concept of Time Warp may take nine steps forward only to then take eight steps back. The previously mentioned article "Fast Concurrent Simulation Using the Time Warp Mechanism" by Jefferson et al (1985~ takes the position that the time spent projecting an object's future is not really wasted since in other schemes, such as Chandy-Misra, the interaction would be blocked for synchronization and the simulation would not progress. In actual fact, only objects involved in that particular interaction will be bloc~ed and the processors simulating those objects will still be available to run the other ~-objects in the simulation. Time Warp is entirely free of simulation induced deadlock since all message passing is .: - . - : . . : , , :
:. -~, , . ' ! , ~
asynchronous. This simplifies algorithms and eliminates the overhead previously required in other systems in order to detect or avoid deadlosk. Time Warp is good for loosely coupled, highly asynchronous systems but is inefficient when the models have mixed time scales or diverse interaction behaviours.
The rollback process in TW simulations can be improved through the use of lazy cancellation in which antimessages are sent only when it is clear that the corresponding messages should never have been sent. A Ph.D. Dissertation by O. Berry at the University of Southern California, Los Angeles, CA in 1986 entitled "Performance Evaluation of the Time Warp Distributed Simulation Mechanism" proved that the performance of Time Warp using lazy cancellation is not bounded by the critical path of synchronization. This result is demonstrated in an article by O.
Berry et al presented at the Second International Conference on Computers and Applications in Beijing, China in June 1987 entitled "The potential speedup in the optimistic Time Warp mechanism for distributed simulation" (pages 694-698).
Simulations written using optimistic techniques, such as TW, are quite different from those written using pessimistic methods. Several systems have attempted to address the middle ground between optimism and pessimism but none have been fully successful up to present. P.F. Reynolds at the Proceedings of the 1988 Winter Simulation Conference in San Diego, CA on pages 325 to 332 (Dec. 1988) presented nine design variables which can be used to characterize current distributed simulation systems in an article entitled "A spectrum of options for parallel simulation".
-:~
These variables are Partitioning, Adaptability, Aggressiveness, Accuracy, Risk, Knowledge embedding, Knowledge dissemination, Knowledge acquisition and Synchrony. It is agreed with Reynolds that there is a range or spectrum of different possibilities and that it is worth considering points in this range which are between the two extremes of optimistic and pessimistic methods.
Furthermore, it is believed that transitions between points in this spectrum should be seamless and that components functioning at difrerent points should be compatible, i.e. optimistic and pessimistic simulation should be unified.
Only Risk and Aggressiveness of the nine variables are considered in a method according to the present invention along with a new variable Compatibility. Aggressiveness is the property of processing messages based on conditional knowledge, i.e.
relaxing the requirement that messages be processed in a strict monotonic order with respect to message times. Risk is passing messages which have been processed based on aggressiveness or inaccurate processing assumptions in a simulation component.
Compatibility is the ability of components in a simulation to have different bindings for their design variables e.g. one model can be aggressive while there are others in the simulation which are not.
Chandy-Misra simulations are non-aggressive while Time Warp simulations are maximally aggressive. These two simulations treat risk as a discrete variable with only one of two values, O or respectively~
Current technology is incapable of simulating dynamic, complex systems which contain a mixture of synchronous and ' ' ~
. . ~ ., . -i r ~
asynchronous components so ~hat simulationalists are, as a result,forced to work around the simulation tools in order to implement their models. However, much of this ef~ort could be avoided by unifying the simulation techniques by creating a system which is adaptable, which allows continuous and in~inite levels of aggressiveness and risk and which allows individual models to determine how they will interact. In addition, the simulation should include a sound model of concurrency and all models must be compatible.
It is an object of the present invention to create a tool for building logical, flexible, simulations which can be run efficiently on a distributed computer system~
A simulation system, according to the present invention, comprises assigning to each object in the simulation a local virtual time (LVT) and a global virtual time (C~VT) as well as assigning to each object a variable aggressiveness A; where O~ Aj~
A; being the nu~ber of time units an object is capable of looking ahead, and a variable risk Rj, where O 'RjC~O, Rj being the number of time units into the global future that an object is capable of sending messages. This will provide a unified distributed simulation system which allows variable asynchronous message passing, the synchrony between objects being varied by adaptable aggressiveness A; and risk Rj parameters.
The inventions will now be described in more detail with reference to the accompanying drawings in which:
Fig. 1 shows a message queue time window for a model in which aggressiveness A=O, -- 10 -- :
:~ :
:: : :
~d ~ 3 Fig. 2 shows a message queue time window for a model in which the aggressiveness A=30, Fig. 3 shows a message queue time window for a model in which the aggressiveness A=OO, Fig. 4 illustrates a concurrent meta-object structure implemPnted using actors along with their communications pattern and Fig. 5 illustrates the insertion of a duplicate element.
The Unified Distributed Simulation (UDS) algorithm according to the present invention is loosely based on the Time Warp algorithm. The UDS algorithm can consistently model both optimistic and pessimistic components as well as models with limited bidirectionality. UDS parameterizes each component's level of optimism by its aggressiveness Aj and risk Rj.
The aggressiveness Aj (O~Aj~) of a component Mj is the number of time units that the component Mj is capable of looking ahead. The range [GVT, GVT+Aj~ defines a receive window within which Mj is capable of receiving and processing messages.
Therefore, M; is responsible for rolling back any non-committed actions taken during this period i.e. simulation for times after GVT.
The risk Rj (O~R;~0c~ of a component Mj lS the number of time units into the global future Mj is capable of sending messages.
The range [GVT, GVT+R;] defines a send window within which Mj is capable of sending messages although it is up to the destination to determine if the message will be received.
:
`:
Each Mj has an aggressiveness Aj and risk Rj that can be varied depending on circumstances in the simulation. For instance, in a traffic system if a car M; enters a ferry it is synchronous at that time and the Aj goes to O until the ferry docks. After the ferry docks, the car can again enter the traffic system and the aggressiveness Aj increases depending on the arrangement of the traffic system and other cars in that system.
In the UDS algorithm, a model's processing capabilities are regulated by the size and position of its send and receive windows. Each model Mj is provided with a continuously updated GVT
estimate or EGVT(Mj) which defines the origin of its windows. The inequality EGVT~Mj)~GVT always holds.
The aggressiveness Aj and risk Rj parameters allow the UDS
algorithm to use variably asynchronous message passing. That is, the message <Tse~, T~rrive~ Mj, Ml>, Mj and Mj being the sender and receiver respectively, can only be sent if time Tse~ is in Mj's send window and received if time TarrjVe is in Mj's receive window.
Otherwise, Mj will block on either the send or receive of the message. This is illustrated in Figures 1 to 3 which show message queues for models with different sized time windows.
In Figures 1 to 3, the arrow indicates the next message to be read ~rom the queue. In these figures, the messages have 3 states i.e. processed (white), received (cross-hatched from left to right) and sender blocked (cross-hatched from right to left).
The component X in Fig. 1 has a local virtual time LVTX of 20, an EGVTX of 20 and aggressiveness AX=O. The EGVTX+Ax defines the time that a message can be received, up to 20 in Fig. 1, although r ~ 12 ~
:, ~J ~3 no messages shown have been processed since the LVTX is also 20 i.e.
the same as that of the lowest shown messages. Note that any EGVT
is always C GVT and that the GVT is equal to the minimum of all the LVT's in the system as previously mentioned.
The component Y in Fig. 2 has a LVTy of 24, an EGVTy of 18 and is provided with an aggressiveness Ay of 30 so that all messages with a time stamp less than EGVTy+Ay, which is 30+18=~8, can be received. Therefore, messages with time stamps of 19, 22 and 24 can all be received with the last received message not yet having been processed. The earlier received messages with time stamps of 19 and 22 have been processed. The message with a time stamp 49 is blocked and cannot be received by Y since this is larger than 48, the value of EGVTy+*. However this is due to the inaccuracy of EGVTy and the message with a time stamp 49 would be received if EGVYy~GVTy~20 so ~hat EGVTy~GVTy+~=20+30=50. Note that the number of messages processed in the projected future increases as the aggressiveness increases.
The component Z in Fig. 3 is provided with a LVTz of 87, and EGVT~ of 17 and an aggressiveness Az of c~o so that all messages can be received.
The UDS algorithm allows Aj and Rj to vary dynamically and has the property that as A; and Rj decrease, the required accuracy of EGVT (M;) increases. If EGVT(Mj) is sufficiently inaccurate, then it is possible that Mj's message queue will be erroneously empty and Mj will stop processing. Simulation induced deadlock can occur if this were to happen to all the models simultaneously.
However, if for some reason the simulation does deadlock, the .
GVTEstimator will generate an exact value for the GVT to resolve the deadlock.
The GVTEstimator is an actor that polls the components in the simulation for estimates of the current GVT and sets each component's EGVT to the minimum of these values. This technique is suitable since the UDS algorithm requires only that the EGVT be less than or equal to the real GVT. The accuracy of the GVTEstimator's result is inversely proportional to the amount of simulation which takes place during one round of polling. The simulation has the property that as the GVT estimate decreases in accuracy, more components will suspend processing resulting in that more processor time will be available to the GVTEstimator. These two properties balance each other and keep the simulation running at a reasonable rate while avoiding deadlock. If deadlock does occur, thsn the GVTEstimator is given exclusive use of the processors by default and will generate an exact value for the GVT
by checking all the components which will resolve the deadlock. It should be noted that the more optimistic a component is, the larger its time window and the less accurate the EGVT must be to keep the simulation running.
If at all times the origin of all time windows is equal to the GVT (e.g. EGVT(Mj)=GVT for all j) and there exists no messages~ <Tserld~ Tarrive~ MSOurce~Mde5t>~ such that Msource~Mdes~ a~d Tarrive~Tser,d~ Adest where Adest is the aggressiveness of the destination, then fatal simulation induced deadlock cannot occur.
Because the GVT is dynamic and distributed, the algorithm for calculating the EGVT cannot guarantee that EGVT(Mj)=GVT at all :.
times. In practice, it is enough that the EGVT algorithm be capable of calculating the exact GVT when deadlock occurs. In general, EGVT(Mj) can be inaccurate by as much as (GVT~Aj)-TarrjVe and messages at time TarrjVe will be received and processed by M;.
SmalltalX/ ~ has been used to implement the UDS
algorithm. In Smalltalk everything is an object and every object is an instance of some class which is also an object. Classes describe the structure and behaviour of their instances while the instances contain the data. An object's behaviour is the set of methods or procedures which the object can execute. Methods are invoked by sending a message containing the method's salector, the method name and any required arguments to an object. If the behaviour of the object receiving the message defines that method then the message is processed, otherwise an error occurs. Since messages are sent to objects rather than sending objects to procedures, a variable's class is irrelevant as long as it can understand the specified messa~e. Another important part of Smalltalk is the inheritance or subclassing mechanism. Subclasses inherit and refine the structure and behaviour of their superclasses. The structure of a subclass is the accumulation of the structures defined by itself and its superclasses while the behaviour of a subclass is given by the union of the methods defined by itself and its superclasses.
The UDS algorithm belongs to a class of computation Xnown as "speculative computation" which is a computation that is initiated before it is known that the result will be required.
Conversely, "mandatory computation" is computation which is known ' -' :
~' ~
to be required. Using speculation, idle processor time in non-speculative systems is used to compute possible future results.
Unified Distributed Simulation is a speculative algorithm in which the amount of speculation possible is proportional to the aggressiveness and risk of various objects in the simulation. The previously discussed Chandy-Misra simulation is non-speculative whereas Time Warp is fully speculative.
Speculative systems, lik~ the UDS alyorithm, falls into one of three categories. These are (1) algorithmic, (2) code-based and (3) system-based speculation. The present UDS system performs algorithmic speculation although code-based or system-based speculation could be used. Each object in the present ~DS
simulation is a separate algorithm which projects its own future based on the common data set provided by the other components.
Therefore, each algorithm speculates and contributes to the final result of the simulation. The main problem is that the data set is dynamic and all components have global side-effects. UDS can limit the number of side-effects by restricting the spread of speculation (i.e. reducing the risk) or limiting the initiation of speculation ti.e. reducing the aggressiveness). However, a reduction of either parameter will also reduce the potential for parallelism.
The Smalltalk implementation of UDS, called RIVAL is motivated by ideas from computational reflection and actor theory.
Computational reflection is the process of doin~ computation about computation. Typical computations model some real or abstract entity, for instance a database, which is called the application.
The application in a reflective system is t~e computation itself.
, : .
.
, ,,.:
In other words, reflection is the capability to look at the computation from the level of tha machine which is running it.
This capability can be used to dynamically modify the behaviour of the system. One system which has reflective capabilities is ABCL/R
which is described in an article "Reflection in an Object-Oriented Concurrent Language" by T. Watanabe et al in the Proceedings of ~OPSLA 88, San Diego, CA on pages 306-315 (Sept. 1988).
Actor theory is described by G. Agha et al in '~Concurrent Programming Using Actors"l Object-Oriented Concurrent Programming (Yonezawa and Tokoro eds.) from MIT Press, Cambridge, MA on pages 35 to 53 (1987). An actor is a Smalltalk object with additional mechanisms for multiprocessing and communications. The message passing protocol used is based on the send, receive, reply primitive set found in Harmony. The behaviourial similarities of actors to objects and the simplicity of their protocol results in a powerful programming environment which can be used to create an ABCL/R style model of concurrency. For the present case, an actor is a group of co-operating objects which f~mction independently of, and asynchronously to, the other actors in the system.
ABCL/R is a concurrent object-oriented language which supports the notion of meta-objects. For each object, A, there is a one-to-one mapping to a meta-object, ~A. That is, ~A describes A just as A describes some entity in the problem domain. A is called the "denotation" of ~A. Meta-objects are similar to Smalltalk classes in that they define both the struct~ral and computational aspects of their denotation. However, they differ in that A and ~ A execute in parallel and that there is a meta-' ~ tr~ r ~
object for each object. Therefore, ~ A can change the behaviour of A while A is executing. Because both A and ~A are objects, there also exists an ItA which is the meta-object for ~A. This infinite chain of meta-objects is similar to the infinite tower of interpreters found in 3 Lisp as described by J. des Rivieres et al in a report "The Implementation of Procedurally Reflective Languages" Report CSLI-84-9, Center for the Study of Language and Information, Stanford University, CA (1984). Level shifting between the interpreters is done automatically when a meta-object receives a message. Thus, reflective procedures for an object are implemented in its meta-object. The utility of computational reflection is demonstrated in the previously mentioned article entitled "Reflection in an Object-Oriented Concurrent Language" by Watenabe et al 88, in which they describe a simple implementation of Time Warp in ABCL/R is described. The entire mechanism is implemented by redefining, in the meta-object, the way an object receives messages.
Every component in a Rival simulation, the Smalltalk implementation of UDS, is an actor with Fig. 4 showing a concurrent meta-ob;ect structure implemented using actors. Fig. 4 shows two objects with their associated meta-objects and illustrates their communications patterns. Objects communicate by sending synchronous actor messages to each other's meta-objects and tha meta objects dictates how objects send and receive messages. A
single message from B to A requires three actor messages, one from B to ~ B, one from t B to ~A and one between ~ A and A.
- . .: : -.::
- ,: . :.
. , . .: .,.. :
:. :: - ~ : : :
- : : :: .-: :- :
Unlike fully reflective systems, Rivals reflective capabilities are limited to inter-object communication and thus a level shifting interpreter is not required. Components are highly reusable because each can define its own concurrent behaviour and external protocol. Models can be exchanged between simulations even if their internal definitions are vastly different.
The class hierarchy of the complete Rival system is shown below. Classes printed with æ~do~s are new and are required for actors while those in boldface implement the Unified Distributed lG Simulation system. All other classes are supplied by Smalltalk.
Object Collection . . .
Sorted Collection IndexedSortedCollection Process A~or GVTEstimator NetaObject SimulationO~ject SimulationMessage The GVTEstimator was discussed previously. The remaining classes in the class hierarchy specifically related to the UDS
algorithm will now be described in more detail.
The instance variables in SimulationMessge are:
and , , :
~ ~ `` `,'; .il ~.
~ . To interact in a simulation, objects send "request"
messages (i.e. SimulationMessages with ~ ) to each other. The ~ of a request is the time, local to the destination, at which processing of the request began. Similarly, the ~ ffl~ is when the destination finished processing the request. Accordingly, the start and end times are undefined if the request has not been processed. These time fields are used by components to d~tect if a rollback is required and, if so, the time to which they should rollback.
Instances of IndaxedSortedCollection (ISC) are used to implement the time-bounded infinite message queues in which request messages are stored in ascending ~ -order. An ISC's index points to the next request to be read. The protocol of the ISC
~à~ method is very important here. The algorithm used to inserk elements guarantees that when a duplicate element (e.g. a message with an ~r~iv~L~ the same as a message already in the queue) is added, it will be added after those elements to which it is equal.
This is illustrated in Fig. 5 which shows an example where a message E, having a timestamp 25, is added to a queue. The sorted position of message E is immediately following message B which also has a timestamp 25. This positioning is guaranteed by the algorithm. Note that the queue's index or next element has been moved to E, making it the next message in the queue. In this example, ~ ~ will return true.
Simulation Objects have the following instance variables:
and ~ . Each object in the simulation is modelled by an instance o~ a subclass of SimulationObject(SO~. A SimulationObjsct ~.
describes the domain specific behaviour of a particular component.
Each SimulationObject has an associated meta-object which is an instance of MetaObject. When the SimulationObject is ready to process a request, it invokes the ~ ~ ~ method defined by its MetaO~ject and processes the return request. If there are no requests the object is blocked, otherwise supplies the next requests.
SimulationObjects support the Restoration phase of rollback by maintaining the ~ . Whenever, its EGVT is updated, a SO garbage collects the ~ xand ensures that the ~ always contains an entry with timestamp equal to the EGVT. When a rollback is triggered, the SO restores itself from the snapshot with the latest timestamp less than or equal to the rollback tima.
In Rival, each SimulationObject has an associated MetaObject(MO) through which all messages are sent and received.
MO's are also responsible for garbage collection, maintenance of the EGVT, co-ordination of rollbacks and maintaining the receive and send windows. The following are the instance variables of MetaObject which are relevant to UDS, ~
~i~ and ~?~. The protocol for MetaObject which is of interest here is~
~`en?~`?~ ~ and ~x~ ~ x~
When a MetaObject, for instance "M", receives a request 'IR", its ;~ ~ ethod first checks if the ~ is within its receive window and, if it is, then "M" accepts "R" by sending the ~s.~.u. ~ essage to the request's sender. If the is not within M's receive window, then the sender is ~- , s ~
blocked until M's receive window advances to include "R", "M" then adding "R" to the ~ which is an instance of IndexSorted Collection . If when "R" is added, it is inserted before the next request in the queue (i.e., if ~ returns true) then l'RII is out of sequence and should have been received and processed earlier in simulation time. "M" must then rollback to the latest possible time for which "R" can be processed consistently. Note that this rollback time is the ,~,'"~,5~ of the previous request after the new request is added to the ~ ` ~ , not necessarily the of 'IR'l.
In the Cancellation phase of a rollback, MOs undo messages by sending an ~ message for each request in the ~Q~ which was sent after the rollback time. This may cause other components to rollback. The cascade of rollbacks, which may result, will terminate if the rollback of one component cannot cause a rollback of some other component to an earlier time. In other words, the rollback of some object, such as A, to 30 cannot cause any other object to rollback to a time earlier than 30. This termination of rollback is guaranteed and it is implicit in the UDS
algorithm. If lazy cancellation is being used then the requests to be undone are simply marked as cancelled and are undone, if required, at a later time.
The MetaObject method, ~` ~ , performs a blocking receive waiting for a message to enter the receive window.
Under normal conditions the MO returns the next available request but it returns a rollback request containing the rollback time if the MO has detected a rollback condition. The MO carries out the ,-, ` . : '' ,. . ~ `
cancellation phase while the SO is restoring its state. The object then Coasts Forward by rewinding the ~` ~ o the appropriate time and reprocessing the requests.
The MetaObject's ~ ~ protocol is used when SOs want to send reque~ts to other components. The reguest is first logged in the o~ and then it is sent immediately if the request's sendtime, i.e. the current lvt, fits into the send window.
Otherwise, the re~uest is marked as pending and is forwarded to the receiver when the send window advances to include the requast's send time.
A MetaObject's receive and send windows are kept up to date by the GVTEstimator~ The GVTEstimator supplies a new value of the EGVT and requests the MO's estimate of the new EGVT . A MO
calculates its estimate based on the elements in its ~ and the state of its associated SO. The MO then uses the new EGVT to move the receive window and accept more requests, unblocking their senders. It also moves the send window and sends any pending messages. Note that in general there will be at most one pending message because the sender must block until the message is accepted by the destination.
Many of these operations can be carried out in parallel since a SimulationObject and its MetaObject are concurrent. Note that even if the SO part of a component is blocked, the corresponding MetaObject is still available to send and receive messages and contribute to the estimate of the GVT.
An example of a simple simulation system whose component's interactions are diverse and non-deterministic is a : ~
traffic system which contains both highways and city streets. This particular traffic system model has the following basic properties:
(1) There are thousands of simple cars which require littls processor power to simulate.
(2) The roads cross at intersections which can contain at most one car while allowing cars to pass through the intersection in a first-in first-out (FIFO) order. The intersections synchronize cars, as a result, since one car is forced to wait to enter an intersection when two cars att~mpt to enter that intersection at the same time. Cars can enter an intersection through one side and leave through any of the other sides i.e. U-turns are not permitted.
(3) There are many intersections in the cities and few on the highways.
(4) Traffic may backup from one intersection into another causing the intersections to interact.
(5) A number of the intersections may contain crosswalks which form a special kind of intersection that can contain both cars and pedestrians, but not both at the same time. Cars cannot enter a crosswalk occupied by pedestrians and pedestrians have entrance priority over cars. Furthermore, any number of pedestrians may enter a crosswalk asynchronously and occupy it for varying amounts of time.
This type of traffic system has many different re~uirements for component interaction. Cars and pedestrians are asynchronous whereas intersections and road segments are syn~hronous. The amount of synchronous behaviour will therefore - - , - . -: , - , ~ ..
;
::
2 ~ Ji increase as the density of intersections increases. There are, as a result, pockets of synchrony (e.g. intersections containing cars) within the city wherein each pocket interacts asynchronously with its neighbor.
The bulk of the concurrency in the system will be lost using a Chandy-Misra simulation. Intersections will dominate any CM simulation because they define the synchronous behaviour. CM is efficient for modelling a single intersection but will require each car to be synchronized with all intersections in a full system model resulting in cars in the busiest intersections holding back all cars, even those on highways. This results in a highly connected system graph and high overhead if null message passing is used. CM is not capable of exploiting the concurrency between distinct heavy traffic routes within the city and between cars in the city and those on the highways.
A Time Warp simulation of the traffic system is better able to take advantage of the available system wide concurrency but will perform poorly for intersections. Cars will become more and more synchronized as the number of intersections increase and the rollbacks more expensive if a TW simulation is used. This is illustrated, for example, when a late pedestrian steps into a crosswalk in a city with a large number of intersections. The crosswalk and all cars passing through it would then have to be rolled back. Those cars will likely have gone on to interact with other intersections in the city and thus more cars so that the rollback's cascade will be widespread. The cost of performing rollbacks can easily dominate the relatively low cost of simulating .
-~
f/ 1 `: , _ . ~
a car. A global multiprocessor load balancing scheme would improve performance by ensuring that only the components with the least LVTs are run by each processor. However, such a scheme does not exist at present and, even if it did, it would be difficult to implement efficiently on top of TW because it would require global knowledge and/or reflective capabilities.
This traffic system model serves to illustrate the deficiencies of current technologies such as CM and TW simulations.
The main difficulty is that the components behave both synchronously and asynchronously depending on where they are in the traffic system. However, Rival (a UDS system according to the present invention) can eliminate some of these problems in a simulation. Lowering a car's risk and aggressiveness in the city will limit the number and extent of rollbacks. Increasing a car's aggressiveness and risk on highways will take advantage of the available parallelism. Both of these last two features can be accomplished using a Unified Distribution Simulation (UDS) system as described with respect to the present invention. The incorporation of reflective capabilities allows models to adapt to changing requirements and resources.
The traffic system example is a simplistic model but it serves to illustrate the usefulness of variable synchronism.
~nitial runs of that example has indicated that varying the risk and aggressiveness of cars has a substantial effect on the behaviour of the simulation e.g. rollbacks. This indicates that the UDS algorithm is capable of extracting significant parallelism from system models.
- . ~
Various modifications may be made to the preferred embodiment without departing from the spirit and scope of the invention as defined in the appended claims.
:.
,:
This type of traffic system has many different re~uirements for component interaction. Cars and pedestrians are asynchronous whereas intersections and road segments are syn~hronous. The amount of synchronous behaviour will therefore - - , - . -: , - , ~ ..
;
::
2 ~ Ji increase as the density of intersections increases. There are, as a result, pockets of synchrony (e.g. intersections containing cars) within the city wherein each pocket interacts asynchronously with its neighbor.
The bulk of the concurrency in the system will be lost using a Chandy-Misra simulation. Intersections will dominate any CM simulation because they define the synchronous behaviour. CM is efficient for modelling a single intersection but will require each car to be synchronized with all intersections in a full system model resulting in cars in the busiest intersections holding back all cars, even those on highways. This results in a highly connected system graph and high overhead if null message passing is used. CM is not capable of exploiting the concurrency between distinct heavy traffic routes within the city and between cars in the city and those on the highways.
A Time Warp simulation of the traffic system is better able to take advantage of the available system wide concurrency but will perform poorly for intersections. Cars will become more and more synchronized as the number of intersections increase and the rollbacks more expensive if a TW simulation is used. This is illustrated, for example, when a late pedestrian steps into a crosswalk in a city with a large number of intersections. The crosswalk and all cars passing through it would then have to be rolled back. Those cars will likely have gone on to interact with other intersections in the city and thus more cars so that the rollback's cascade will be widespread. The cost of performing rollbacks can easily dominate the relatively low cost of simulating .
-~
f/ 1 `: , _ . ~
a car. A global multiprocessor load balancing scheme would improve performance by ensuring that only the components with the least LVTs are run by each processor. However, such a scheme does not exist at present and, even if it did, it would be difficult to implement efficiently on top of TW because it would require global knowledge and/or reflective capabilities.
This traffic system model serves to illustrate the deficiencies of current technologies such as CM and TW simulations.
The main difficulty is that the components behave both synchronously and asynchronously depending on where they are in the traffic system. However, Rival (a UDS system according to the present invention) can eliminate some of these problems in a simulation. Lowering a car's risk and aggressiveness in the city will limit the number and extent of rollbacks. Increasing a car's aggressiveness and risk on highways will take advantage of the available parallelism. Both of these last two features can be accomplished using a Unified Distribution Simulation (UDS) system as described with respect to the present invention. The incorporation of reflective capabilities allows models to adapt to changing requirements and resources.
The traffic system example is a simplistic model but it serves to illustrate the usefulness of variable synchronism.
~nitial runs of that example has indicated that varying the risk and aggressiveness of cars has a substantial effect on the behaviour of the simulation e.g. rollbacks. This indicates that the UDS algorithm is capable of extracting significant parallelism from system models.
- . ~
Various modifications may be made to the preferred embodiment without departing from the spirit and scope of the invention as defined in the appended claims.
:.
,:
Claims (7)
1. A method of simulation for a number of objects comprising assigning to each object in the simulation a local virtual time (LVT) and a global virtual time (GVT) as well as assigning to each object a variable aggressiveness Ai, where 0 ? Ai? ?, Ai being the number of time units an object is capable of looking ahead to define a receive window within which an object is capable of receiving and processing messages, and a variable risk Ri, where 0 ? Ri? ?, Ri being the number of time units into the global future that an object is capable of sending messages to define a send window for each of the objects, to provide a unified distribution simulation system that allows variable asynchronous message passing with the synchrony between objects being varied by adaptable aggressiveness Ai and risk Ri parameters for each object in the simulation with each parameter being adjusted depending on circumstances in the simulation.
2. A method of simulation as defined in Claim 1 in which each object is provided with a continuously updated global virtual time (GVT) estimate (EGVT) where any EGVT ? GVT and the GVT is equal to the minimum of all the local virtual times (LVTs) for the objects in the system.
3. A method of simulation as defined in Claim 2 in which there is a corresponding meta object for each object, all messages being sent and received through the meta-objects wherein objects communicate with each other by sending synchronous actor messages to each other's meta-object with the meta-objects dictating how objects send and receive messages.
4. A method of simulation as defined in Claim 3, wherein EGVT + Ai for each object defines the time that a message can be received by that object.
5. A method of simulation as defined in Claim 4, wherein EGVT + Ri for each object defines the time that a message can be sent by that object.
6. A method of simulation as defined in Claim 5, wherein each metaobject's receive and send windows are kept up to date by a GVTEstimator which supplies a new value of the EGVT and requests the metaobject's estimate of a new EGVT which is calculated based on the elements in its requestQ and the state of its associated Simulation Object.
7. A method of simulation as defined in Claim 6, wherein the GVTEstimator polls all objects in the simulation for estimates of their current GVT and sets each component's EGVT to the minimum of these values.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2048140 CA2048140A1 (en) | 1991-07-30 | 1991-07-30 | Unified distributed simulation process |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CA 2048140 CA2048140A1 (en) | 1991-07-30 | 1991-07-30 | Unified distributed simulation process |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CA2048140A1 true CA2048140A1 (en) | 1993-01-31 |
Family
ID=4148096
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CA 2048140 Abandoned CA2048140A1 (en) | 1991-07-30 | 1991-07-30 | Unified distributed simulation process |
Country Status (1)
| Country | Link |
|---|---|
| CA (1) | CA2048140A1 (en) |
Cited By (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5956261A (en) * | 1997-03-13 | 1999-09-21 | International Business Machines Corporation | In-transit message detection for global virtual time calculation in parrallel time warp simulation |
| US7158925B2 (en) | 2002-04-18 | 2007-01-02 | International Business Machines Corporation | Facilitating simulation of a model within a distributed environment |
-
1991
- 1991-07-30 CA CA 2048140 patent/CA2048140A1/en not_active Abandoned
Cited By (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5956261A (en) * | 1997-03-13 | 1999-09-21 | International Business Machines Corporation | In-transit message detection for global virtual time calculation in parrallel time warp simulation |
| US7158925B2 (en) | 2002-04-18 | 2007-01-02 | International Business Machines Corporation | Facilitating simulation of a model within a distributed environment |
| US7856347B2 (en) | 2002-04-18 | 2010-12-21 | International Business Machines Corporation | Facilitating simulation of a model within a distributed environment |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Ferscha et al. | Parallel and distributed simulation of discrete event systems | |
| Peacock et al. | Distributed simulation using a network of processors | |
| Righter et al. | Distributed simulation of discrete event systems | |
| EP2156307B1 (en) | Distributed, fault-tolerant and highly available computing system | |
| Tindell | Adding time-offsets to schedulability analysis | |
| Fujimoto | Time management in the high level architecture | |
| Bagrodia et al. | Parsec: A parallel simulation environment for complex systems | |
| West | Optimising time warp: lazy rollback and lazy reevaluation | |
| GB2338325A (en) | Parallel discrete event simulation | |
| Wang et al. | Optimistic synchronization in HLA based distributed simulation | |
| Bagrodia | Perils and pitfalls of parallel discrete-event simulation | |
| McAffer | A unified distributed simulation system | |
| Vee et al. | Parallel discrete event simulation: A survey | |
| CA2048140A1 (en) | Unified distributed simulation process | |
| Kumar et al. | An approach towards distributed simulation of timed petri nets | |
| Chen et al. | Lookback: a new way of exploiting parallelism in discrete event simulation. | |
| Lin | Understanding the limits of optimistic and conservative parallel simulation | |
| Goldberg | Optimistic Algorithms for Distributed Transparent Process Replication | |
| Mascarenhas et al. | Minimum cost adaptive synchronization: experiments with the ParaSol system | |
| Kumar | Systems with low distributed simulation overhead | |
| Son | An algorithm for non-interfering checkpoints and its practicality in distributed database systems | |
| Madisetti et al. | Synchronization mechanisms for distributed event-driven computation | |
| Huang et al. | An approach for the unified time management mechanism for HLA | |
| Calinescu | Conservative discrete-event simulations on bulk synchronous parallel architectures | |
| Djemame | Distributed simulation of high-level algebraic petri nets with limited capacity places |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FZDE | Dead |