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

Multi-Objective Partitioning Method for Parallel Computation of Directed Graph

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

In some grid-based numerical simulation applications, the data dependence relationship between neighboring zones can be depicted by directed graphs. It is essential that for parallel computing of such simulations on how to partition the directed graph into multiple subgraphs to map the simulation to processors. The partitioning method should well leverage four objectives such that connectivity, parallelism, load balance and communicational overheads. This paper presents a method towards to tradeoff on these four objectives. The numerical experiments for parallel solution of two-dimensional neutron transport equation on cylindrically unstructured grid show that the parallel efficiency on this method is superior to that on the usual partitioning method derived from undirected graph by 50%.