Hierarchical Dynamic Multilevel Graph Partitioning for Load Balancing in Distributed Agent-Based Simulations

• Cristina Peralta Quesada Universitat Autònoma de Barcelona
• EduardoCésar Galobardes Universitat Autònoma de Barcelona
• Andreu Moreno Vendrell Universitat Autònoma de Barcelona
• Anna Sikora Universitat Autònoma de Barcelona

Resumo

Applications handling massive graphs deployed within distributed High-Performance Computing (HPC) systems require careful allocation of vertices across processing elements (PEs) to maximize the utilization of the available resources. This allocation should minimize the number of edges cut between PEs while ensuring a balanced workload. Different graph partitioning tools are available to address this issue, providing both static and dynamic methods for efficiently distributing the application graph across the system.Among existing partitioners, multilevel graph partitioning (MGP) approaches produce high-quality partitions with even workload distribution across PEs while minimizing inter-process communication. However, state-of-the-art MGP frameworks such as Zoltan and ParMETIS often struggle with real-world networks. Although ParHIP provides better support for these cases, it lacks dynamic workload balancing, making it unsuitable for dynamic graphs.This paper presents a novel methodology for a distributed, hierarchical, and dynamic multilevel graph partitioning (HDMGP) framework designed for load-balancing large-scale simulations handling real-world graphs. The HDMGP framework is validated through a proof of concept implementation using ParHIP as a baseline. Initial tests demonstrate that the tool maintains repartition quality comparable to the baseline MGP while achieving a repartitioning time up to 8,8 times faster than recomputing the entire graph partition.

Palavras-chave: Adaptation models, Runtime, Adaptive systems, High performance computing, Computer architecture, Load management, Agent-based modeling, Resource management, Load modeling, Testing, High-Performance Computing (HPC), Multilevel Graph Partitioning, Dynamic Load Balancing, Agent-Based Modeling and Simulation (ABMS)