Partitioning on Dynamic Behavior for Parallel Discrete Event Simulation

Partitioning plays an important role in PDES performance due to the high communication cost in parallel platforms and the fine-granularity of most simulation models. Traditionally, models are partitioned by deriving the static communication graph of objects and applying graph partitioning to reduce the mincut while load balancing the number of objects. However, many, if not all, models exhibit great diversity in their dynamic behavior: objects communicate with each other with diverse frequencies that are commonly power-law distributed. Similar diversity exists in the activity of objects and the processing requirements of events. In this paper, we argue that partitioning based on static graphs ignores these effects, leading to poor partitioning. We explore how partitioning based on dynamic information should be approached and explore policies that focus on communication cost, load balancing and both. We show that on multicore clusters, dynamic partitioning achieves up to 4x better performance than static partitioning. On the AMD magnycours, where the communication latency is low, dynamic partitioning results in a 2x performance improvement over static partitioning for some of our models. Our future work considers how to derive the dynamic weights (in this study, we do that through profiling), and how to balance the importance of communication and computation in a way that is informed by the underlying architecture.