Acceleration of Distributed Discrete Event Simulation with Intelligent Approximation of Look-Ahead

分布式离散事件仿真的一个主要问题是其性能相对较差，这是由于维护因果关系顺序的开销巨大，这保证了仿真的正确性。因此，与顺序模拟相比，不能显著减少执行时间。这在进程紧密耦合且前瞻时间非常短的情况下尤其如此。另一方面，在广泛的模型的仿真中通常存在大量的事件，其中这些事件的执行时间的有限偏差对最终仿真结果的正确性具有非常小的影响。因此，模拟不需要关于每个单个事件的时间戳和顺序是精确的。以受控的方式接受这种偏差提供了一种机制，以实现模拟精度和执行时间之间的权衡。本项目的主要目标是开发一种方法，以便通过在一定程度上容忍这种偏差来减少模拟的执行时间，同时结果仍然具有可接受的精度。为了实现这一目标，我们提出了一种新的分布式仿真方法与半保守前瞻估计。在这种方法中，我们考虑估计前瞻允许有限的高估。过度估计可能会导致因果关系错误，这将被一个非常有效的恢复过程以牺牲仿真结果中的错误为代价而消除。接受这种高估是一种最大化前瞻的方式，这导致了仿真执行时间的减少。

One major problem of distributed discrete event simulation is its relative poor performance due to the huge overhead to maintain the order of causality, which guarantees the correctness of the simulation. As result, the execution time cannot be reduced significantly compared to sequential simulation. This holds especially when the processes are tightly coupled and the look-ahead is very short. On the other hand, there usually is a great amount of events in the simulation of a wide range of models, where a limited deviation in the execution time of these events has a very small influence on the correctness of the final simulation result. Thus the simulation does not need to be exact regarding the time stamp and the order of every single event. Acceptance of such deviations in a controlled way provides a mechanism to achieve the trade-off between simulation accuracy and execution time.The main objective of this project is to develop a methodology, so that the execution time of the simulation will be reduced by tolerating such deviations to a certain extent while the result still has acceptable accuracy. To achieve this objective, we propose a new approach of distributed simulation with semi-conservative look-ahead estimation. In this approach, we consider to estimate the look-ahead permitting limited over-estimation. The over-estimation might result in causality errors, which will be dismissed by a very efficient recovery procedure at the expense of errors in the simulation result. Acceptance of such over-estimation is a way to maximize the look-ahead that results in a reduction of the execution time of the simulation.