Parallelization and Optimization of the Discrete Event Simulation in a Multicore Processor

• Tobias Gehlen UFMS http://orcid.org/0000-0002-9464-6624
• Nahri Moreano UFMS http://orcid.org/0000-0001-8305-4677

DOI: https://doi.org/10.5753/wperformance.2020.11103

Abstract

Simulation is used to study the behavior of physical systems. Parallelsimulation accelerates the solution of these systems, but it causes overhead toensure respect for the causality relations of the system. This work presentsthe project and implementation of a parallel discrete event simulator in amulticore architecture with shared memory. We examine issues as data structurefor the event queue, impact of application workload, lookahead exploitation,techniques for advancing the simulation horizon and suspending the managermechanism, performance, and scalability. The parallel simulator achievedspeedups up to 7.01, when compared to the sequential simulator, on a processorwith four cores and capable of executing eight threads simultaneously.

Keywords: Discrete simulation, Parallel simulation, Parallelism, Multicore processor

References

Ahmed, M. G., Pattalwar, S. V., and Thakare, V. M. (2012). Parallel discrete eventsimulation based on multi-core platform – a new approach. International Journal of Computer Applications – Proceedings of the National Conference on Innovative Paradigms in Engineering and Technology, NCIPET(11):12–16.

Banks, J. et al. (2010).Discrete-event system simulation. Prentice Hall, 5 edition.

Chandy, K. M. and Misra, J. (1981). Asynchronous distributed simulation via a sequenceof parallel computations.Communications of the ACM, 24(4):198–206.

De Munck, S., Vanmechelen, K., and Broeckhove, J. (2010). Design and performanceevaluation of a conservative parallel discrete event core for GES. In Proceedings of the International Conference on Simulation Tools and Techniques, pages 1–10.

Fujimoto, R. M. (2000).Parallel and distributed simulation systems. John Wiley & Sons.

Fujimoto, R. M. (2015). Parallel and distributed simulation. In Proceedings of the Winter Simulation Conference, pages 45–59.

Jefferson, D. R. (1985). Virtual time. ACM Transactions on Programming Languages and Systems, 7(3):404–425.

Law, A. M. and Kelton, W. D. (2015). Simulation modeling and analysis. McGraw-Hill.

Liu, J. (2009). Parallel discrete-event simulation. Technical report, School of Computing and Information Sciences, Florida International University.

Misra, J. (1986).Distributed discrete-event simulation. ACM Computing Surveys,18(1):39–65.

OpenMP Architecture Review Board (2020). The OpenMP API specification for parallelprogramming. https://www.openmp.org/. (accessado em janeiro 2020).

Ristov, S., Prodan, R., Gusev, M., and Skala, K. (2016). Superlinear speedup in HPC systems: why and when? In Proceedings of the Federated Conference on Computer Science and Information Systems, pages 889–898.

Sokolowski, J. and Banks, C., editors (2010). Modeling and simulation fundamentals. John Wiley & Sons.

Wagner, D. B., Lazowska, E. D., and Bershad, B. N. (1989). Techniques for efficient shared-memory parallel simulation. In Proceedings of the SCS Multiconference on Distributed Simulation, pages 29–37.