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

摘要

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