Large Scale Model Partitioning For Discrete Event Systems Parallel Simulation

Abstract

Parallel simulation algorithms for discrete-event systems use a model divided into as many parts as required processors, so that each processor simulates a smaller sub-model. For this strategy to efficiently accelerate simulations, two conditions are required: the cost associated with simulating each sub-model must be similar and the communication required between the sub-models should be as minimal as possible. These conditions lead to the model being partitioned by solving a load-balancing problem, which is usually solved using an equivalent graph-theoretic problem: how to split a graph into a given number of sub-graphs such that the sub-graphs have a similar number of vertices and at the same time there is a minimum number of edges between different sub-graphs. In this way, simulations can advance in parallel, and synchronization only becomes necessary when a change occurs in one sub-model that affects the behavior of another sub-model. An essential observation is that large-scale models typically result from the use of regular repetitive structures (equations compactly defined in for loops involving arrays of variables). To exploit this characteristic when representing a model using a graph, the concept of Set-Based Graphs (SBGs) was recently developed. SBGs are graphs in which vertices and edges are grouped into distinct sets that can be represented compactly by comprehension. Thus, when the size of the arrays in a model changes without changing its structure, the representation of the associated SBG remains identical. In this work, we present an adaptation of the classic Kernighan-Lin algorithm that, using the SBG representation, allows for the generation of partitions with a computational cost independent of the size of the arrays of variables defined in the original model.