Nov 08, 2016: Carlos E. Budde: Compositional Construction of Importance Functions in Fully Automated Importance Splitting

November 08, 2016Compositional Construction of Importance Functions in Fully Automated Importance Splitting
Room: HB 2BCarlos E. Budde
12:30-13:30

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 of the model under study.
Besides the lack of generality, this strategy may result in the choice of an inadequate function,
in detriment of the efficiency gain which is sought.

In this talk I will present a compositional and automatic technique to derive the importance
function from the model description[0]. This technique is linear in the number of modules,
in contrast to the exponential nature of our previous proposal. The models we study are
expressed in the IOSA formalism[1]. I will also analyse different composition heuristics for
the resulting "local importance functions".

We compared our approach to crude simulation and to importance splitting using typical ad hoc
importance functions. Experimentation was carried out on several models taken from the literature,
using a prototypical tool we developed. By means of an example I will depict the feasibility and
overall efficiency of our technique.

[0]: Carlos E. Budde, Pedro R. D’Argenio, and Raúl E. Monti: Compositional Construction of Importance Functions in Fully Automated Importance Splitting. Accepted for publication at VALUETOOLS '16 (PDF available upon request).
[1]: 
Pedro R. D’Argenio, Matias David Lee, and Raúl E. Monti: Input/Output Stochastic Automata: Compositionality and Determinism. In Proceedings of FORMATS 2016 (doi: 10.1007/978-3-319-44878-7_4).