Research On Static Load Balancing Of Parallel Discrete Event Simulation Based On Graph Partitioning

Complex system simulation contains a large number of entities and the load balancing based on entities distribution impacts the efficiency of parallel discrete event simulation(PDES).As for static load balancing of PDES,graph partitioning algorithm is a major research direction.However,most present static load balancing technologies based on graph partitioning lack uniform description of entities' computation and interaction,which leads to inadequate consideration of dynamic running characteristics of entities.As a result,the load partitioning is imbalanced,restricting the running efficiency of PDES.Therefore,it is theoretically and practically meaningful to conduct research on static load balancing of PDES based on graph partitioning,whereby improving the balance of load partitioning and the efficiency of PDES applications.Based on synthetic analysis of related work and aiming at effective improvement of load balancing,this paper mainly conducts research on PDES-oriented parameterized simulation of entity computation and interaction load,static graph partitioning of PDES applications based on vector weights and static graph partitioning of PDES applications based on ant colony algorithm.The innovations of this paper are concluded as follows:1)Most present load partitioning algorithms require repeat running of the actual PDES applications to obtain running information for optimization,which will be time-consuming for complex system simulation.Accordingly,this paper proposes a technology on PDES-oriented parameterized simulation of entity computation and interaction load.Specifically,this technology is an extension of classical Phold benchmark,which regulates the Phold to mimic the behaviors of entities by setting related parameters.Thereby,the running of actual applications can be replaced by the faster simulation of parameterized Phold,which provides an efficient benchmark for evaluating and optimizing load balancing algorithms.The test results showed that the proposed method can effectively simulate different computation and communication loading of entities.2)Graph partitioning algorithm is an important resort for PDES-oriented static load balancing.Generally,the vertex and the edge respectively represents the computation and communication of the entity.Most present graph structures use fixed values to represent the weights of vertices and edges,which loses most dynamic running information of entities,reducing the balance of load partitioning.To narrow the gap between entities' dynamic behaviors and static graph structures,this paper proposes a technology on static graph partitioning based on vector weights.Specifically,the weights of vertices and edges are represented by vectors which are calculated according to different simulation intervals.The test results showed that this technology achieved speedup of 1.551 in simulated experiments,which outperforms the original graph partitioning algorithm by 22%.3)Most present graph partitioning algorithms conduct partitioning in random or greedy ways,lacking reasonable consideration of entities' dynamic information and global balancing.Accordingly,this paper proposes a technology on static graph partitioning based on ant colony algorithm.Specifically,this technology utilizes the global searching advantage of ant colony algorithm,whereby improving the overall balance of the load partitioning.The test results showed that the proposed technology achieved speedup of 1.677 in simulated experiments,which is superior to graph partitioning algorithms based on fixed-value weights and vector weights,respectively reaching 32% improvement and 8% improvement.Based on the aforementioned three technologies,this paper designs and implements static load balancing of PDES based on graph partitioning.To test and evaluate the synthetic performance of the proposed method,a real PDES application is introduced.The test results showed that the static graph partitioning algorithms based on vector weights and based on ant colony algorithm respectively achieved speedups of 1.30 and 1.34,both outperforming the original graph partitioning algorithm by 4% and 7%.