• Gabriele D'Angelo
• Stefano Ferretti
• Moreno Marzolla

Parallel And Distributed Simulation (PADS) is a modeling paradigm that enables efficient implementation of large simulation models represented as a collection of interacting entities, called Simulate Entities (SEs). To speed up the simulation, SEs are assigned to independent execution units for parallel execution. Finding the best strategy for allocating SEs to execution units is one of the most important problems in PADS. Ideally, highly interacting SEs should be placed on the same execution unit so that all communications remain local. However, placing too many SEs on the same execution unit would degrade performance, effectively creating a bottleneck for the entire simulation execution. The problem is further complicated by the fact that many simulation models exhibit non-uniform computation and communication patterns among their components, which can change dynamically at unpredictable times during execution. In this paper, we propose a self-clustering heuristic based on the migration of SEs within the PADS execution architecture. The heuristic is designed to identify and exploit communication locality, with the aim of reducing the communication cost during execution. It adapts automatically to changing interaction patterns by migrating SEs, without imposing strict assumptions on the simulation model and while supporting highly heterogeneous execution platforms. A set of tunable parameters allows users to find the best balance between the gain obtained by clustering highly interacting SEs and the cost of running the heuristic and performing the migrations. We conduct an extensive set of computational experiments to assess the effectiveness of the heuristic on a representative simulation scenario, evaluating the role of the main parameters with the aim of guiding users in selecting optimal values, supporting the development of more advanced heuristics, and providing insights into the definition of fully self-tuning mechanisms.

• Parallel and Distributed Simulation, Discrete Event Simulation, Model Partitioning, Clustering Heuristics.

• Submitted for peer-review to an international journal.

• Simulation model source code, scripts and raw data are available at this link