Research Article
Compositional Construction of Importance Functions in Fully Automated Importance Splitting
@INPROCEEDINGS{10.4108/eai.25-10-2016.2266501, author={Carlos Budde and Pedro D'Argenio and Ra\^{u}l Monti}, title={Compositional Construction of Importance Functions in Fully Automated Importance Splitting}, proceedings={10th EAI International Conference on Performance Evaluation Methodologies and Tools}, publisher={ACM}, proceedings_a={VALUETOOLS}, year={2017}, month={5}, keywords={computing methodologies~rare-event simulation computing methodologies~discrete-event simulation computing methodologies~modeling and simulation}, doi={10.4108/eai.25-10-2016.2266501} }- Carlos Budde
Pedro D'Argenio
Raúl Monti
Year: 2017
Compositional Construction of Importance Functions in Fully Automated Importance Splitting
VALUETOOLS
ACM
DOI: 10.4108/eai.25-10-2016.2266501
Abstract
Importance splitting is a technique to accelerate discrete event simulation when the value to estimate depends on the occurrence of rare events. It requires a guiding importance function typically defined in an ad hoc fashion by an expert in the field, who could choose an inadequate function. In this article we present a compositional and automatic technique to derive the importance function from the model description, and analyze different composition heuristics. This technique is linear in the number of modules, in contrast to the exponential nature of our previous proposal. This approach was compared to crude simulation and to importance splitting using typical ad hoc importance functions. A prototypical tool was developed and tested on several models, showing the feasibility and efficiency of the technique.