论文部分内容阅读
在高性能科学计算中,计算区域通常被离散成网格,微分方程在网格上由计算方法离散。从相邻网格间数据依赖关系的角度,计算方法可以分为两种类型:无向数据依赖和有向数据依赖。对于前者,网格单元的计算可以通过引用相邻网格单元的已知量而独立进行;对于后者,网格单元的计算依赖于某些相邻网格单元的最新计算结果,也就是说,只有所有这些相邻网格单元计算完毕,才能开始该网格单元的计算。对无向数据依赖的计算方法,计算区域可以分解为多个子区域并分配到不同处理器中,高效并行算法可以按粗粒度的BSP模型进行设计。但是,对有向数据依赖的计算方法,这种并行算法设计模式无法适应,需要考虑细粒度的并行计算模型和相应的并行算法。细粒度的并行计算对并行机的通信延迟提出了很高的要求,但是,随着现代高性能计算机的快速发展,处理器间的通信延迟可以降低到几个微秒,这使得细粒度的高效有向数据依赖并行算法的设计成为可能。本文以求解粒子输运方程的离散纵标(S_N)计算方法及其它若干有向数据依赖关系计算方法为背景,围绕刻画有向数据依赖关系的并行计算模型、基于模型的通用并行算法、并行算法的性能优化、并行算法的实际应用等方面进行了系统深入的研究,取得如下主要研究成果:(一)通过分析典型科学计算应用计算方法的有向数据依赖关系,基于有向图,归纳总结并提出了一种刻画有向数据依赖关系的数据驱动并行计算模型,将计算方法的并行计算问题等价地转化为模型的并行计算问题。(二)针对数据驱动并行计算模型,提出了统一形式的数据驱动并行算法,以及相应的性能评价方法。该算法由三部分组成:有向图剖分、结点优先级策略和并行流水线算法。(三)针对二维辐射输运问题,实现具体的数据驱动并行算法,通过对程序LARED-R-1的并行化,在上百个处理器上,取得了可扩展的并行性能。(四)针对数据驱动并行算法,提出一种具有普适性的新的结点优先级策略,可用于充分挖掘并行度。理论证明和实际应用表明,该策略在数百个处理器上效果明显。(五)针对并行自适应结构网格应用支撑软件框架(JASMIN),提出并实现了适合数据驱动并行算法的三层软件体系结构。该体系结构大幅降低了有向数据依赖关系计算方法并行程序的研制难度。并且2048个处理器上的性能测试表明,这种实现是相当有效的。