可扩展数据驱动并行算法研究及应用

论文摘要

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

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景与意义
• 1.2 研究动态
• 1.3 论文主要贡献
• 1.4 论文组织结构
• 1.5 预备知识、相关记号和术语
• 1.6 本文计算环境
• 第二章 数据驱动计算模型
• 2.1 数据驱动计算模型
• 2.1.1 定义
• 2.1.2 可计算条件
• 2.1.3 基于模型的数据驱动串行计算
• 2.2 数据驱动计算建模
• 2.2.1 从实际应用中抽取有向图
• 2.2.2 有向数据依赖关系应用计算与数据驱动计算的等价关系
• 2.3 模型分类
• 2.4 小结
• 第三章 数据驱动并行算法
• 3.1 概述
• 3.2 有向图剖分
• 3.2.1 P-路图剖分
• 3.2.2 P-路图剖分到处理器的映射
• 3.2.3 有向图剖分算法
• 3.3 结点优先级策略
• 3.3.1 最优调度问题
• 3.3.2 优先级策略介绍
• 3.4 并行流水线算法
• 3.4.1 并行流水线算法
• 3.4.2 并行流水线算法终止条件
• 3.5 小结
• 第四章 数据驱动并行算法性能评价
• 4.1 算法评价准则
• 4.1.1 理想加速比
• 4.1.2 算法加速比
• 4.1.3 实测加速比
• 4.2 关键性能因素
• 4.2.1 通信延迟
• 4.2.2 结点粒度
• 4.3 小结
• 第五章 在辐射输运计算中的应用
• 5.1 LARED-R-1程序介绍
• 5.1.1 辐射输运方程
• 5.1.2 数值方法
• 5.2 并行实现方案
• 5.3 通量扫描并行计算
• 5.3.1 数据驱动计算模型
• 5.3.2 有向图剖分
• 5.3.3 优先级策略
• 5.3.4 并行流水线算法
• 5.4 数值实验
• 5.4.1 并行流水线性能
• 5.4.2 整体并行性能
• 5.5 小结
• 第六章 一种新的结点优先级策略
• 6.1 新的优先级策略CAP-FB
• 6.1.1 顺逆交替迭代技术
• 6.1.2 截弧优先策略
• 6.1.3 算法流程与示例
• 6.2 算法并行实现
• 6.3 算法收敛性证明
• 6.4 数值实验
• 6.4.1 模型案例测试
• 6.4.2 实际应用测试
• 6.5 小结
• 第七章 JASMIN框架中数据驱动并行算法实现
• 7.1 面向JASMIN框架的设计思想
• 7.2 在JASMIN框架中的实现
• 7.2.1 数据驱动并行计算模块
• 7.2.2 扫描构件模块
• 7.3 基于框架的应用示例
• 7.3.1 隐式迎风格式求解中子输运方程
• 7.3.2 基于框架的实现
• 7.4 应用测试
• 7.4.1 串行性能
• 7.4.2 并行性能
• 7.5 小结
• 第八章 总结和展望
• 参考文献
• 完成论文
• 个人简历
• 致谢