Parallel discrete event simulation. STW: SWITCH TIME WARP.

M. Serrano, R.L. Suppi, E.Luque

Abstract. Parallel discrete event simulation (PDES), refers to the execution, of a single discrete event simulation program on a parallel computer in order to maximise speedup. The main performance pitfall of Time Warp optimistic synchronisation method, lays on overoptimistic event execution that may lead to a massive rollback production and so, to an inefficient simulation due to an unbalanced LVT advancement. It is likely that the number of LPs required for a simulation will exceed the number of processors available to do simulation. From an static analysis of the system we may be able to obtain the rate relation of one process and its causal predecessors, arriving to an optimal initial process assignment onto the available nodes that, theoretically, provides a balanced initial situation. If a certain speedup can be achieved with one process for processor, we may guarantee the same value for the same number of LPs, but a less number of processors (which means a higher degree of effective utilisation and an improvement on the system performance). Moreover, we may provide scalability to the simulation application, allowing the growth of the application size (an increase on the number of LPs) for the same number of nodes and maintaining the speedup. Then, we propose the STW (Switch Time Warp) mechanism: a dynamic distributed solution (considering arriving messages and also allowing dynamic creation of LPs during simulation time), based not in limiting the optimism but in distributing CPU time among processes in order to adjust their relative rates by balancing the relative execution time of those LPs involved in rollbacks, to achieve the best system simulation time In runtime, an LP is able to locally calculate a cost function value from its event execution speed against the input messages arriving rate, which quantifies somehow the simulation real advancement due to the LP event processing. It only introduces a fixed computation time to the local simulation time. A monitor process (one per node) will determine the LP’s optimal execution order within the node and the amount of CPU time to assign to a process not to further advance its LVT, so slower LPs will benefit. If the system behaviour is constant the results of the simulation execution under our STW monitoring will match the theoretical result. Otherwise, the dynamic schedule adjustment aims to arrive to a result as nearer as possible to the initial static speed balance obtained, but with a little intrusion degree in the system

Key words. PDES, parallel discrete event simulation, SwitchTime Warp, scheduling.

Registration: PIRDI-2/99, February 1999.


Retrieve compressed PostScript document (pirdi11.zip: 108926 bytes)
Copyright © 1999 by Computer Science Department. UAB