Compositional Construction of Importance Functions in Fully Automated Importance Splitting

TitleCompositional Construction of Importance Functions in Fully Automated Importance Splitting
Publication TypeBook Chapter
Year of Publication2017
AuthorsBudde, CE, D'Argenio, PR, Monti, RE
EditorPuliafito, A, Trivedi, KS, Tuffin, B, Scarpa, M, Machida, F, Alonso, J
Book Title10th EAI International Conference on Performance Evaluation Methodologies and Tools {VALUETOOLS 2016}
PublisherACM
ISBN Number978-1-63190-141-6
Keywordsdiscrete-event simulation, modeling and simulation, rare-event simulation
AbstractImportance 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.
URLhttp://dx.doi.org/10.4108/eai.25-10-2016.2266501
DOI10.4108/eai.25-10-2016.2266501
PDF (Full text):