面向可重构阵列任务编译的循环变换技术研究

论文摘要

近年来,结合了通用处理器的灵活性和专用集成电路的高效性优点的可重构计算技术获得了广泛深入的研究,它具有灵活高效的结构,非常适合多媒体运算和信号处理等计算密集型任务的处理。但是,目前可重构计算领域缺乏高效的自动任务编译工具,尤其是对应用中循环代码的处理是个难题。与手工映射相比,高效的任务编译工具可以有效节约映射的时间和提高映射的效率。本文即以循环变换技术为重点,研究将循环代码高效地映射到可重构阵列上的创新技术,并开发相应的自动化高效任务编译工具。本文改进了现有程序剖析(profiling)工具来进行循环的剖析,收集循环执行的信息以用于循环的分析和优化。可重构阵列具有计算单元多、无访存功能等特点,本文结合传统的并行编译优化技术,研究了循环展开等技术在任务编译器中的实施条件和方法,从而解决了现有编译工具很难高效利用可重构部分硬件资源的缺点,并采用了标量替换技术将循环中的访存操作进行集中预取或写回,从而支持可重构阵列无访存功能这一特点。本文改进了现有的高级语言循环数据流图的生成方法,使用数据流分析技术分析并消除数据流图中冗余的节点。本文将这些循环变换和编译方法实现到任务编译器RCAcompiler中,并对典型的多媒体处理算法和数字信号处理算法进行实验,实验数据显示采用本文的优化方法后循环数据流图中的节点平均减少了30%,编译后目标代码运算性能平均提高了2.4倍。本文方法能够有效地提高任务编译器对循环编译的并行性,提高了任务编译器的性能。

论文目录

• 摘要
• ABSTRACT
• 图录
• 表录
• 第一章 绪论
• 1.1 研究背景
• 1.2 可重构计算处理器及其任务编译器
• 1.2.1 可重构计算处理器
• 1.2.2 可重构计算处理器的任务编译器
• 1.3 REmus 可重构计算阵列处理器体系结构
• 1.4 论文的主要内容与章节安排
• 第二章 循环变换技术的基本理论与方法
• 2.1 循环中依赖关系分析
• 2.1.1 基本概念
• 2.1.2 数据依赖分析方法
• 2.2 数据局部性
• 2.3 并行编译中常用的循环变换
• 2.4 本章小结
• 第三章 面向 REmus 可重构系统的循环变换与优化方法设计
• 3.1 程序中循环的profiling
• 3.1.1 循环分离
• 3.1.2 循环的profiling 和实验
• 3.2 面向REmus 可重构系统的循环展开
• 3.2.1 一个循环展开的例子
• 3.2.2 循环展开的条件
• 3.2.3 循环展开的步骤
• 3.3 面向REmus 可重构系统的循环中标量替换
• 3.3.1 一个标量替换的例子
• 3.3.2 循环中标量替换的算法
• 3.4 面向REmus 可重构系统的循环中冗余计算消除
• 3.4.1 使用数据流分析技术来分析和消除循环中冗余计算
• 3.4.2 数据流图上消除循环中的冗余计算
• 3.5 面向REmus 可重构系统的循环的数据流图生成
• 3.5.1 循环的数据流图生成
• 3.5.2 循环中依赖关系的保持
• 3.5.3 DFG 节点对应的源码输出
• 3.6 本章小结
• 第四章 面向 REmus 可重构阵列处理器的任务编译器实现
• 4.1 可重构阵列任务编译器RCAcompiler 的系统流程
• 4.2 RCAcompiler 的开发平台SUIF/MACHSUIF
• 4.3 可重构阵列任务编译器RCAcompiler 的前端
• 4.3.1 输入源文件的解析
• 4.3.2 任务软硬件划分
• 4.3.3 循环数据流图的生成
• 4.4 可重构阵列任务编译器RCAcompiler 的后端
• 4.4.1 基于DFG 的划分和映射方法
• 4.4.2 基于模板库的映射方法
• 4.4.3 联合编译
• 4.5 可重构阵列任务编译器RCAcompiler 的系统实现
• 4.6 本章小结
• 第五章 实验结果与分析
• 5.1 实验测试平台
• 5.2 实验与结果分析
• 5.3 本章小结
• 第六章 结束语
• 6.1 主要工作与创新点
• 6.2 后续研究工作
• 参考文献
• 致谢
• 攻读硕士学位期间已发表或录用的论文