集群计算环境下基于复杂网络的社会学仿真负载划分优化算法

作     者：姚益平 张颖星 Yao Yiping;Zhang Yingxing

作者机构：国防科学技术大学计算机学院长沙410073 

出 版 物：《计算机研究与发展》 (Journal of Computer Research and Development)

年 卷 期：2011年第48卷第9期

页      面：1759-1767页

核心收录：

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

基　　金：国家自然科学基金项目(60773019) 高等学校博士学科点专项科研基金项目(200899980004) 

主　　题：负载划分 社会学仿真 复杂网络 并行离散事件仿真 图划分 

摘      要：负载划分是决定集群计算环境下基于复杂网络的并行社会学仿真性能的核心因素之一.由于背景负载等因素的影响,集群系统中往往需要根据实际可用计算资源非均匀分配仿真任务,而现有针对无标度特性拓扑结构的并行仿真负载划分算法无法适应集群环境下计算负载非均匀划分的需求.针对这一问题,提出了一个基于集散节点聚合的负载划分算法,将集群计算环境下基于复杂网络的并行社会学仿真负载划分优化问题转换为一个二部图最小代价赋值问题,最终得到仿真任务到计算节点的分配方案.理论证明该算法近似解与全局最优解比值不超过3,时间复杂度不超过O((k!+1)·kn).实验结果表明该负载划分算法相比现有算法平均提高18.8%的仿真运行性能,证明了该算法的有效性和实用性.