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.
Referências
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.
