In classical parallel discrete-event simulation, the simulation state space is decomposed into a number of sub-spaces. The responsibility for the simulation of each sub-space is assigned to a separate parallel process and simulation is performed concurrently by the parallel processes. This is also referred to as spatial parallelization. To allow for an efficient parallel simulation, a suitable decomposition has to be found, where parallel processes are largely independent of one another. This is not always possible, as the spatial decomposability of a model might be limited, depending on the specificities of the model state space. Time-parallel simulation is another approach, where each of the parallel processes is responsible for the simulation of the whole state space, but only for a part of the overall simulation time interval (also referred to as temporal parallelization). The simulated time is decomposed into a number of time slices and the calculations corresponding to each slice are assigned to a separate parallel process. The central problem of this approach are the initial states of the parallel simulations, as these are unknown prior to the simulation execution. The advantages of time-parallel simulation are the achievable parallelism and a high degree of independence between parallel processes.
Most of the existing approaches for parallel simulation only consider accurate parallelization methods, i.e. methods ensuring identical results of the parallel simulation and a corresponding sequential simulation. However, in many cases, no satisfying degree of parallelism can be achieved with accurate parallelization approaches, due to interdependencies between parallel processes. As an alternative, approximate parallel simulation methods are constructed to tolerate a deviation of parallel simulation results from those of a corresponding sequential simulation, giving the opportunity for an efficient parallel simulation. Without a fundamental analysis of the error introduced with the approximation, simulation results might be seriously compromised. In this thesis, the applicability of approximate methods to the approach of time-parallel simulation is examined. A formal model of time-parallel simulation is introduced and used as a basis for the definition of the approximate parallel simulation method. Furthermore, the approximate time-parallel simulation approach is enhanced to a new parallel simulation approach. This progressive time-parallel simulation is intended to provide imprecise simulation results quickly, improving these results progressively in the continued simulation execution. For a thorough examination of the proposed approaches, three case studies are performed: queuing systems, simulation of caching in computer systems, and road traffic simulation. Theoretical considerations indicate the feasibility of the approximate time-parallel simulation methods, as do experiments with prototypical implementations of approximate simulators.
«In classical parallel discrete-event simulation, the simulation state space is decomposed into a number of sub-spaces. The responsibility for the simulation of each sub-space is assigned to a separate parallel process and simulation is performed concurrently by the parallel processes. This is also referred to as spatial parallelization. To allow for an efficient parallel simulation, a suitable decomposition has to be found, where parallel processes are largely independent of one another. This is...
»
Login
BibTeX