Efficient graph-based dynamic load-balancing for parallel large-scale agent-based traffic simulation

One of the issues of parallelizing large-scale agent-based traffic simulations is partitioning and load-balancing. Traffic simulations are dynamic applications where the distribution of workload in the spatial domain constantly changes. Dynamic load-balancing at run-time has shown better efficiency than static partitioning in many studies. However, existing work has only focused on geographic partitioning methods which do not consider the minimization of communication overhead. In this paper, a graph-based dynamic load-balancing mechanism which minimizes the communication overhead during load-balancing operations is developed. Its efficiency is investigated in the agent-based traffic simulator SEMSim Traffic using real world traffic data. Experiment results show that it has significantly better performance than static graph partitioning methods in improving the overall speed of the simulation.