Roberto Vitali
Alessandro Pellegrini
Francesco Quaglia
Abstract
Parallel Discrete Event Simulation (PDES) is based on the partitioning of the simulation model into distinct Logical Processes (LPs), each one modeling a portion of the entire system, which are allowed to execute simulation events concurrently. This allows exploiting parallel computing architectures to speedup model execution, and to make very large models tractable. In this article we cope with the optimistic approach to PDES, where LPs are allowed to concurrently process their events in a speculative fashion, and rollback/ recovery techniques are used to guarantee state consistency in case of causality violations along the speculative execution path. Particularly, we present an innovative load sharing approach targeted at optimizing resource usage for fruitful simulation work when running an optimistic PDES environment on top of multi-processor/multi-core machines. Beyond providing the load sharing model, we also define a load sharing oriented architectural scheme, based on a symmetric multi-threaded organization of the simulation platform. Finally, we present a real implementation of the load sharing architecture within the open source ROme OpTimistic Simulator (ROOT-Sim) package. Experimental data for an assessment of both viability and effectiveness of our proposal are presented as well.
- Atlante stradale italia. http://www.automap.it/.Google Scholar
- ACI. Dati e statistiche. http://www.aci.it/?id=54.Google Scholar
- Baltas, N., and Field, T. Continuous performance testing in virtual time. In Proceedings of the 9th International Conference on Quantitative Evaluation of Systems (2012). Google ScholarDigital Library
- Boukerche, A., and Das, S. K. Dynamic load balancing strategies for conservative parallel simulations. In Proceedings of the 11th Workshop on Parallel and Distributed Simulation (1997), pp. 20--28. Google ScholarDigital Library
- Brown, R. Calendar queues: a fast O(1) priority queue implementation for the simulation event set problem. Communications of the ACM 31 (October 1988), 1220--1227. Google ScholarDigital Library
- Carothers, C. D., and Fujimoto, R. M. Efficient Execution of Time Warp Programs on Heterogeneous, NOW Platforms. IEEE Transactions on Parallel and Distributed Systems 11, 3 (2000), 299--317. Google ScholarDigital Library
- Chen, L.-l., Lu, Y.-s., Yao, Y.-P., Peng, S.-l., and Wu, L.-d. A well-balanced time warp system on multi-core environments. In Proceedings of the 2011 IEEE Workshop on Principles of Advanced and Distributed Simulation (2011), PADS, IEEE Computer Society, pp. 1--9. Google ScholarDigital Library
- Dantzig, G. B. Discrete-variable extremum problems. Operational Research, 5 (1957).Google Scholar
- Fujimoto, R. M. Parallel discrete event simulation. Communications of the ACM 33, 10 (Oct. 1990), 30--53. Google ScholarDigital Library
- Glazer, D. W., and Tropper, C. On process migration and load balancing in time warp. IEEE Transactions on Parallel Distributed Systems 4, 3 (1993), 318--327. Google ScholarDigital Library
- Hamada, T., and Nitadori, K. 190 tops astrophysical n-body simulation on a cluster of gpus. In Proceedings of the 2010 ACM/IEEE International Conference on High Performance Computing, Networking, Storage and Analysis (2010), SC, IEEE Computer Society, pp. 1--9. Google ScholarDigital Library
- HPDCS Research Group. ROOT-Sim: The ROme OpTimistic Simulator - v 1.0. http://www.dis.uniroma1.it/~hpdcs/ROOT-Sim/, Oct. 2012.Google Scholar
- Jefferson, D. R. Virtual Time. ACM Transactions on Programming Languages and System 7, 3 (July 1985), 404--425. Google ScholarDigital Library
- Kandukuri, S., and Boyd, S. Optimal power control in interference-limited fading wireless channels with outage-probability specifications. IEEE Transactions on Wireless Communications 1, 1 (2002), 46--55. Google ScholarDigital Library
- Lin, Y.-B., and Lazowska, E. D. Processor scheduling for Time Warp parallel simulation. In Proceedings of the 23rd SCS Multiconference on Advances in Parallel and Distributed Simulation (Jan. 1991), IEEE Computer Society, pp. 11--14.Google Scholar
- Liu, T., Curtsinger, C., and Berger, E. D. DThreads: Effcient deterministic multithread. In Proceedings of the 23rd Symposium on Operating Systems Principles (SOSP 2011) (2011), ACM, pp. 327--336. Google ScholarDigital Library
- Mellon, L., and West, D. Architectural optimizations to advanced distributed simulation. In Proceedings of the 27th conference on Winter simulation (1995), WSC, IEEE Computer Society, pp. 634--641. Google ScholarDigital Library
- Miller, R. J. Optimistic parallel discrete event simulation on a beowulf cluster of multi-core machines. Master's thesis, University of Cincinnati, 2010.Google Scholar
- Park, A., and Fujimoto, R. M. Optimistic parallel simulation over public resource-computing infrastructures and desktop grids. In Proceedings of the 12th IEEE International Symposium on Distributed Simulation and Real Time Applications (2008). Google ScholarDigital Library
- Peluso, S., Didona, D., and Quaglia, F. Application transparent migration of simulation objects with generic memory layout. In Proceedings of the 25th Workshop on Principles of Advanced and Distributed Simulation (june 2011), IEEE Computer Society, pp. 169--177. Google ScholarDigital Library
- per L'Italia S.p.A., A. Reportistica sul traffco. http://www.autostrade.it/studi/studi_traffico.html.Google Scholar
- Quaglia, F., and Cortellessa, V. On the processor scheduling problem in time warp synchronization. ACM Transactions on Modeling and Computer Simulation 12, 3 (July 2002), 143--175. Google ScholarDigital Library
- Vitali, R., Pellegrini, A., and Quaglia, F. Autonomic log/restore for advanced optimistic simulation systems. In Proceedings of the Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (2010), IEEE Computer Society, pp. 319--327. Google ScholarDigital Library
- Weatherly, R. M., Wilson, A. L., Canova, B. S., Page, E. H., Zabek, A. A., and Fischer, M. C. Advanced distributed simulation through the aggregate level simulation protocol. In HICSS (1) (1996), pp. 407--415. Google ScholarDigital Library
Index Terms
- Load sharing for optimistic parallel simulations on multi core machines
Recommendations
Conservative vs. optimistic parallel simulation of DEVS and Cell-DEVS: a comparative study
SCSC '10: Proceedings of the 2010 Summer Computer Simulation ConferenceThe conservative Parallel DEVS protocol offers a novel approach that allows conservative simulation of DEVS-based PDES systems. The protocol is based on the classical Chandy-Misra-Bryant synchronization mechanism, and it extends the DEVS abstract ...
Transparent and Efficient Shared-State Management for Optimistic Simulations on Multi-core Machines
MASCOTS '12: Proceedings of the 2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication SystemsTraditionally, Logical Processes (LPs) forming a simulation model store their execution information into disjoint simulations states, forcing events exchange to communicate data between each other. In this work we propose the design and implementation ...
Comments