支持SIMD的DSP编译优化技术的研究与实现

论文摘要

与传统的DSPs相比，现代DSPs采用了更多的ILP技术以提高性能。同时，为了适应媒体处理的特殊需要，现代的DSPs在硬件的设计方面的一个普遍的特征就是引入了SIMD指令。这就使得低精度的媒体数据的快速处理成为可能。一个真正的高性能、低功耗的系统，不仅要有良好的硬件支持而且更重要的是要有一个能够充分利用这些硬件特征的优化的软件系统。编译器作为这个软件系统中最重要的一环，其性能的优劣将直接影响系统的整体性能。但目前的编译技术却不能很好的提供对SIMD指令的支持，所以本文就深入的研究了支持SIMD指令的编译优化技术，取得了如下的一些研究成果。 1．提出了一套完整的支持SIMD指令的代码选择技术的实现框架。该框架使得代码选择面向基本块，而不再是语句，扩大了指令注释的搜索空间，产生了SIMD指令。同时采用机器描述来刻画目标机器指令集，使得代码选择中与机器相关的部分局限于机器描述中，提高了代码选择的灵活性和可移植性。 2．设计并实现了一种基本块的数据流图(DFG)表示，这种表示既能充分表达Lcode语义又比较适合模式匹配算法。传统的代码选择技术往往基于的是数据流树(DFTs)的中间表示，这也正是其不能很好的支持SIMD指令的一个重要原因。同时为了借鉴模式匹配的思想，在这里还实现了从DFG到DFTs的转化。 3．采用一种树文法描述了目标机器的指令集，并对其进行预处理，使其转化为相应的指令模板。树文法为目标机器指令集的描述提供了一种易读、易写、易修改的方式，同时通过预处理隐藏了机器描述的细节，为编译的树匹配过程提供了统一的接口。 4．改进了传统的树匹配和动态规划算法。使得其在匹配每棵输入树时，不再是产生唯一的最优覆盖，而是产生多个可选的最优覆盖。为整数线形规划从全局角度最终确定最优覆盖做准备。 5．采用了整数线形规划的方法解决了最终的最优覆盖的选择问题。在充分考虑最终覆盖的正确性和有效性的情况下，提取出其所应满足的一系列约束及相应的目标方程，该方程的最大解即表示最终将产生的SIMD指令的数目。

论文目录

• 图目录
• 表目录
• 摘要
• ABSTRACT
• 第一章 引言
• §1.1 课题背景与意义
• §1.2 本文的贡献
• §1.3 论文结构
• 第二章 SIMD指令及其编译器
• §2.1 SIMD指令概述
• 2.1.1 基本概念
• 2.1.2 YHFT-DSP／700支持的SIMD指令
• §2.2 IMPACT编译器简介
• 2.2.1 编译器整体结构
• 2.2.2 Lcode中间表示
• 第三章 支持SIMD指令的代码选择技术
• §3.1 经典的指令选择算法
• 3.1.1 解释型代码生成（Interpretative Code Generation）
• 3.1.2 模式匹配代码生成
• 3.1.3 表驱动代码生成
• 3.1.4 两种代码生成方法优缺点的比较
• §3.2 传统的编译器对SIMD指令的支持
• 3.2.1 建立内联函数（intrinsics）的方法
• 3.2.2 优化汇编库的方法
• 3.2.3 IMPACT代码注释的方法
• 3.2.4 传统的模式匹配算法不支持SIMD指令的原因
• §3.3 支持SIMD指令的代码选择技术实现框架
• §3.4 小结
• 第四章 指令模板和DFT生成
• §4.1 目标机器指令集描述
• 4.1.1 树文法
• 4.1.2 文法规范
• 4.1.3 YHFT-DSP／700指令集的描述
• §4.2 中间代码转换
• 4.2.1 基本块的DFG表示
• 4.2.2 特殊指令的DFG表示
• 4.2.3 由基本块构造DFG的过程
• 4.2.4 把DFG分解为DFT的过程
• 第五章 模板匹配
• §5.1 问题描述
• §5.2 树匹配和动态规划算法
• 5.2.1 多关键字匹配算法
• 5.2.2 自顶向下的模式匹配算法
• 5.2.3 动态规划算法
• §5.3 算法的改进和实现
• 5.3.1 算法思想
• 5.3.2 设计与实现
• §5.4 小结
• 第六章 覆盖选择
• §6.1 生成最优覆盖的约束
• §6.2 实例分析
• §6.3 小结
• 第七章 结束语
• 致谢
• 攻读硕士期间发表的论文
• 参考文献