Approximate time and temporal uncertainty in parallel and distributed simulation.

摘要

One of the most fundamental aspects of simulation programs is the concept of time. In parallel and distributed simulations, it is important to coordinate the advancement of time and ensure that a simulation's clock and its view of global time are managed consistently. Otherwise events may not be correctly ordered before they are processed by the simulation, resulting in temporal anomalies. Time management mechanisms are used by parallel and distributed simulations to ensure the temporal aspects of the system are correctly reproduced. The importance of correctly ordering events depends on the simulation application. In some simulations, impossible event orderings can cause a simulator to fail; in others, non-causal event orderings may be acceptable because they are not perceptible to human participants. The result is two types of time management used in these simulations; one that imposes strict ordering of events and one that imposes no ordering of events.; The focus of this research is to create a unified approach to time management, one that supports existing approaches but also allows the user to strengthen or relax ordering constraints depending on the requirements of the application. The approach is based on temporal uncertainty. Temporal uncertainty is ubiquitous in simulation modeling, stemming from the fact that virtually any simulation is only an approximation of the real world. A key question concerns how one can introduce temporal uncertainty to simulation models and software. To address this question, a framework was developed for specifying temporal uncertainty in simulation models through the use of time intervals rather than precise time stamps. This approach yields a natural way of representing the inherent uncertainty in the structure, behavior, and operation of a system.; Based on the framework, an approach called Approximate Time clocks was developed which exploits time intervals to improve the runtime performance of parallel and distributed simulations. A partial ordering was defined for events with interval time stamps and algorithms for realizing this ordering were developed. The algorithm greatly reduces the number of synchronization steps required to implement event ordering, resulting in much more efficient execution on parallel computers.; A third focus of this research was to implement several cases from the temporal uncertainty framework to evaluate the efficiency of approximate time. For the first case, a new time advance primitive for process-oriented simulations called Interval Hold was developed. Performance measurements demonstrate that exploiting temporal uncertainty enabled the parallel simulation to execute an order of magnitude faster using the interval hold construct. In the second case, approximate time clocks were realized by exploiting temporal uncertainty over existing time management services. The Pre-Sampling approach to approximate time leads to enhanced lookahead of the simulation, significantly improving its performance.