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

Xu, Yadong; Wentong Cai; Aydt, Heiko; Lees, Michael · 2014 · Crossref

DOI: 10.1109/wsc.2014.7020180

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of efficient parallelization in large-scale agent-based traffic simulations, specifically focusing on dynamic load-balancing. Traffic simulations are inherently dynamic, with workload distributions shifting constantly as agents move through the road network. While static partitioning methods often fail to maintain balance during peak traffic hours, existing dynamic approaches typically rely on geographic partitioning, which ignores communication overhead. The authors propose a graph-based dynamic load-balancing mechanism that simultaneously minimizes workload imbalance and inter-process communication costs, aiming to improve overall simulation speed. The study utilizes the SEMSim Traffic simulator, a nanoscopic agent-based model, to evaluate the proposed method. The experimental setup involves a real-world scenario using the entire road network of Singapore, comprising 43,392 nodes and 84,343 links, with approximately 1.2 million trips generated from Household Interview and Travel Survey data. The simulation runs on a cluster of four compute nodes connected via InfiniBand. The proposed mechanism employs a master-slave architecture where the master process periodically monitors workload imbalance. When the imbalance exceeds a specific threshold, a multilevel k-way graph partitioning algorithm generates new partitions. To minimize data redistribution costs, a mapping strategy aligns new partitions with old ones based on agent similarity. This approach is compared against two static partitioning baselines: one using only network topology and another using pre-generated average traffic flow data. The results demonstrate that the dynamic load-balancing mechanism significantly outperforms static methods. Workload imbalance was substantially lower in the dynamic approach, particularly during morning and evening peak hours when traffic volume fluctuates rapidly. For instance, with four processes, the average imbalance dropped from over 3,200 agents in static methods to under 420 agents in the dynamic method with a threshold of 1,000. Furthermore, the graph-based approach reduced the total number of migrated agents, indicating lower communication overhead compared to static partitioning. Although the dynamic method introduces computational overhead for repartitioning, the authors found that appropriate threshold settings (e.g., 500 or 1,000 agents) kept this overhead manageable while delivering significant performance gains. The significance of this work lies in demonstrating that graph-based dynamic load-balancing is viable and superior for parallel traffic simulations. By considering both computational load and communication costs, the method achieves better speed-up than static graph partitioning and geographic dynamic methods. This approach enables more efficient large-scale simulations of complex transportation systems, such as those required for studying the impact of electric vehicles or autonomous driving in mega-cities. The findings suggest that incorporating graph partitioning into dynamic load-balancing strategies is essential for optimizing parallel discrete-event simulations where workload distribution is highly irregular and time-dependent.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• traffic density