中文摘要：

动态负载划分是提高并行离散事件仿真运行性能的有效途径之一．现有研究往往孤立地考虑计算负载平衡和通信负载优化，使得复杂应用背景下整体性能低下．论文综合考虑仿真模型计算负载和交互模式，提出了一个基于带权重无向图有限容量k划分问题的并行离散事件仿真负载划分模型，并配合一套通用的仿真运行性能度量方法，提出了一个基于顶点交换的启发式局部搜索近似划分算法，实现了在计算负载平衡的前提下系统通信负载最优化，其近似解与全局最优解比值不小于（1—1／｜N｜）（1-ε）．实验证明了该动态负载划分算法的有效性和实用性．

英文摘要：

With the rise of simulation platforms which support efficiently migration, the dynamic partitioning mechanism can significantly improve performance of the PDES. How to estimate and optimize the communication structure becomes an essential research topic for dynamic partitioning. Currently, there are several dynamic partitioning algorithms. Since they consider computation and communication load balancing isolated, these algorithms may suffer under complex application background. This paper formalizes the dynamic partitioning problem statement which combine both computation and communication load balancing, and proposes an algorithm based on approximate local search, which obtains a solution with value no smaller than （1-1/｜N｜）（1-ε）of the optimal solution value in polynomial time complexity. The experiments show that the algorithm has high performance and low overhead.