Paralelização e Otimização da Simulação Discreta de Eventos em Processador Multicore

Resumo


A simulação é uma maneira de estudar o comportamento de sistemas físicos, em casos onde a solução em laboratório ou analítica são inviáveis. A paralelização de sua execução permite a modelagem de sistemas mais complexos e agiliza suas soluções. Entretanto, a simulação paralela dificulta o respeito às relações de causalidade do sistema físico, acarretando um overhead significativo para assegurar a evolução correta da simulação. Este trabalho apresenta o desenvolvimento de um simulador paralelo de eventos discretos em uma arquitetura multicore de memória compartilhada. Uma extensa avaliação experimental de desempenho analisa questões como a estrutura de dados adotada para a fila de eventos, o impacto da aplicação (topologia da rede de filas e carga de trabalho) na extensão da simulação, a exploração de lookahead da aplicação, as técnicas de avanço do horizonte da simulação e de suspensão do mecanismo gerenciador de threads, e por fim, desempenho e escalabilidade do simulador paralelo. O simulador paralelo obteve um speedup de até 7,01 em relação ao simulador sequencial, em um processador com quatro núcleos físicos e capaz de executar oito threads simultaneamente.

Palavras-chave: Simulação discreta, Simulação paralela, Paralelismo, Processador multicore

Referências

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.
Publicado
30/06/2020
GEHLEN, Tobias; MOREANO, Nahri. Paralelização e Otimização da Simulação Discreta de Eventos em Processador Multicore. In: WORKSHOP EM DESEMPENHO DE SISTEMAS COMPUTACIONAIS E DE COMUNICAÇÃO (WPERFORMANCE), 19. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 25-36. ISSN 2595-6167. DOI: https://doi.org/10.5753/wperformance.2020.11103.