Abstract
We re-examine the problem of load balancing in conservatively synchronized parallel discrete-event simulations (PDES) on high-performance computing clusters. In domains characterized by spatial clustering and geographic "hot-spots," traditional geographic partitioning often leads to severe load imbalances, where a few processors become bottlenecks. We investigate "scatter partitioning," a technique that explicitly assigns neighboring entities to different processors. Despite increased messaging overhead, our results show that scatter partitioning significantly outperforms conventional methods by achieving nearly perfect load balance, often obviating the need for complex dynamic load balancing.
The Challenge of Spatial Clustering in PDES
In conservatively synchronized parallel simulations, the global simulation clock is constrained by the slowest processor. If one processor is overwhelmed with events while others are idle, the entire simulation's progress is halted. Many real-world systems, such as urban transportation networks or power grids, exhibit intense spatial clustering where certain regions generate significantly more simulation events than others.
Standard geographic partitioning—assigning contiguous map regions to specific CPUs—fails in these scenarios. A processor handling a "downtown" area with high activity will be significantly more loaded than one handling "the suburbs," creating a massive performance bottleneck that grinds the entire parallel system to a halt.
Partitioning Strategies
The study compared three primary strategies:
- Geographic Partitioning (Balanced Entities): Divides the domain into regions with an equal number of entities, ignoring actual computational load.
- Geographic Partitioning (Balanced Load): Attempts to divide the domain based on estimated computational load per region.
- Scatter Partitioning: Intentionally assigns neighboring entities to different processors across the cluster. If two intersections are adjacent, they are explicitly sent to different CPUs.
These strategies were evaluated using both an abstracted synthetic model (100,000-node networks) and FastTrans, a high-fidelity transportation microsimulator modeling the North East US with 500,000 nodes and over 25 million vehicular trips.
Results and Insights
The core finding is that on modern High-Performance Computing (HPC) clusters with fast interconnects (e.g., InfiniBand), the cost of inter-processor communication is secondary to the cost of processor idleness.
Load Balancing and Fairness
Scatter partitioning achieved a "fairness ratio" (the ratio of the minimum load to the maximum load across all CPUs) of approximately 0.99, indicating nearly perfect distribution. In contrast, geographic partitioning often resulted in ratios below 0.01.
Performance Gains
In the FastTrans simulation, scatter partitioning delivered nearly an order of magnitude speedup in execution time compared to geographic partitioning. While it generated roughly 10x more inter-processor messages, the elimination of computational bottlenecks far outweighed this overhead. Furthermore, scatter partitioning demonstrated superior strong scaling, continuing to improve performance up to 512 processors, whereas geographic methods plateaued much earlier.
Conclusion
Spatial scattering provides a robust, static solution for load balancing in simulations with clustered activity. By ensuring equitable CPU load, it can often eliminate the need for difficult-to-implement dynamic load balancing schemes. Future work will explore its applicability in other simulation domains and its sensitivity to network interconnect performance.
Summary updated