面向科学计算流处理器的编译存储优化技术研究

论文摘要

流处理器以其强大的计算能力、较低的功耗和灵活的可编程性,成为当前高效能计算系统定制加速部件的主要选择之一,已成功运用于2008年TOP500排名第一的IBM Roadrunner系统。然而,原本面向多媒体领域开发的流编译器,在处理数据依赖关系更加复杂的科学计算应用时,表现出较差的适应性,对流存储系统特征的利用十分有限,致使存储墙问题更为严重,成为制约其性能发挥的瓶颈。因此,研究面向科学计算流处理器的编译存储优化技术成为释放流处理器强大计算能力,有效缓解存储墙问题的关键。本文重点研究了如何通过编译优化技术来改善流处理器的存储性能。流存储系统包括三级存储层次:本地寄存器文件（Local Register File,简称LRF）、流寄存器文件（Stream Register File,简称SRF）和片外存储系统。优化片上存储器的局部性、隐藏访存延迟和避免片上存储器溢出,能有效改进流处理器性能。本文在分析了大量具有不同性能特征的科学计算流程序的访存行为后,面向科学计算从优化片上存储器局部性、隐藏访存延迟和避免SRF溢出等方面进行了深入的研究。本文的主要工作和创新如下:1.当前流编译器通过簇间通信机制发掘簇间记录复用,然而大量簇间通信的引入严重影响了程序性能。本文提出了流转置方法ST,该方法根据程序的复用信息重新组织数据,将簇间记录复用等价地转换为同一运算簇内的记录复用。同时,为避免因数据重组导致的存储体冲突,该方法给出了发生存储体冲突的判别定理,并采用循环分割技术避免冲突发生。该方法在不引入任何簇间通信且不影响流访存性能的同时,有效发掘了ALU簇间记录复用,改进了LRF的局部性。与当前流编译器的簇间复用发掘方法相比,ST方法获得了高达46%的性能提升。2.发掘SRF中的流复用能有效改进SRF的局部性。据我们所知,迄今为止还没有现成的方法,能够自动发掘流程序中起始或终止边界为变量的变界流之间的复用,只能依靠程序员手工完成。本文提出了定界流替换方法CBSR,该方法是国际上第一个自动发掘变界流完整复用的方法,由一系列创新性的理论、机制和算法组成,包括首次提出的流复用识别理论、首次定义并构建的用于描述流复用信息的流复用图（SRG）、基于SRG发掘流完整复用的程序变换算法和SRF压力评估与缓解算法等。CBSR方法有效发掘了变界流之间的完整复用,避免了数据的重复加载,改进了SRF局部性,提升了程序性能。与当前流编译器的流调度方法相比,CBSR方法获得了1.14～2.78的性能加速比。3.存在于流的访存子序列之间的流部分复用,是流编程模型所特有的一类复用。当前流编译器无法发掘变界流之间的部分复用,面向传统体系结构的编译技术中也没有可借鉴的方法。本文对CBSR方法进行扩展,首次提出了发掘流部分复用的E-CBSR方法,该方法包括:定义并量化流部分复用;提出并证明它的识别与判定理论;改进SRG以描述该类复用;扩展CBSR方法中的程序变换算法使其能够处理流部分复用。该方法同时发掘了变界流之间的完整和部分复用,消除了流的冗余加载,改进了SRF的局部性。与当前流编译器的流调度方法相比,E-CBSR方法获得了1.27～2.54的性能加速比。4.数据预取是隐藏访存延迟的一种有效方法,但资源分配冲突会导致预取失效。本文提出了一种基于SRG的SRF资源分配避免算法SRFACA。与已有SRF资源分配算法相比,该算法在SRF预取开销更小的同时,避免了SRF资源分配冲突,增加了预取的有效性。实验结果表明,在CBSR/E-CBSR方法优化后的流程序基础之上,SRFACA算法进一步获得了高达1.88的性能加速比。5. SRF溢出将导致流复用和流预取带来的好处尽失。当前流编译器采用循环分段算法避免SRF的溢出,却破坏了程序中跨迭代流复用的发掘和流预取。本文提出了基于SRG的循环分块算法。与当前流循环分段技术相比,该算法可给出更加精确的SRF空间需求,自动确定合适的块大小,在有效避免SRF溢出的同时,确保跨迭代流复用的发掘和流预取。与循环分段算法相比,该算法获得了1.12～2.61的性能加速比。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 课题研究背景
• 1.1.1 高性能体系结构发展趋势
• 1.1.2 高性能流计算模型及其存储瓶颈分析
• 1.2 课题研究重点
• 1.2.1 基本概念
• 1.2.2 LRF 局部性优化
• 1.2.3 SRF 局部性优化
• 1.2.4 隐藏访存延迟优化
• 1.2.5 避免SRF 溢出的优化
• 1.3 相关研究工作
• 1.3.1 面向传统体系结构存储优化的编译技术
• 1.3.2 已有的优化流处理器存储性能的编译技术
• 1.4 本文工作和创新
• 1.5 章节组织
• 第二章 流科学计算概述及存储瓶颈分析
• 2.1 流、流编程模型和流体系结构
• 2.1.1 流
• 2.1.2 流编程模型、编程语言及编译器
• 2.1.3 流体系结构
• 2.2 流科学计算的优势与存储瓶颈分析
• 2.2.1 流科学计算的优势
• 2.2.2 存储瓶颈分析
• 2.3 典型科学计算应用的流化及其存储性能分析
• 2.3.1 测试程序
• 2.3.2 流化
• 2.3.3 面向存储性能的手工优化
• 2.3.4 性能评测
• 2.3.5 结论
• 2.4 本章小结
• 第三章 发掘簇间记录复用的流转置方法
• 3.1 簇间记录复用分析
• 3.2 流的重组算法
• 3.3 避免存储体冲突的MBCA 算法
• 3.3.1 流片外存储系统
• 3.3.2 SRO 算法与存储体冲突
• 3.3.3 MBCA 算法
• 3.4 ST 方法及其编译实现
• 3.5 实验建立和结果分析
• 3.6 本章小结
• 第四章 发掘变界流完整复用的定界流替换方法
• 4.1 问题提出与方法概述
• 4.1.1 问题提出
• 4.1.2 方法概述
• 4.2 流完整复用的判别理论
• 4.2.1 定义与假设
• 4.2.2 流完整复用判别
• 4.3 SRG 及其构建算法
• 4.3.1 构建流有向无环图的BSDAG 算法.
• 4.3.2 构建复用图的BRG 算法
• 4.4 SRG 的优化
• 4.5 流级程序的变换算法SLPT.
• 4.6 SRF 压力评估与缓解
• 4.7 编译实现与实验评测
• 4.7.1 编译实现
• 4.7.2 实验评测
• 4.8 相关工作
• 4.9 本章小结
• 第五章 发掘变界流部分复用的扩展的定界流替换方法
• 5.1 流部分复用
• 5.2 方法概述
• 5.3 流部分复用的判别理论
• 5.4 SRG 的改进算法BPRE
• 5.5 扩展的流级程序变换算法E-SLPT
• 5.6 实验建立与评测
• 5.6.1 实验建立
• 5.6.2 评测结果
• 5.7 本章小结
• 第六章 基于SRG 的SRF 资源分配冲突避免算法.
• 6.1 SRF 资源分配冲突分析
• 6.2 SRF 资源分配冲突避免算法SRFACA
• 6.2.1 流片外存储系统状态评估
• 6.2.2 算法实现
• 6.3 编译实现与实验评测
• 6.3.1 编译框架
• 6.3.2 实验评测
• 6.4 相关工作
• 6.5 本章小结
• 第七章 基于SRG 自动确定块大小的循环分块算法
• 7.1 问题提出
• 7.2 自动确定块大小的循环分块算法
• 7.2.1 循环分块算法
• 7.2.2 基于SRG 自动确定块大小的算法
• 7.3 编译实现与实验评测
• 7.3.1 编译实现
• 7.3.2 实验评测
• 7.4 本章小结
• 结束语
• 致谢
• 参考文献
• 攻读博士学位期间已发表和待发表的主要学术论文
• 攻读博士学位期间参加的主要科研工作