在以离散网格为基础的科学计算数值模拟中,在某些情形下,网格间的计算顺序是单方向数据依赖的,这种依赖关系可以抽象为有向图。于是,这类科学数值模拟的并行计算可以抽象成为有向图的并行计算问题。如何剖分这些有向图成多个子图,将各子图对应的数值模拟任务映射到不同的处理机,是该类数值模拟有向图并行计算的基础。有向图并行计算可分解为三个部分,有向图剖分算法、结点的优先级算法和基于有向图剖分算法和结点优先级算法的扫描并行算法。有向图剖分算法中,我们需要综合考虑连通性、并行度、负载平衡、通信开销四个目标。本文在传统有向图剖分算法的基础上,提出了一个权衡这四个目标的有向图多目标剖分区域分解算法。应用于二维非结构网格上的柱对称中子输运并行计算中,基于该剖分算法的通量扫描并行算法的并行效率比基于非结构网格无向图剖分区域分解的相应并行算法的并行效率有明显的提高。具体分为六章。 第一章简单分析离散网格为基础的科学数值模拟中有向图剖分的应用,指出了开展多目标剖分区域分解算法研究的必要性,总结了有向图剖分算法的发展状况和以往有向图剖分算法的不足。最后,简述了本文的主要工作。 第二章介绍有向图并行计算的基本概念、有向图并行计算的评判准则和基于区域分解的扫描并行算法。 第三章介绍有向图的结点优先级算法。 第四章介绍多目标剖分区域分解算法,即如何根据图中结点的单方向数据依赖关系,将图剖分成P个子图,分配给P台不同的处理机,使得基于图剖分的扫描并行算法获得最高的并行效率。我们将相邻结点引入多目标剖分区域分解算法之后,相应地引入三个新概念,从而改进多目标剖分区域分解算法。 第五章利用扫描并行算法对Iterative Kernigham-Lin(IKL)方法和改进前后多目标剖分区域分解算法给出的剖分进行比较,并对结果进行具体分析。实验结果表明我们的多目标剖分区域分解算法达到了预期的目标,并且某些性质方面比IKL方法有更好的效果,而改进后的算法比改进前的多目标剖分区域分解算法有更好的效果。 第六章为结束语,总结了全文工作,展望了将来的研究重点。