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

莫则尧1金光浩2

1.中国工程物理研究院; 2.北京应用物理与计算数学研究所;

摘要：

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

关键词：有向图、图剖分、并行计算

所属期刊栏目：28

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金60425205;中国科学院资助项目60273030;中国工程物理研究院基金

在线出版日期：2006-02-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：2045-2051