Jeff S. Steinman
Jet Propulsion Laboratory
California Institute of Technology
4800 Oak
Grove Drive, Mail Stop 525-3960
Pasadena, CA 91109
(818) 306-6139, Fax
(818) 306-6912
jss@pebbles.jpl.nasa.gov
Frederick Wieland
MITRE Corporation
Mail Stop W291
7525 Colshire Drive
McLean, VA
22012
(703) 883-5385, Fax (703) 883-6478
fwieland@swift.mitre.org
KEY WORDS
Proximity detection, SPEEDES, Breathing Time Buckets, Time Warp, object-oriented simulation, interactive simulation, parallel discrete-event simulation.
ABSTRACT Generalized proximity detection for moving objects in a logically correct parallel discrete-event simulation is an interesting and fundamentally challenging problem. Determining who can see whom in a manner that is fully scalable in terms of cpu usage, number of messages, and memory requirements is highly non-trivial. A new scalable approach has been developed to solve this problem. This algorithm, called The Distribution List, has been designed and tested using the object-oriented Synchronous Parallel Environment for Emulation and Discrete- Event Simulation (SPEEDES) operating system. Preliminary results show that The Distribution List algorithm achieves excellent parallel performance. INTRODUCTION Providing proximity detection for simulations involving moving objects can be critical, especially when object interactions are restricted to finite range (Lubachevsky 93). Various parallel simulation studies in the past have touched on the subject of proximity detection. These "toy" simulations have ranged from colliding pucks (Hontalas 89) to swimming sharks devouring nearby fish (Bagrodia and Liao 90). Toy simulations are not the only applications that require proximity detection. For example, real-world applications would include: interactive military simulations, virtual reality, colliding space debris, biological models, and the modeling of interacting particles with short range forces (Rapaport 80). In this paper, proximity detection is applied to military simulations (Steinman 93b). Definitions Before introducing methods for proximity detection, some basic terms must be defined. Moving objects are called movers while sensing objects (which may also be movers) are called sensors. Each sensor has a perception envelope that defines the region of space for which it can "see" movers. Perception envelopes do not need to be circular or spherical, and they might be influenced by the environment (e.g. topography, time-of-day) or by the state of their sensors. The term, equation of motion (or EOM), is defined as a logical construct (e.g., a C++ object with internal data and methods) that supplies position and velocity information as a function of time (Stroustrup 86). No restrictions (such as straight line motion) are placed on EOMs. EOMs typically have a start and end time so that a sequence of EOMs can be formed to describe the motion of a complicated flight path. This sequence (or list) of EOMs is called the mover's script. For the sake of generality, a script may be composed of multiple types of EOMs. A general solution to the proximity detection problem must allow movers to unexpectedly change their scripts as they interact with their perceived environment. These changes must then be propagated to all of the sensors that can "see" the mover. Proximity Detection and Distributed Interactive Simulation It is useful to study how proximity detection is applied in other contexts. For example, the current trend in the military community is to confederate simulation elements by using the Distributed Interactive Simulation (DIS) set of protocols (Loral 92). The DIS approach is not a logically correct simulation strategy because it uses the wall clock for synchronization. Events in a DIS exercise are therefore not repeatable. Protocol Data Unit (PDU) messages are broadcast and received by different DIS "cells" without regard for rigorous time ordering. Because DIS protocols were designed for real-time training and systems acquisition decisions, the rigorous synchronization required for analytic studies is not as critical. DIS uses a strategy called Dead Reckoning for simulation objects to compute the locations of other objects in their virtual world. DIS objects periodically broadcast their state information (which includes parameters for their dead- reckoning equations) to all of the other objects in the simulation (Lin, 93). This requires a total of N messages (one from each object) if there are N objects in the simulation. Each object must process and store those N messages resulting in a loss of scalability. Objects broadcast their state information whenever one of two conditions have occurred: (1) five real-time seconds have elapsed since the last broadcast; or (2) the object has determined that the dead reckoning algorithm computed by the other DIS cells is in error. The second condition can arise when an object changes its EOM, or if cumulative errors in the dead reckoning algorithm have exceeded a certain threshold. These two conditions are motivated by the use of the (unreliable) User Datagram Protocol (UDP) for message communication and for ease in providing interoperability. The net effect is that DIS objects broadcast their state more frequently than what would have been required by strict adherence to discrete-event simulation practices. To be fair, DIS is not advertised as a synchronized discrete-event protocol. In summary, the DIS strategy assumes that the perception envelope of each sensor includes the entire virtual world. Each sensor receives information about all moving objects continually during the simulation. It is up to the algorithms within the computer image generators that are connected to each sensor to determine which objects in the virtual world are to be rendered or ignored. CTLS and Grid Bottlenecks A second example illustrating methods for proximity detection is taken from the Concurrent Theater Level Simulation (CTLS) effort at JPL (Wieland 89) that was implemented under the Time Warp Operating System (TWOS) (Jefferson 87). In their initial approach, the battlefield was decomposed into grids that represented physical regions of space. Objects were constrained to move in straight lines (although the scalar speed of the objects and their direction of motion could be changed at any time). Because all motion was modeled as a sequence of straight-line segments, only one type of EOM was needed. Curved trajectories, for example, could be approximated through a set of straight lines. Combining the straight-line motion with a rectangular battle space, grid boundary crossings could be easily computed. If a mover changed its motion by either changing its speed or direction, grid crossing events that were erroneously scheduled were canceled through user cancellation messages. The actual proximity detection computations were performed by the grid objects themselves, which reduced overall message traffic, ensured consistency in the treatment of proximity detection, and off-loaded the work from the moving objects. What was not anticipated was the fact that military simulations tend to behave like football games where everyone chases the player with the ball. In a typical CTLS simulation run, most of the ground units would inevitably congest into a small number of grids to fight their battle. Because grids performed most of the work, they became bottlenecks, thus limiting the amount of parallelism in the simulation. CTLS later developed a simplified preliminary version of The Distribution List algorithm (described later in this paper). The result of that effort was to remove proximity detection as the bottleneck (only to find another bottleneck in a different part of the simulation). The Distribution List approach worked well in the simplified TWOS implementation, but because it was not decoupled from the rest of the CTLS simulation, real benchmarks were not possible. At the same time, an overly complicated preliminary version of The Distribution List algorithm was similarly implemented in the Synchronous Parallel Environment for Emulation and Discrete-Event Simulation (SPEEDES) operating system (also developed at JPL) (Steinman 92a) with startling results. Excellent speedups were attained for most runs. However, it was observed that when all of the moving objects congested into the same area, Time Warp (which is one of the synchronization strategies supported by SPEEDES) sometimes became unstable. It was further interesting to note that the optimistic Breathing Time Buckets synchronization algorithm (also supported by SPEEDES) was completely stable because it uses a risk free message-sending strategy. More recent versions of The Distribution List algorithm virtually eliminate these instabilities by further reducing the number of messages required and by providing lazy cancellation to allow unrelated events to be processed out of order (more on lazy cancellation later). Furthermore, a new synchronization mechanism has been developed in SPEEDES called Breathing Time Warp (Steinman 93a) that merges the best ideas of Breathing Time Buckets and Time Warp into one paradigm. Breathing Time Warp provides a handle on the risk factor for parallel simulations. REQUIREMENTS OF THE ALGORITHM Main requirement: Proximity detection must provide each participating sensing object with a list of equations of motion for all other objects within its perception envelope. This list must be correct at all simulation times. In addition to the main requirement, there are requirements concerning scalability. The computations, messages, and memory should all scale well as the size of the simulation increases. Obviously, the algorithm will scale no better than the system that it is simulating. Besides scalability, there are a number of correctness requirements which must be met. First, the algorithm must be logically correct: that is, it must provide correct results independent of wall clock time, cpu capability, and communications latency. The algorithm must also provide repeatable results. Secondly, the solution must support asynchronous sensors with different scan modes and rates. This requirement eliminates those solutions relying on global time steps that synchronize all movers and sensors. Thirdly, the algorithm must be independent of the EOMs used by the movers. This requirement can be fulfilled by using a virtual base class object (in C++ for example) in which the EOM interface is defined without providing details of the implementation. Finally, the algorithm must allow objects to change their motion at any time. These changes must be propagated to all other sensors that have the object in their field of view. THE SIMULATION OBJECTS Four types of simulation objects are required by The Distribution List algorithm for proximity detection. They are listed below along with their important data structures. 1. Sensor: List of pointers to mover EOMs. 2. Mover: Script (sequence of EOMs describing motion). List of sensors (i.e., its distribution list). EOM node-distribution information. 3. Grid: List of movers that are "in" their space. List of sensors that can "see" their space. 4. EOMAN: List of mover scripts. A list of sensors for each mover script. Sensors may be fixed or moving. Furthermore, sensors can be enabled or disabled (see the discussion below on movers). The goal of The Distribution List algorithm is to provide each sensor with the equations of motion for all nearby movers. Movers move according to a sequence of one or more consecutive equations of motion. The mover's list of equations of motion is called a script. Gaps are not allowed in a mover's script. If a mover stops for a period of time, it must have an equation of motion that describes its (albeit trivial) position. When a mover's script is over, the mover should not be seen by any of the sensors. Movers are also defined as sensors (i.e., mover objects inherit from sensor objects in C++) but their sensing capabilities may be disabled if desired (for example, in a simulation focusing on the interaction of military aircraft, background commercial air traffic may be modeled as movers without sensors). Support for multiple inheritance is not assumed or required. Figure 1 shows an example of an inheritance tree for moving military objects and sensors.
Figure 1: An inheritance tree for various moving objects and sensors. In this example, the F15 is a mover and a sensor, the SCUD Missile is a mover with sensing disabled, the Space Sensor is a moving sensor but not a mover (it is not detected by anyone), and the Ground Radar is a fixed, non-moving sensor.Grids tile the simulated battle arena. They may be rectangular or they may be irregular in their shape. For example, when the Earth is decomposed into approximately equal area grids, the grids are first decomposed into equal latitude bands. Then, each latitude band is further decomposed into longitude segments to provide nearly equal area grids covering the Earth. With this approach, it is easy to compute a unique grid ID given a mover's latitude and longitude by using modular arithmetic. Card dealing the grids to computer nodes provides a simple way (again using modular arithmetic) to determine the processor node for each grid. EOMANs manage the equations of motion used by the sensors local to its node. The purpose of EOMAN objects is to maintain, at most, a single copy of a moving object's script on a given node. EOMAN objects have the responsibility of locally distributing mover equations of motion (from their script) to appropriate sensors. There are multiple EOMANs on each node so that a single EOMAN does not become a bottleneck. Movers choose their appropriate EOMAN by using a simple modular arithmetic hashing scheme that takes the remainder after dividing the mover's ID by the number of EOMAN objects created on each node. BASIC STRATEGY OF THE DISTRIBUTION LIST Before the full details of The Distribution List algorithm are given, a brief outline of its basic strategy is presented here to assist the reader later when the complete algorithm is described. The Distribution List algorithm uses grids to model simulated space. Movers check in and out of grids while moving sensors periodically inform the grids of their coverage (note, fixed sensors only need to inform the grids once during initialization). Grids manage a list of movers and a list of sensors that are operating in their represented space. When a mover checks into a new grid, it simultaneously checks out of its old grid (except during initialization when it checks into its first grid). The new grid returns its current list of sensors back to the mover so that the mover can update its distribution list. Movers always maintain a distribution list of sensors that require its equations of motion. In a similar fashion, when a sensor updates its coverage, it sends messages to new grids that are now in its coverage and to old grids that are no longer in its coverage. The grids then relay this sensor information to the movers in their mover list so that movers can also update their distribution list of sensors. Each mover keeps track of which nodes already have its script. All nodes that require the mover's script receive the script through a message sent to one of its EOMAN objects (remember, a hashing scheme based on the mover's unique id determines which EOMAN to use so that a single EOMAN on a node does not become a bottleneck). Then, messages (time tagged slightly later than the script's arrival time) are sent to EOMAN objects to identify which new sensors need the mover's current equation of motion and to identify which old sensors no longer contain the mover in their coverage. EOMAN objects then forward these changes to their local sensors by sending a message to new sensors (containing a pointer to the mover's current equation of motion), or by informing old sensors that they can no longer see the mover. From these messages, sensors maintain a list of pointers to their mover's current equation of motion (the primary goal of The Distribution List algorithm). The sequence of messages described for movers checking in and out of grids is depicted in Figure 2. The sequence of messages for sensors changing their grid coverage is depicted in Figure 3. These figures introduce the lookahead value, T/3, which is used for messages that are exchanged between objects that are on different nodes (more on this later). It should be noted here that a sensor's lists of equations of motion is actually a superset of the actual movers that are in its true coverage at any simulation time. In other words, The Distribution List algorithm acts as a filter providing all of the necessary equations of motion for movers that are inside its sensing coverage along with others that might be nearby.
Figure 2: Sequence of events for a mover checking in and out of grids. A lookahead delay of T/3 is allowed for the internode communications. EOMAN objects are on the same node as their local sensor objects so no lookahead is required. In this example, there are six sensors on three different nodes that received the mover's current equation of motion.
Figure 3: Sequence of events for a sensor updating its grid coverage. In this example, the sensor determines that there are two new grids in its coverage and two old grids that are no longer in its coverage. These grids relay the sensor information to their movers which then update their corresponding EOMAN objects back on the sensor's node. A lookahead delay of T/3 is allowed for the internode communications, but because the EOMAN objects are on the same node as the sensor, no lookahead is required in the final step.SCALABILITY AND GRID SIZE It is important for The Distribution List algorithm to use an appropriate grid size. If grids are too small, then sensor coverages will contain large numbers of grids. This results in more sensor-grid messages than necessary. Also, having a large number of grids in sensor coverages can make their new/old grid computations become costly. On the other hand, if grids are too large, then sensors will have many movers in their list, thus requiring more computations per scan to filter out the extraneous movers. Therefore, it is important to choose a grid size that keeps the number of grids per sensor relatively small, but not too small. A compromise must be made when the simulation involves differing sensor coverage sizes. Even though the optimal grid size is a function of the number of nodes, synchronization strategy, and computer hardware, The Distribution List algorithm still scales well (Wieland 92). On the other hand, if most of the work in the simulation is done in sensor scan events (which should normally be the case since there are no intensive computations required by The Distribution List algorithm), then proximity detection (i.e., sensors obtaining the equations of motion for nearby movers) is provided for free (which is the goal). Therefore, it should not be critical to completely optimize The Distribution List algorithm in practice. FUZZY GRIDS Grids play a fundamental role in The Distribution List algorithm. Movers and sensors both periodically check in and out of grids. One might question how this is really accomplished. Because grids may be irregular in shape (this is the case for a simulation where grids cover the Earth), and because movers potentially move in complicated motion (straight line motion cannot be assumed), computing exactly when a mover exits one grid and enters another can only be done iteratively (a very expensive endeavor). Computing exact grid crossings for movers can cripple the performance of any proximity detection algorithm. Furthermore, there may be problems (in terms of performance) for movers that just barely enter a grid and then almost immediately exit the same grid (see Figure 4). In this case, lookahead (i.e., the relative time difference between events and those that they schedule) may not be provided (more on this later). Therefore, the proximity detection algorithm should not be expected to compute grid crossings exactly. This leads to the concept of fuzzy grids. Fuzzy grids do not require exact grid crossing calculations. Instead, fuzzy resolution parameters are defined that reflect various grid uncertainties. Movers and Fuzzy Grids Movers check in and out of grids but not at exact boundaries. Instead, a resolution parameter, dr, is defined. Movers periodically calculate their grid as they move (at most) a distance of dr. Because movers might change their velocity unexpectedly, the time period for movers to check their grid is given by, dt = dr / Vmax(mover) Note that each mover may have a different maximum velocity so that in general, dt can be different for each mover. Suppose a mover calculates its grid at time t, and then almost immediately afterwards, enters the region of a different grid (see Figure 4). Because the fuzzy grid mechanism doesn't recheck the mover's grid until time t + dt, the mover would actually be in the wrong grid for almost dt simulation time units. However, because of the way dt is defined, the mover is in error (in terms of distance out of the grid) by at most dr. To accommodate this uncertainty, all sensor coverages must be expanded by the amount, dr, so that sensors can be guaranteed of having the equations of motion for all movers that are within their true sensing range. Expanding sensor coverages by dr may increase the number of movers in a sensor's list of mover equations of motion, but this is a small price to pay for the added benefits of generality provided by fuzzy grids.
Figure 4: An example of a mover at time t in grid 3 until time t+dt where it then exits grid 3 and checks into grid 2. Exact grid crossings are not required. There is no need for the mover to check into grid 4. Fuzzy grids allow moving objects to be outside of their grid by the amount dr.Sensors and Fuzzy Grids Moving sensors, like movers, do not add and delete grids from their coverages exactly in time as they move. Instead, a sensor resolution parameter, Dr, is defined. The basic idea here is that each moving sensor artificially expands its own coverage further by the amount Dr to account for its own grid coverage uncertainty. Moving sensors then only need to recompute their grid coverages at time intervals given by, Dt = Dr / Vmax(sensor) Again, note that each moving sensor may have a different maximum velocity so that in general, Dt can be different for each sensor (fixed sensors have Dr = 0, and Dt = infinity). Extending a sensor's coverage by Dr might seem like more than what is necessary. However, for the sake of generality, the fuzzy grid approach assumes that sensors may change their motion at any time (possibly moving in the opposite direction at maximum velocity). Therefore, sensor coverages are expanded symmetrically in all directions to accommodate possible changes to their motion. The result is that the true coverage of a sensor is always contained within its expanded coverage. Figure 5 shows how a moving sensor expands its coverage to accommodate the two fuzzy resolution parameters (dr for movers and Dr for sensors).
Figure 5: Expanding a moving sensor's coverage by dr to account for fuzzy movers and then by Dr to keep the sensor's true coverage within the current set of grids. The solid outline shows which grids are contained in the sensor's coverage.LOOKAHEAD Lookahead in a parallel simulation is defined to be the time difference (or delay) between a processed event and those that it generated. The importance of providing lookahead in both optimistic and conservative parallel simulations has been well established (Fujimoto 88, Felderman 91, Steinman 92b). Optimistic parallel simulations with a high degree of lookahead tend to have fewer rollbacks. Conservative simulations often rely on lookahead to ensure causality or to prevent deadlocks. Lookahead is also important in The Distribution List algorithm and is characterized by the parameter T (see Figures 2 and 3). The basic idea for incorporating lookahead in The Distribution List algorithm is to add fixed delays as events are scheduled for objects on other nodes. Zero-time delays (i.e., scheduling events with no lookahead) are allowed for events scheduled between objects on the same node (e.g., self scheduling events or events between an EOMAN object and its local sensors). Because lookahead delays events, ensuring that all sensors have their required mover equations of motion becomes more challenging. Figure 2 shows the sequence of message-events that are generated as a mover checks in and out of its grids. At time, t, imagine that the mover determines that it is in a new grid. Then at time, t + T/3, the two grids (the old and the new) receive updates concerning the mover. The new grid relays its corresponding sensor information back to the mover with another delay of T/3 so that the mover has the new sensor information at time t + 2T/3. The mover next relays its script to EOMAN objects (again with a delay of T/3) at time t + T. EOMAN objects finally distribute the mover's current equation of motion to their appropriate local sensors with a zero time delay. The net result is that sensors receive their updates T units of simulation time after the mover determines that it is in a new grid. Figure 3 shows a similar situation as sensors modify the grids in their coverage. Again, the sensors receive updates from movers T units of simulation time after their coverage has changed. Both of these situations (see Figures 2 and 3) result in proximity detection errors if further steps are not taken. For example, a mover might have just entered a sensor's coverage at time t, but because of the delay T, the sensor won't know about the mover until time t + T. Thus, the sensor would miss the mover between times t and t + T, thereby having invalid proximity detection information. The problem of sensors receiving late mover information is fixed by extending each sensor's coverage one more time by an additional amount D. This amount must account for the fastest mover in the simulation. Therefore, each sensor must extend its coverage by the amount, D = T x Vmax(all movers) By extending sensor coverages by D, a buffer zone is provided to guarantee that even with the delay T, no mover will be missed in a sensor's true coverage. The amount of lookahead can be varied by changing the value T. No lookahead would then correspond to the value T being set to zero resulting in a zero value for D. SPEEDES DIAGRAMS The flow of The Distribution List algorithm is described by the SPEEDES diagram in Figure 6. SPEEDES diagrams show how events are generated, which objects they act on, and the amount of lookahead provided as events are scheduled. One interesting feature of SPEEDES diagrams is that events are separated from the simulation objects that they act on. This reflects the highly object-oriented nature of event processing in SPEEDES (where events are encapsulated C++ objects, separate from the simulation objects that they "act" on). Events as objects have major benefits in terms of scalable software engineering practices and by providing very powerful mechanisms for supporting external I/O, efficient incremental state saving, and lazy cancellation (Steinman 93c). THE DISTRIBUTION LIST ALGORITHM
Figure 6 gives the complete picture of The Distribution List algorithm. The reader is advised to frequently refer to this figure in the following discussion.The Initial Events The best place to begin the discussion of The Distribution List algorithm is with the initial events that start up the simulation. There are three kinds of initial events. It is important to notice that these three events are also self- scheduling events. The next_script event is scheduled for each mover in the simulation. Its purpose is to manage its mover's script of equations of motion. An equation of motion has a start time and an end time (note, the end time of an equation of motion can be infinity). Scripts are constructed by consecutive equations of motion without time gaps. The next_script event removes the current equation of motion from the mover's script at its end time so that the next item in the script will represent the movers correct equation of motion. When this event is processed, it first checks if the end time of the current equation of motion matches the event time tag. If it does, then the event is processed and reschedules itself for the next equation of motion in the mover's script (unless the script is empty or if the new equation of motion has an end time of infinity). However, if the time tag does not match the end time of the mover's current equation of motion, the event knows that the mover has changed its script unexpectedly (see the change_script event) so the event does no processing (this eliminates the need for canceling events). The update_grid event is scheduled for each mover in the simulation. Its purpose is to compute the grid that the mover is in, and then if this is a new grid, it schedules events to move into the new grid (add_m2g) and to move out of the old grid (del_mfg) with lookahead T/3 (see discussion on lookahead). When the update_grid event is initially processed, its mover is not in a grid yet so it only schedules one event (add_m2g) to check into the new grid. The update_grid event then reschedules itself (unless its script is empty) to occur at dt time units into the future (see discussion on fuzzy grids). The update_coverage event is scheduled for each sensor in the simulation (remember that movers might also be sensors). Its purpose is to compute grid coverages for a sensor (remember that sensor coverages are expanded by three parameters: dr, Dr, and D). The update_coverage event checks which grids are new and which grids are old. The changes are then sent with lookahead T/3 to the grids by scheduling two events (add_s2g and del_sfg). The update_grid event then reschedules itself to occur at Dt time units into the future unless it is a fixed sensor that does not move (note, Dt is infinite for non-moving sensors). Grid Events There are four kinds of events that act on grids. These events involve adding movers and sensors to grids, or deleting them from grids. First consider the two mover-grid events. When a mover checks into a new grid with the event add_m2g, it simultaneously checks out of its old grid with the event del_mfg (unless it is the first time when there is no old grid). The new grid needs to relay its sensor information back to the mover (see the new_sensors event in Figure 6) so that the mover can correctly distribute its equations of motion to the appropriate sensors. Figure 6: SPEEDES diagram for parallel proximity detection. Legend for SPEEDES Diagrams 1. Oval: Represents a type of event object. 2. Box: Represents a type of simulation object. 3. Bold Line: Links an event type with its associated simulation object type. 4. Arrow: Shows which events schedule other events. 5. Bold Arrow: An event type that is scheduled at the start of the simulation. 6. Time Value: The amount of lookahead when scheduling an event 7. Bold Box: An external module that is outside of the internal (SPEEDES) simulation. 8. Dashed Arrow: A message coming to or from an external module. Now, consider the two sensor-grid events. As sensors check their coverages, they determine which old grids are no longer in their coverage and which new grids are now currently in their coverage. Add_s2g events are then scheduled to add the sensor into its new grids, and del_sfg events are scheduled to delete the sensor from its old grids. The new sensor information is then relayed to the movers in the sensor's new and old grids (see the add_s2m and del_sfm events in Figure 6). Updating the Mover's Distribution List Three events (new_sensors, add_s2m, and del_sfm ) can modify a mover's distribution list. The new_sensors event contains a new distribution list for the mover. This new distribution list is compared with the mover's old distribution list. Sensor's that are in the new list, but not in the old list, must receive a copy of the mover's equations of motion. Similarly, sensors that are in the old list, but not in the new list, must have the mover's equations of motion removed. The add_s2m and del_sfm events also update distribution lists in a similar way as sensors change their grid coverage. Adding Equations of Motion to Sensors The new_sensors and add_s2m events may add new sensors to a movers distribution list. Because The Distribution List algorithm makes sure that at most only one copy of a mover's equations of motion resides on a node, a check is made to see if the mover's script has already been sent to the appropriate EOMAN object (remember, hashing is used based on the mover's unique ID to determine which EOMAN object to use on the sensor's node). If the mover's script does not reside on the sensor's node, an add_e2e event is scheduled for the appropriate EOMAN object to add the mover's equations of motion (i.e., its script) to the EOMAN object. A lookahead value of T/3 is used. In addition to this, an add_s2e (add sensor to EOMAN) event is scheduled to occur with lookahead T/3 + e so that the mover's equations of motion are already residing in the EOMAN object when the mover's current equation of motion is passed to the sensor. When the EOMAN object processes the add_e2e event, it actually sends a pointer to the mover's current equation of motion to the sensor through the add_m2s event, not a full copy of it. A special self-scheduling event is generated when the add_e2e event is processed. This event, called eoman_script, manages the mover's script in the EOMAN object (very similar to the next_script event for the mover). However, there is one important difference. As this event removes the mover's old equation of motion from its script (time tagged at the end time of the equation of motion), it schedules an add_m2s event for all sensors on its node that need the mover's current equation of motion. When processed, the add_m2s event replaces the pointer to the mover's old equation of motion with a pointer to the mover's new equation of motion. No lookahead is required because these sensors are (by definition) on the same node as the EOMAN object. When the script is over, the mover is removed from the sensor. Removing Equations of Motion from Sensors The new_sensors and del_sfm events may delete old sensors from a movers distribution list. When this occurs, an event called del_sfe is scheduled for the EOMAN object on the sensor's node that deletes the sensor from the EOMAN object. A lookahead value of T/3 is used. When the del_sfe event is processed, it schedules an additional event, del_mfs, for the sensor (with no lookahead) that removes the pointer to the mover's current equation of motion from the sensor's list. When processing the del_sfm event, if it is determined that there are no more sensors on that node that require the mover's equation of motion, the mover is informed that its script no longer exists on that node. Similarly, when the del_sfe event is processed, it will remove the mover's script from the EOMAN object because it too will know that no other sensors require its mover's equation of motion. However keep in mind that there is a delay of T/3 from the time the mover thinks that its script is no longer residing in the EOMAN to the time that the EOMAN actually removes the mover's script. Care must be taken to keep things straight, especially when human interactions or other mechanisms change the script of the mover unexpectedly. Sensor Scans Sensors should be idle if there are no movers in their perception envelope. It is important, therefore, to have a general mechanism to start up a sensor when a mover enters its coverage (i.e., when the sensor receives a mover's equation of motion). This is accomplished by having each sensor define its own scan event type (for example, ground-based radars scan differently than airborne radars or space-based infrared sensors). This scan event is activated when a mover's equation of motion is added to a sensor's empty list. The scan event is a self-scheduling event, so it only needs to be activated when the sensor is idle. The scan event reschedules itself periodically if the sensor's mover list is not empty. If the sensor's mover list ever becomes empty, then the scan event terminates. It will be activated again the next time a mover is added to the sensor's empty list. Provisions have been made for external trackers to plug into any of the sensors in the simulation (see the ext_tracker event in Figure 6). These external tracker modules take over the tracking function of the sensor. Human Interactions and Changing the Script So far the discussion of proximity detection has assumed that movers move according to predefined scripts of equations of motion. However, in a more complicated simulation, movers may change their motion based on either internal events (for example, a simulated military aircraft engaged in an interactive dogfight) or from human interactions coming from the outside world (see the change_script event in Figure 6). To make things more complicated, lookahead cannot be assumed. If a mover changes its equations of motion Үow,Ӡthen sensors in the mover's distribution list must get those changes now. To solve this problem of unexpected changes in mover scripts, when a script is sent to an EOMAN object, the time tag of the change_script or add_s2m event is also sent (these are the only events that send mover scripts to EOMAN objects). Therefore, the EOMAN object always knows what time mover scripts are valid. If an EOMAN ever gets a script from a mover with a later send time than a mover script that is currently in the EOMAN, it accepts it. Otherwise, the EOMAN object knows that the current script is more up-to-date than the one that it is currently trying to add. Therefore, the script is not added because it is not valid any longer. This approach alleviates the need for user event-cancellation. BENEFITS OF BREATHING TIME BUCKETS Breathing Time Buckets (Steinman 92a) is a unique optimistic synchronization strategy like Time Warp (Fujimoto 90) except that it is risk free (i.e., bad messages are never released so that antimessages are not required). Because events are processed risk free in (breathing) time cycles and because messages for grids are always given a lookahead value of T/3, it turns out that events for grids never need to be rolled back. This is because the time tags for grid events in the next Breathing Time Buckets cycle are always greater than the time tags of the grid events in the current cycle. This very important phenomenon is only true in risk free paradigms such as Breathing Time Buckets. This is also one of the reasons why Breathing Time Buckets is completely stable in supporting The Distribution List algorithm while Time Warp may not be. LAZY CANCELLATION Time Warp does not offer the same risk-free stability as Breathing Time Buckets but it can offer superior performance for simulations with limited intrinsic lookahead, especially if the number of objects per node is high. As a method of decreasing the number of rollbacks, lazy cancellation can help reduce possible instabilities (Reiher 90). It should be noted here that lazy cancellation is supported in SPEEDES in the Breathing Time Buckets algorithm (as well as in Time Warp) even though it is not necessary for grid events. SPEEDES offers a unique mechanism for supporting lazy cancellation because it defines events as C++ objects (Steinman 93c). When a SPEEDES event is processed, input data from the simulation object (which is also a C++ object) can be stored in data portions of the event object. If a straggler message arrives for that simulation object, all events processed in its future must be rolled back. However, antimessages are not immediately released for events that are participating in lazy cancellation. Instead, just before reprocessing the event (for the second time), the inputs from the simulation object that were stored in the event object when it was first processed are compared with the current values in the simulation object. This comparison is accomplished through a user defined virtual function called by SPEEDES. If the virtual function determines that reprocessing the event would get the same answer, the event is simply rolled forward (reversible incremental state saving techniques are used in SPEEDES) without repeating the event's computations. Otherwise, antimessages are generated and the event is reprocessed. Now, the key to using lazy cancellation in The Distribution List algorithm is to note that sensor-grid events or mover-grid events can be processed out of order, but not sensor-mover grid events. For example, when mover events act on grids, sensor information is sent back to the mover. Mover events are independent of other mover events. The same is true for sensor- grid events. They only need to know which movers require their sensor information and are independent of other sensor events. A simple trick is used to determine whether rolled back grid events can be rolled forward instead of being reprocessed. Each time a mover-grid event is processed, a mover counter in the grid object is incremented. Similarly, each time a sensor-grid event is processed, a sensor counter in the grid object is incremented. Note that as these counters are incremented, they must bypass state saving mechanisms. Otherwise it would defeat their purpose. When a mover event is processed, it saves the sensor counter in its object. If the mover event is rolled back, then just before reprocessing the event again, it checks if the sensor counter is unchanged. If it is unchanged, then the mover event simply rolls forward. In a similar fashion, rolled back sensor events can check the mover counter. This simple mechanism very much reduces rollbacks, especially at initialization when fixed sensors are first entering grids before movers have begun their events. This mechanism also cuts down the number of rollbacks during the normal progression of the simulation. Grids can be a source of instabilities in Time Warp since they can easily become fan-in and fan-out sources of events. Therefore, it is very important to reduce the number of rollbacks for grid events. DEAD RECKONING REVISITED The Dead Reckoning strategy was discussed in the introduction of this paper. In a simulation where moving objects are constantly changing their equations of motion, something like Dead Reckoning must be used. Continuously changing equations of motions must be discretized and then distributed to appropriate sensors. The Distribution List algorithm does this automatically whenever a mover changes its equations of motion. As long as movers don't change their motion too often, The Distribution List algorithm will perform admirably. However, unlike the Dead Reckoning approach, The Distribution List algorithm completely scales in terms of reliable message sending (DIS relies on UDP broadcasts), memory usage, and in terms of computations. The Distribution List algorithm developed in SPEEDES can also support external human interactions similar to those defined by Distributed Interactive Simulation (DIS) protocols without losing scalability (Gordon 92). For example, training simulators representing tanks, jet fighters, or any other moving vehicle can plug into the discrete-event simulation through ghosted objects (Weatherly 91) represented within SPEEDES (see Figure 7). In fact, it is easy to mix computer generated forces with ghosted objects that are controlled externally by humans. Proximity detection events are then executed within a larger simulation context.
Figure 7: External modules and ghost objects in SPEEDES. Two external tank modules are connected to corresponding ghost objects in SPEEDES. Other simulation objects are modeled inside of SPEEDES to provide computer generated forces. All objects participate in proximity detection supported by The Distribution List algorithm. External tanks receive proximity detection data from their simulated ghost object. When a tank changes its equations of motion, those equations are sent back to its ghost object which then distributes them as needed to other objects according to The Distribution List algorithm.The methods for supporting external interactions have been documented in other papers (Steinman 92a). They will only be briefly mentioned here. The basic idea is that an external module (representing a tank, for example) continuously exchanges messages with an internal SPEEDES object that is ghosted within the simulation. While SPEEDES may be running an optimistic synchronization protocol, external modules can never be allowed to roll back. Some might think that this proves that optimistic synchronization strategies can never support interactive applications. However, this is actually not the case. It turns out that because of rollback support, optimistic strategies can offer the best means for supporting interactive real-time simulations. In SPEEDES, an event is processed in multiple stages. One of these stages is performed as events are committed (typically just before garbage collection). During this stage (sometimes called Phase 2 in SPEEDES), valid messages are released to the outside world for external modules. These messages could contain proximity detection information as well as other state information required by external modules. External modules may then send their updated equations of motion (if their motion has changed) and other pertinent information back to the ghosted object in the simulation. A certain amount of lookahead should be defined as messages are continuously being exchanged between ghosted SPEEDES objects and external modules. When SPEEDES releases a message to an external module, it expects a message back at a certain time later (this simulated time delay represents the amount of lookahead for the external module). SPEEDES then keeps all of the external modules logically synchronized with the simulation. For example, when a message is sent from SPEEDES to an external module, a barrier is set up that does not allow the Global Virtual Time (GVT) of the simulation to advance beyond the defined return message time. This barrier is only removed when the return message is received, or if the external module ever disconnects intentionally or unintentionally from the simulation. The lookahead defined for external modules should be very similar to the broadcast rate in DIS. The Distribution List, supported by SPEEDES, manages time in a logically correct manner (instead of relying solely on the wall clock) and in a manner that scales. PERFORMANCE It is not the goal of this paper to give conclusive performance results of The Distribution List algorithm. An extensive benchmarking effort is currently underway. More results will be given at a later date. However, it is important that some evidence is presented here to show that this algorithm does indeed give good speedup. A simulation consisting of 800 ground radars, 947 commercial aircraft, and 173 military aircraft randomly flying about the Earth was chosen to measure the performance of The Distribution List algorithm (see Figure 8). The aircraft were allowed to randomly change their motion (i.e., their scripts) using an exponential time distribution with a time constant of 10 minutes. Aircraft flew at velocities ranging from 125 to 1858 km per hour (mach 2). Radar coverages ranged from 150 to 1500 km. Sensor scan times varied from one to fifteen seconds. Kalman filters were used by all of the radars. The grid size was chosen to be 500 km (a good match with typical sensor coverages). Both fuzzy grid parameters (dr and Dr) were chosen to be 100 km. The lookahead parameter, T, was chosen to be 100 seconds. Breathing Time Buckets achieved a speedup of 3.29 on four workstation Silicon Graphics Inc. processors communicating over Ethernet. Interestingly, there was only one rollback reported as 2,212,676 events were processed. Only 34,437 messages were sent between nodes, thus confirming the fact that The Distribution List algorithm provides locality for scan events. Time Warp (not shown in Figure 8) also achieved excellent performance attaining a speedup of 3.17. Only 82 rollbacks and 25 antimessages were reported. These measurements clearly show that there is a high degree of parallelism in the simulation. Very high performance on large parallel machines is therefore expected.
Figure 8: Performance results. 800 ground radars, 947 commercial aircraft, and 173 military aircraft with radars were modeled for one hour of simulation time. Breathing Time Buckets on four processors communicating through Ethernet achieved a speedup of 3.29. During the course of the simulation, 2,212,676 events were processed requiring 34,437 messages. Because of good load balancing, large numbers of objects, and enough lookahead, only one rollback occurred in the simulation.SUMMARY This paper described a new solution to the parallel proximity detection problem called "The Distribution List" algorithm. In The Distribution List algorithm, movers and sensor coverages check in and out of grids. As this occurs, movers maintain a list of sensors that might detect its motion. This list can be viewed, then, as the mover's distribution list to sensors that require its equations of motion. The net result is that every sensor in the simulation receives a list of pointers to the equations of motion for all movers that are within its sensing range. This list is valid at any time in the simulation so that sensors can scan their proximity at any time without requiring extra messages to be sent. Proximity detection operates in the background by providing mover equations of motion to sensors. The majority of simulation computations are typically performed through sensor scan events that require no extra messages. One of the important concepts in The Distribution List is that fuzzy grids are used to model simulated space. Fuzzy grids manage spatial information for moving objects and sensor coverages. Fuzzy grids allow movers and sensor coverages to check in and out of grids without computing exact grid crossings. Instead, sensor coverages are expanded by fuzzy resolution parameters to accommodate the fuzzy grid crossings. Lookahead is also introduced in The Distribution List algorithm in such a way that allows risk-free synchronization strategies like Breathing Time Buckets to never roll back grid events. Lazy cancellation can be used with Time Warp to permit mover-grid events or sensor-grid events to be processed out of order while mover-sensor grid events must still be processed in their correct order. Lazy cancellation for grid events (which can become fan-in and fan-out types of events) can help Time Warp become more stable. Preliminary results measured on UNIX workstations over Ethernet show that The Distribution List achieves outstanding performance for military simulations involving air and strategic defense scenarios. Work in porting SPEEDES to other computer architectures is currently underway. Further benchmarks of The Distribution List algorithm are expected in the near future. BIOGRAPHY Jeff Steinman received B.S. degrees in computer science and in mathematical physics from California State University Northridge in 1980. He then worked at Hughes Aircraft Company in the Radar Systems Group for four years while studying physics at UCLA. In 1988, he received his Ph.D. in experimental high-energy particle physics from UCLA, where he measured the quark content of virtual photons generated at the Stanford Linear Accelerator Center. Since then, he has been a member of the technical staff working at the Jet Propulsion Laboratory, building simulations for strategic missile and air defense. Jeff Steinman is the principal developer of the SPEEDES operating system. Frederick Wieland received a B.S. degree in astronomy from the California Institute of Technology in 1983, and an M.S. degree in Computer Information Systems from the Claremont Graduate School in 1988. He worked at the Jet Propulsion Laboratory from 1983-1992 where his primary research interest was the performance of distributed simulations. Subsequently he joined the staff at the Naval Research Laboratory, where he is studying interactive physics-based distributed simulations. ACKNOWLEDGMENTS The research described in this paper was carried out by the Jet Propulsion Laboratory, California Institute of Technology, and was sponsored by SDIO through the National Test Facility at Falcon Air Force Base, Colorado Springs, and through Innovative Science & Technology at the Pentagon by agreement with the National Aeronautics and Space Administration. Reference herein to any specific commercial product, process, or service by trade name, trademark, manufacturer, or otherwise, does not constitute or imply its endorsement by the United States Government or the Jet Propulsion Laboratory, California Institute of Technology. REFERENCES Bagrodia R. and Liao W. 1990. "Parallel Simulation of the Sharks World Problem." In Proceedings of the Western Simulation Conference, December 1990, Pages 191-198. Felderman R. and Kleinrock L. 1992. "Two Processor Time Warp Analysis: Some Results on a Unifying Approach." Proceedings of the SCS Multiconference on Advances in Parallel and Distributed Simulation. Vol. 23, No. 1, Pages 3-20. Fujimoto R. 1988. "Lookahead in Parallel Discrete-Event Simulation." International Conference on Parallel Processing. Vol. 3, Pages 34-41. Fujimoto R. 1990. "Parallel Discrete-Event Simulation." Communications of the ACM. Vol. 33, No. 10, Pages 30-53. Gordon L. 1992. "On Distributed Simulation Involving Human Interaction." In Proceedings of the SCS Summer Computer Simulation Conference. Hontalas P., et al. 1989. "Performance of the Colliding Pucks Simulation on the Time Warp Operating System." In Proceedings of the SCS Multiconference on Distributed Simulation. Vol. 21, No. 2, March 1989, Pages 3-7. Jefferson D., et al. 1987. "Distributed Simulation and the Time Warp Operating System." ACM Operating System Review. November 1987. Lin K. 1993. ҄evelopment of Improved Dead Reckoning Algorithms for Distributed Interactive Simulation, Second Draft,Ӡ Institute for Simulation and Training, University of Central Florida, May 1993. Loral Systems Company 1992. Strawman Distributed Interactive Simulation Architecture Description Document. Prepared for Program Manager - Training Devices Naval Training Systems Center. Orlando, Florida, ADST/WDL/TR-92003010, Vols. 1 and 2. Lubachevsky B. 1993. "Several Unsolved Problems in Large-Scale Discrete Event Simulations.", In Proceedings of the 7'th Workshop on Parallel and Distributed Simulation (PADS93). Vol. 23, No. 1, July 1993, Pages 60-67. Rapaport D. 1980. "The Event Scheduling Problem in Molecular Dynamic Simulation." Journal of Computational Physics. Vol. 34, 1980, Pages 184-201. Reiher P. 1990. "Cancellation Strategies in Optimistic Execution Systems." In Proceedings of the SCS Multiconference on Distributed Simulation. Vol. 22, No. 1, Pages 112-121. Steinman J. 1992a. "SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation." International Journal in Computer Simulation. Vol. 2, Pages 251-286. Steinman J. 1992b. "The Event Horizon.", JPL Internal Document D- 10029. November 1992. Steinman J. 1993a. "Breathing Time Warp." In Proceedings of the 7'th Workshop on Parallel and Distributed Simulation (PADS93). Vol. 23, No. 1, July 1993, Pages 109-118. Steinman J. 1993b. "Synchronization of Parallel and Distributed Military Simulations using SPEEDES." In Proceedings of the 1993 Summer Computer Simulation Conference. July 1993, Pages 701-710. Steinman J. 1993c. "Incremental State Saving in SPEEDES Using C++." To be Published in Proceedings of the SCS Winter Simulation Conference, December 1993. Stroustrup B. 1986. The C++ Programming Language. Addison-Wesley Publishing Company, Reading Massachusetts. Wieland F. et al. 1989. "The Performance of a Distributed Combat Simulation With the Time Warp Operating System." Concurrency: Practice and Experience. Vol. 1, No. 1, Pages 35-50. Wieland F., Reiher P., and Jefferson D. 1992. "Experiences in Parallel Performance Measurement: The Speedup Bias." In Proceedings of the Third Symposium on Experiences With Distributed and Multiprocessor Systems. March 1992. Weatherly R. et al. 1991. "Aggregate Level Simulation Protocol." In Proceedings of the 1991 Summer Computer Simulation Conference. Pages 953-958.