Explicit Spatial Scattering for Load Balancing in Conservatively Synchronized Parallel Discrete Event Simulations

Sunil Thulasidasan, Shiva Prasad Kasiviswanathan, Stephan J. Eidenbenz, Philip RomeroPADS 2010 · OpenReview

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.

Exponentially distributed load showing significant spatial clustering and hot-spots.

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:

  1. Geographic Partitioning (Balanced Entities): Divides the domain into regions with an equal number of entities, ignoring actual computational load.
  2. Geographic Partitioning (Balanced Load): Attempts to divide the domain based on estimated computational load per region.
  3. 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.

Balanced processor load distribution achieved through scatter partitioning.

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

Abstract

We re-examine the problem of load balancing in conservatively synchronized parallel, discrete- event simulations executed on high-performance computing clusters, focusing on simulations where computational and messaging load tend to be spatially clustered. Such domains are frequently characterized by the presence of geographic "hot-spots'' - regions that generate significantly more simulation events than others. Examples of such domains include simulation of urban regions, transportation networks and networks where interaction between entities is often constrained by physical proximity. Noting that in conservatively synchronized parallel simulations, the speed of execution of the simulation is determined by the slowest ( i.e most heavily loaded) simulation process, we study different partitioning strategies in achieving equitable processor-load distribution in domains with spatially clustered load. In particular, we study the effectiveness of partitioning via spatial scattering to achieve optimal load balance. In this partitioning technique, nearby entities are explicitly assigned to different processors, thereby scattering the load across the cluster. This is motivated by two observations, namely, (i) since load is spatially clustered, spatial scattering should, intuitively, spread the load across the compute cluster, and (ii) in parallel simulations, equitable distribution of CPU load is a greater determinant of execution speed than message passing overhead. Through large-scale simulation experiments - both of abstracted and real simulation models - on high performance clusters, we observe that scatter partitioning - even with its greatly increased messaging overhead - often significantly outperforms more conventional spatial partitioning techniques that seek to reduce messaging overhead. Further, even if hot-spots change over the course of the simulation, if the underlying feature of spatial clustering is retained, load continues to be balanced with spatial scattering leading us to the observation that spatial scattering can often obviate the need for dynamic load balancing.
BibTeX
@inproceedings{thulasidasan2010explicit,
  author = {Sunil Thulasidasan and Shiva Prasad Kasiviswanathan and Stephan J. Eidenbenz and Philip Romero},
  title = {{Explicit Spatial Scattering for Load Balancing in Conservatively Synchronized Parallel Discrete Event Simulations}},
  booktitle = {PADS},
  year = {2010},
  url = {https://openreview.net/forum?id=stQnTKi6K6},
}
Figure