Acceleration of Distributed Discrete Event Simulation with Intelligent Approximation of Look-Ahead
Security and Dependability, Operating-, Communication- and Distributed Systems
Final Report Abstract
In this project we have investigated the approach to accelerate distributed discrete event simulation by offering the possibility of a trade-off between the simulation precision and the execution time. Our novel approach is based on the semi-conservative look-ahead estimation. The models for approximate simulation give some free margin to the simulator during the execution. It allows some overestimation and estimation failures during the dynamic look-ahead estimation. In our approach, the semi-conservative look-ahead estimation is done during the simulation for each link between LPs. The length of the time interval between committing time of one external event and the time stamp of the next event of the same link will be collected. Its probability density function is estimated and the look-ahead from a regular conservative estimation will be extended based on the probability density function. Both the probability of estimation failure and the time deviation of the event when the estimation fails are controlled. We demonstrated the potential of our method by a case study of different models. The results show that by accepting up to 5% event error, the execution time of the distributed simulation with semi-conservative look-ahead estimation is much lower than the simulation with native conservative look-ahead, so that a speed-up of 2% - 20% can be expected. Most important, an acceptable trade-off between the simulation precision and the execution time can be achieved. With the completion of the project, the objective defined in the proposal has been achieved. Our approach developed in this project can be applied in many different simulation systems to reduce the execution time and the related overhead. It is considerable for many extra large and complex simulation tasks. Especially, it is useful to find notable phenomena, most of them are errors and drawbacks, through simulation in an early stage during the development of new product in industry. In this way, the overall cost of the development could be reduced. Furthermore, we believe that the basic idea of our approach is not limited by the scope of this project. Besides the discrete event simulation, our approach is a way to reduce the overhead of other types of simulations, such as time-stepped simulation and co-simulation.
Publications
- Improving the performance of distributed discrete event simulation by exchange of conditional lookahead. Concurrency and Computation: Practice and Experience, Wiley, 2016
D. Fu, M. Becker, H. Szczerbicka
(See online at https://doi.org/10.1002/cpe.3811) - “Approximate distributed discrete event simulation using semi-convervative look-ahead estimation,” in Distributed Simulation and Real-Time Applications, 2019. DS-RT 2019. 23th IEEE/ACM International Symposium on, Oct 2019
D. Fu, M. O’Connor, M. Becker, and H. Szczerbicka
(See online at https://doi.org/10.1109/DS-RT47707.2019.8958660)
