有向图并行计算中的多目标剖分算法

作     者：金光浩 莫则尧 JIN Guan-Hao;MO Ze-Yao

作者机构：中国工程物理研究院研究生部北京100088 北京应用物理与计算数学研究所高性能计算中心北京100088 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2005年第28卷第12期

页      面：2045-2051页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：国家杰出青年基金(60425205) 国家自然科学基金(60273030) 中国工程物理研究院双百人才基金资助 

主　　题：有向图 图剖分 并行计算 

摘      要：在以离散网格为基础的某些数值模拟中,网格间的数据依赖关系可以抽象为有向图.如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟并行计算的基础.剖分算法中,需要综合考虑连通性、并行度、负载平衡、通信开销四个目标.文章在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法.应用于二维非结构网格上的柱对称中子输运并行计算中,通量扫描并行算法在该区域剖分算法上获得的并行效率比原来的无向图区域剖分算法高50%以上.