Simultaneous parallel simulations of continuous time Markov chains at multiple parameter settings

Abstract

The authors describe multi-PUCS (parallel uniformized continuous-time simulation), an approach based on uniformization for simultaneously running parallel simulation of CTMCs (continuous time Markov chains) at multiple parameter settings. In multi-PUCs, interprocessor communications messages are shared among the multiple simulations. The efficiency of multi-PUCS relative to another multiple parameter simulation approach, the consecutive strategy, was studied empirically through simulations of a large queuing network on a 16-node Intel iPSC/2. Generally speaking, if the parameter being varied is such that the external uniformization rates are unaffected, then multi-PUCS becomes (relatively) more efficient as the amount of interprocessor communications increases. However, the efficiency gains over the consecutive strategy were fairly modest when combining two parameter settings. Better performance can be achieved when more parameter settings are included. In addition, moderate positive correlation was induced using this approach.