流体系结构的编译技术研究 ——面向科学计算程序的编译优化

论文摘要

流体系结构是一种致力于缓解存储墙问题的新型体系结构,它综合利用大量的运算单元、有效的多级存储层次和多种并行技术,在媒体处理和信号处理等领域都获得了很高的性能。科学计算领域对高性能计算的需求巨大,其应用程序同样具有流应用的部分特征,因此如何采用流体系结构加速科学计算程序是值得深入研究的问题。现有面向媒体应用的流编译系统没有针对科学计算程序的特性进行优化,无法保证科学计算流程序的高效性。为了使科学计算程序能够充分发挥流体系结构的性能优势,我们开发了面向科学计算的SF95流编程语言和SF95Compiler流编译器。本课题研究了流体系结构上面向科学计算程序的编译优化技术,重点针对SF95Compiler编译框架中的流变换、代码优化和科学计算函数库三个关键部分进行了研究,并以典型流体系结构Imagine为平台,在SF95Compiler流编译器中实现和验证了论文所提出的优化算法。论文的创新工作主要体现在以下五个方面:(1)提出了基于D&C矩阵的优化流变换技术。流变换是一种从SF95程序到流程序中间代码的源到源转换过程。最简单的直接流变换方法不采用任何面向体系结构的程序变换优化,生成的流程序非常低效。为此,论文深入研究了面向流体系结构的循环变换和数据变换方法,提出了一种新的基于D&C矩阵的优化流变换技术。该技术的研究重点包括以下三个方面。首先将源程序中循环和数组的关系抽象成为一种新的中间表示——数据计算矩阵(Data&Computation矩阵,简称D&C矩阵)。然后,基于D&C矩阵变换,提出了优化流变换所采用的三种关键技术:粗粒度程序变换、细粒度程序变换和流组织优化技术。最后,设计了基于D&C矩阵的优化流变换算法。实验结果表明,基于D&C矩阵的优化流变换技术能够获得良好的指令级和数据级并行性,以及LRF和SRF局部性。与直接流变换技术相比,该优化流变换技术能够获得2.76的平均加速比。(2)提出了基于参数模型的长流分段技术。长流分段是提高流处理器上流寄存器文件(Stream Register File,简称SRF)带宽利用率的重要途径之一。其中获得最优分段大小是长流分段技术的基础。最优分段大小是指程序运行时间最短时所采用的分段长度,因此量化受段大小影响的程序运行时间是获得最优分段的关键。论文提出了一种基于参数模型的长流分段技术,旨在通过建模分析获得理论上的最优分段,从而最小化程序运行时间。该技术的研究重点包括以下三个方面:首先,根据程序性质和采用的优化策略,基于具有单地址产生器的访存系统建立了程序运行时间的参数模型;然后,根据对参数模型的分析,分别研究了计算密集型程序和访存密集型程序的最优分段策略;最后,提出了一种面向任意程序的最优分段算法。实验结果表明,基于参数模型的长流分段技术能够有效避免和隐藏片外访存延迟,提高SRF的利用率。(3)提出了开发kernel内计算与访存重叠的优化技术。开发kernel内计算与访存的重叠能够隐藏访存延迟以保证持续供数。单kernel本身的访存与计算无法重叠执行,因此通常采用数据流分段将单kernel划分为多个子kernel,使得不同子kernel的访存与计算相互隐藏。为了最大化kernel内计算与访存的重叠,论文综合采用理论和经验共同指导的方法,基于实际Imagine访存系统提出了三种针对不同应用需求的分段策略:经验策略、长流策略和最优策略。这三种策略的适用范围各不相同,而编译实现的复杂度依次递增。用户可以根据不同的流编译器对算法复杂度和准确度的要求,以及被编译流程序的特点,选择适合的数据流分段策略,以保证编译算法的简单性和近优性。实验结果表明,经验策略和长流策略分别适用于小规模和大规模科学计算程序,而相对复杂的最优策略适用于开发任意科学计算程序的延迟隐藏。(4)提出了面向任意程序的kernel间重用优化技术。开发kernel间数据流重用能够增强SRF重用,以避免访存延迟。现有流编译器无法将两类kernel间数据流重用(长流重用和部分重用)转化为SRF重用,因而具有进一步重用优化的潜力。为此,论文提出了一种面向任意程序的kernel间重用优化技术。该技术的研究重点包括以下三个方面:首先,研究了受限于SRF容量的kernel间长流重用问题,提出了kernel间长流重用优化算法;然后,定义了更广泛的kernel间重用概念——kernel间部分重用,研究了无法被编译器发掘的kernel间部分重用类型,提出了识别和开发这些部分重用的优化算法;最后,综合以上两种优化算法,提出了不受限于SRF容量和不受限于部分重用类型的kernel间重用优化算法。实验结果表明,论文提出的kernel间重用优化算法能够显著提高SRF局部性,有效减少访存次数,从而增强向Imagine的持续供数能力。(5)提出了几种典型科学计算库函数的优化与实现方法。统计表明,科学计算程序中常用的核心函数一般比较固定,这些核心函数在流体系结构上的实现和复用对于开发科学计算流程序至关重要。为此,基于这些核心函数,我们实现了一个内联的科学计算函数库。其中,库函数的优化设计和实现决定了科学计算函数库的性能。论文从该函数库中选取了五个典型的科学计算程序(Jacobi、GEMM、Transp、Laplace和Swim)作为示例程序,设计了不同特性的库函数在流处理器上的优化实现策略。实验结果表明,经过优化实现的科学计算程序能够在流处理器上获得显著的性能提升。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 高性能体系结构面临的问题
• 1.1.2 流体系结构和流编程模型的性能优势
• 1.1.3 科学计算程序的需求
• 1.1.4 基于流体系结构和流编程模型加速科学计算程序
• 1.2 课题研究内容
• 1.2.1 课题来源
• 1.2.2 课题研究重点
• 1.2.3 课题研究难点
• 1.3 相关研究工作
• 1.3.1 流体系结构
• 1.3.2 流编程模型和编译系统
• 1.3.3 传统编译优化技术
• 1.4 论文的主要工作和创新
• 1.5 论文结构
• 第二章 Imagine上面向科学计算的编译框架
• 2.1 Imagine流处理系统
• 2.1.1 Imagine流体系结构
• 2.1.2 Imagine流编程模型
• 2.1.3 Imagine流编译系统
• 2.1.4 Imagine的性能潜力
• 2.2 面向科学计算的流编程和编译技术
• 2.2.1 科学计算程序对流编程和编译的挑战
• 2.2.2 SF95流编程语言
• 2.2.3 SF95Compiler流编译器
• 2.3 小结
• 第三章 基于D&C矩阵的优化流变换技术
• 3.1 问题的提出
• 3.2 相关工作
• 3.3 D&C矩阵
• 3.4 基于D&C矩阵的优化流变换
• 3.4.1 粗粒度程序变换
• 3.4.2 细粒度程序变换
• 3.4.3 数据流组织优化
• 3.5 编译实现
• 3.6 实验评测
• 3.6.1 粗粒度程序变换评测
• 3.6.2 细粒度程序变换评测
• 3.6.3 数据流组织优化评测
• 3.7 小结
• 第四章 基于参数模型的长流分段技术
• 4.1 问题的提出
• 4.2 相关工作
• 4.3 基本框架
• 4.4 基于参数模型的长流分段
• 4.4.1 建立参数模型
• 4.4.2 计算密集型程序的分段
• 4.4.3 访存密集型程序的分段
• 4.4.4 任意程序的分段
• 4.5 编译实现
• 4.5.1 算法实现
• 4.5.2 优化策略的选择
• 4.6 实验评测
• 4.7 小结
• 第五章 开发计算核心内的计算与访存重叠
• 5.1 问题的提出
• 5.2 相关工作
• 5.3 经验策略
• 5.3.1 程序建模
• 5.3.2 策略实现
• 5.4 长流策略
• 5.4.1 程序建模
• 5.4.2 策略实现
• 5.5 最优策略
• 5.5.1 研究思路
• 5.5.2 分段决策
• 5.5.3 策略实现
• 5.6 实验评测
• 5.6.1 小规模程序
• 5.6.2 大规模程序
• 5.7 小结
• 第六章 开发计算核心间的数据流重用
• 6.1 问题的提出
• 6.2 相关工作
• 6.2.1 存储重用
• 6.2.2 重用优化
• 6.3 开发核间的长流重用
• 6.3.1 重用指导的kernel重排序
• 6.3.2 重用优化的kernel集合
• 6.3.3 重用驱动的长流分段
• 6.4 开发核间的部分重用
• 6.4.1 重要概念
• 6.4.2 基本思想
• 6.4.3 识别kernel间部分重用
• 6.4.4 开发kernel间部分重用
• 6.5 编译实现
• 6.6 实验评测
• 6.7 小结
• 第七章 典型科学计算库函数的优化与实现
• 7.1 问题的提出
• 7.2 相关工作
• 7.3 Jacobi
• 7.3.1 流化方法
• 7.3.2 实验评测
• 7.4 GEMM
• 7.4.1 流化方法
• 7.4.2 实验评测
• 7.5 Transp
• 7.5.1 流化方法
• 7.5.2 实验评测
• 7.6 Laplace
• 7.6.1 流化方法
• 7.6.2 实验评测
• 7.7 Swim
• 7.7.1 流化方法
• 7.7.2 实验评测
• 7.8 小结
• 第八章 总结与未来工作
• 8.1 工作总结
• 8.2 研究展望
• 致谢
• 攻读博士学位期间发表的论文
• 攻读博士学位期间参加的主要科研工作
• 参考文献