CAJ | 학술논문

动态负载划分是提高并行离散事件仿真运行性能的有效途径之一.现有研究往往孤立地考虑计算负载平衡和通信负载优化,使得复杂应用背景下整体性能低下.论文综合考虑仿真模型计算负载和交互模式,提出了一个基于带权重无向图有限容量k划分问题的并行离散事件仿真负载划分模型,并配合一套通用的仿真运行性能度量方法,提出了一个基于顶点交换的启发式局部搜索近似划分算法,实现了在计算负载平衡的前提下系统通信负载最优化,其近似解与全局最优解比值不小于(1-1/|N|)(1-ε).实验证明了该动态负载划分算法的有效性和实用性.
동태부재화분시제고병행리산사건방진운행성능적유효도경지일.현유연구왕왕고입지고필계산부재평형화통신부재우화,사득복잡응용배경하정체성능저하.논문종합고필방진모형계산부재화교호모식,제출료일개기우대권중무향도유한용량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.