Research On Performance Optimization Of Parallel Discrete Event Simulaiton For Complex System Application

The system simulation is an uppermost and effective method to do the research on complex system. With the rapid development of the researches on complexity, the scale of the simulation grows larger and larger, and the behavioral detail of individual model becomes more and more complex, which cause that the computation requirements of large-scale complex system simulation can be hardly satisfied. How to improve the simulation performance, so as to reduce the consumption of the computational resource and afford satisfaction to requirement of running-time limit, is a challenging but important problem. Recently, one solution to this problem is attempted to leverage the parallel discrete event simulation (PDES) methodology to parallelize the simulation by mapping the discrete complex system models onto the LP-based paradigm. However, contrast to traditional PDES application, the complex system application introduces its own characteristics, such as complicate communication structure, dynamic behavior, diversity and so on, which lead the parallel discrete event simulation of complex system to face performance limitations. Considering the characteristics of the complex system application, this dissertation investigates solutions to improve the performance of complex system simulation from various factors which may affect the performance of parallel discrete event simulation, including partitioning, synchronization and interest management. The innovations of this paper are as follows:Firstly, an unbalancing static partitioning algorithm for complex system application with scale-free communication structure is proposed. Since the background load of hosts causes unbalancing constraints associated with the vertices, currently partitioning algorithms based on multilevel k-way partitioning of undirected power-low graph may produce poor-quality solutions. In this paper, a new partitioning algorithm named HApart for the power-law graphs is proposed, in which the hub nodes in the graph are filtered out and assigned to the partitions firstly, and then the k-way partitioning problem could be transformed into a minimum cost assignment problem, the simulation task could be decomposed onto different computing processors with unbalancing constraints by using the new partitioning algorithm. Theoretical analysis shows that this partitioning algorithm is able to approximate the k-way partitioning problem, which is NP-hard, to a ratio of 3, and can be executed in time O((k!+1)?kn)(n is the number of vertices and k is the number of partitions). Experimental results demonstrate that this partitioning algorithm is able to reduce the run-time by 19%.Secondly, a dynamic partitioning algorithm for optimistic synchronization mechanism is proposed. Since current dynamic partitioning algorithms consider computation and communication load balancing isolated, while the optimistic synchronization mechanism introduces new requirements of performance estimates, these algorithms may suffer under complex application background. In this paper, the dynamic partitioning problem is formalized based on graph partitioning model which combine both computation and communication load balancing, and an incremental migration algorithm named ALSPart is proposed, in which computation load is adjusted according to computational resource firstly, then the communication load is optimized by a approximate local-search algorithm based on vertices collection exchange. Experimental results demonstrate that this dynamic partitioning algorithm is able to reduce the cost of rollback by 38%.Thirdly, a hybrid synchronization algorithm based on community detection is proposed. Due to the diversity of individual in complex system, the conservative synchronization mechanism may become limited by sensitivity to lookahead, while the optimistic mechanism appears to be prone to cascading rollbacks. In this paper, with a unified framework for conservative and optimistic synchronization mechanism, a hyrid synchronization algorithm named HCDSyn is proposed, in which community structure is detected by compressing the probability flow of random walk firstly, and one logic process could optimistically choose to be optimistic or conservative by utilizing the community information. The parallelism inherent in simulation system could be exploited by this hybrid mechanism, avoiding cascading rollbacks. Experimental results demonstrate that this hybrid synchronization algorithm is able to reduce the run-time by 10%.Fourthly, a dynamic matching algorithm of hyperspace based on history information is proposed. Since the brute force approach and sort-based approach are time consuming to support large-scale complex system simulation, while the grid-based approach is inaccuracy in filtering, the current matching algorithms are still not good enough to deal with the scenarios that the regions need to be modified along with the simulation advancement frequently. In this paper, a dynamic matching algorithm of hyperspace based on history information named HIMat is proposed, in which the overlapping history information is indexed by a bit vector table for express search, and is used to limit the matching computing only in the area of changing, this algorithm can be executed in time O ( d*k)(d is the number of dimensions in region space and k is average number of ranges that moving region encountered). Experimental results demonstrate that the computational performance of this dynamic matching algorithm is much better than brute force approach and sort-based approach, and is similar to grid-based approach with big cell size, however, grid-based algorithm may generate irrelevant data transmission while the HIMat dynamic matching algorithm derive exact overlapping information.Finally, an open PDES system architecture for complex system application is designed and implemented based on YH-SUPE PDES engine which is developed by our team, and a simulation application to forecast the trend of public opinions under critical condition is used to be an integration testing for our works, the experimental results demonstrate that our work can obtain 35% relative speedup.