论文摘要
现代GPU由于其超强的计算能力、高速访存带宽、高数据级并行体系结构等特点,作为高性能运算部件在集群计算环境中得到广泛应用,并且GPU异构集群正在逐渐成为高性能计算应用领域的主流分布式计算平台,并使现代计算技术正在逐渐进入数据级并行计算的时代。数据级并行计算能否在实际应用领域得到越来越广泛的采用,不仅仅取决于所设计和实现的数据级并行算法是否能够在当前的硬件计算环境中获取较高的计算能力,更为基础和重要的是所设计和实现的数据级并行算法是否能够同时在系统层面(节点与节点之间)和节点层面(单个节点内部)具有良好的和可持续的可扩展性,即它的性能能够随着计算环境中硬件资源的计算能力和内存带宽的提升而带来几乎线性的性能提升。本文在得到多个研究课题基金资助的研究背景下,对GPU异构集群的系统层面(节点与节点之间)的可扩展性,以及节点层面(单个节点内部)的可扩展性同时展开了较为全面和深入的研究。针对系统层面算法和应用程序的可扩展性问题,本文的主要研究工作如下：(1)基于底层混合编程框架(如CUDA/MPI、OpenACC/MPI)设计并实现了一个具有应用层抽象描述能力、与体系结构具有无关性、支持持续可扩展性等特点的顶层编程框架DISPAR,为GPU异构集群在应用中所面临的核心问题提供一种系统层面有效的解决方案。(2)通过预处理器ATDCM实现DISPAR源代码到底层混合编程框架(如CUDA/MPI、 OpenACC/MPI)的源代码转换,并针对底层混合编程框架提出一种能够考虑系统层面异构性的任务调度策略及相应的辅助算法以最优化系统层面的任务和GPU异构集群计算资源之间的匹配。由于更为直接的性能提升本质上来源于节点层面的应用程序,而电子设计自动化、科学计算等通用计算领域中绝大部分应用程序的性能都受限于其核心操作,如稀疏矩阵操作等。因此在节点层面针对这些核心操作,设计和实现具有可扩展性的高效数据级并行算法是能否充分利用GPU超强计算能力的关键因素。因此,本文同样针对节点层面算法和应用程序的可扩展性问题展开了较为深入的研究。主要研究工作如下：(3)GPU为了提供硬件体系结构层面的可扩展性,其所包含的成百上千个处理单元被组织和划分成多个独立的物理层面的SIMD引擎,且不同的SIMD引擎之间各处理单元之间并没有类似于单个SIMD引擎的相应同步原语。虽然可以通过原子操作提供SIMD引擎之间各处理单元之间的同步能力,但由于原子操作本质上都是串行的,从而将使得相应的并行算法不具备良好的可扩展性。本文基于可扩展性的设计理念,提出通用或特定的技术使得所设计的数据级并行算法具有良好的可扩展性。如基于桶划分预处理技术实现的奇偶合并排序和基数排序以及基于反对角线处理方式的带状矩阵向量乘操作的数据级并行算法不存在任何数据依赖,从而完全避免了同步操作和相应的原子操作,使并行算法具有良好的可扩展性。(4)由于现代GPU能够支持多个内核程序同时执行,因此对于那些即使不具有良好可扩展性的算法,也可以利用本文提出的一种有效的内核程序打包策略用于确定将哪些内核程序打包成单个内核程序能够更加充分地利用GPU的硬件资源。(5)通过对电子设计自动化领域中的时序分析这一重要应用进行可扩展性数据级并行算法的重新设计与改进,以加速电子设计自动化领域关键算法的处理速度,探索可扩展性数据级并行化技术及众核处理机技术在该领域的应用前景。本文通过对基于稀疏矩阵框架的统计静态时序分析提出一种新的稀疏格式ELLV。这种格式不仅使得相应的数据级并行算法的设计较为直接,更为重要的是使得并行算法具有良好的可扩展性。不仅如此,基于ELLV格式实现的Jacobi前条件操作与基于ELLH格式相比能够减少一半的内存访问,并最终带来15%左右的性能提升。
论文目录
目录图目录表目录摘要Abstract第1章 绪论1.1 引言1.2 研究背景及研究现状1.2.1 流媒体处理应用领域的三大特性1.2.2 数据级并行及其主流平台GPU成为程序设计新趋势1.2.3 GPU异构集群成为分布式计算的新趋势1.3 本文的主要研究内容1.4 本文研究工作的创新点1.5 本文组织结构第2章 单GPU及GPU异构集群概述2.1 引言2.2 单GPU的软硬件体系结构及其若干关键应用领域2.2.1 GPU软硬件体系结构的演变历史2.2.2 AMD GPU体系结构及AMD OpenCL编程框架2.2.3 NVIDIA GPU硬件体系结构及其CUDA编程框架2.2.4 两种GPU的软硬件体系结构对比2.2.5 若干关键应用领域的数据级并行算法设计及实现概述2.3 GPU异构集群的软硬件体系结构2.3.1 传统集群编程框架2.3.2 GPU异构集群的系统架构2.3.3 GPU异构集群主流的底层混合编程框架第3章 数据级并行的奇偶合并和基数排序3.1 引言3.2 相关工作3.3 桶划分预处理3.4 奇偶合并排序算法及其数据级并行算法的设计与实现3.4.1 奇偶合并排序概述3.4.2 串行迭代算法直接实现为GPU内核程序时的问题3.4.3 由主机程序控制迭代过程的并行化实现3.4.4 基于桶划分预处理技术的并行化实现3.5 基数排序算法及其数据级并行算法的设计与实现3.5.1 基数排序概述3.5.2 计数排序概述3.6 实验结果与性能分析3.6.1 实验的软硬件环境概述3.6.2 奇偶合并排序3.6.3 基数排序3.7 总结与展望第4章 数据级并行的前条件和时序分析4.1 引言4.2 相关工作4.2.1 并行化稀疏矩阵乘操作4.2.2 并行化前条件操作4.2.3 并行化SSTA算法4.3 前条件和统计静态时序分析概述4.3.1 矩阵条件数和前条件技术概述4.3.2 统计静态时序分析4.4 ELLH和ELLV稀疏矩阵存储格式4.4.1 ELLH格式4.4.2 ELLV格式4.5 并行化CS操作4.6 并行化BCS操作4.7 实验结果与性能分析4.7.1 基于ELLH格式和ELLV格式的CS操作4.7.2 基于CPU和GPU的BCS操作的性能比较4.8 总结与展望第5章 数据级并行的带状矩阵向量乘操作5.1 引言5.2 相关工作5.3 带状矩阵结构及其压缩存储格式概述5.3.1 带状矩阵结构5.3.2 内存空间有效的压缩存储格式5.3.3 带状矩阵和值矩阵之间的元素映射5.4 带状矩阵向量乘操作的数据级并行化算法的设计及实现5.4.1 BpMV操作的通用描述5.4.2 基于压缩存储方案的串行BpMV算法5.4.3 基于压缩存储方案和反对角顺序的并行BpMV算法5.5 分支指令消除优化技术5.5.1 带状矩阵及其压缩存储方案讨论5.5.2 消除判定数组下标越界优化技术5.6 实验结果与性能分析5.7 总结与展望第6章 GPU异构集群的系统级任务调度6.1 引言6.2 相关工作6.2.1 GPU异构集群的系统架构设计6.2.2 GPU能够支持多个内核程序同时执行6.2.3 任务调度策略6.3 GPU异构集群的系统级模型6.3.1 系统级模型6.4 任务分类及其系统级数据结构6.4.1 任务分类6.4.2 系统级的任务及其数据结构6.5 系统级任务调度策略及相应辅助算法6.5.1 系统级任务调度策略概述6.5.2 两个评估任务调度结果的参数定义6.5.3 相应的任务打包和任务调度算法6.6 系统级任务调度实例6.6.1 GPU异构集群的实例及其节点信息6.6.2 系统级任务数据级结构及任务调度过程6.7 总结和展望第7章 DISPAR编程框架的设计及实现7.1 引言7.2 DISPAR顶层编程框架的研究背景7.3 DISPAR顶层编程框架的基本思想和设计哲学7.3.1 对程序设计和开发人员的易用性7.3.2 应用程序性能的可扩展性和可移植性7.3.3 应用程序代码的可重用性7.4 DISPAR顶层编程框架的设计及实现7.4.1 DISPAR顶层编程框架的系统模型7.4.2 DISPAR顶层编程框架的自定义基本数据结构7.4.3 DISPAR顶层编程框架工具集和相应的算法7.5 相关工作7.6 实验结果与性能分析7.6.1 所部署的GPU异构集群的节点信息7.6.2 VNODE的打包和调度过程7.6.3 VNODE的分配结果与性能分析7.7 总结与展望第8章 总结和展望8.1 总结8.2 展望参考文献致谢攻读博士期间发表（录用）论文情况
相关论文文献
标签：众核体系结构论文; 图形处理器论文; 数据级并行论文; 并行处理论文; 排序算法论文;
