基于谓词代码的编译优化技术研究

程序中大量分支指令的存在,严重制约了体系结构和编译器开发并行性的能力。有效发掘指令级并行性的一个主要挑战是要克服分支指令带来的限制。利用谓词执行可有效地删除分支,将分支指令转换为谓词代码,从而扩大了指令调度的范围并且删除了分支误测带来的性能损失。阐述了基于谓词代码的指令调度、软件流水、寄存器分配、指令归并等编译优化技术。设计并实现了一个基于谓词代码的指令调度算法。实验表明,对谓词代码进行编译优化,能有效提高指令并行度,缩短代码执行时间,提高程序性能。     

BWDSP10x上地址和数据谓词执行的编译优化

传统的谓词优化技术是在冯·诺伊曼体系结构计算机上实施的,仅对数据流进行优化,并没有考虑哈佛体系结构下指令和数据分开的情况.BWDSP10x是指令和数据分开的哈佛体系结构,它支持超长指令字,不仅提供了对数据谓词执行的支持也提供了对地址谓词执行的支持.特此提出了一种在区域上对两种谓词模式优化支持的方法,在进行两种比较之前,通过判断比较操作的两个操作数类型来分别实施两种模式的谓词优化,使得对地址的比较不用传输到通用寄存器中.实验结果表明该优化方法能显著地节省CPU的时间和带宽,大大减少了分支指令,使程序性能提高了28.4%.     

指令级并行中谓词分析技术的研究

谓词支持是IA 6 4体系结构的新特征 ,它为发掘指令级并行提供了更多的机会 ,同时给编译器的设计者增加了难度 .谓词是条件执行的依据 ,是提高指令级并行的新途径 .该文介绍在ORC(IA 6 4OpenResearchCompiler)中首次设计实现的基于谓词划分图的谓词分析技术及其在指令调度中的应用 .利用谓词分析技术建立了谓词关系数据库、指令调度查询谓词关系数据库提高指令级并行 .文章着重论述了谓词关系数据库的核心———谓词划分图的建立 ,在谓词划分图的基础上实现了谓词关系的计算和查询 ,实际结果表明谓词分析技术有显著优化效果 .     

分簇VLIW DSP上支持单双字模式选择的SIMD编译优化

BWDSP100是一款采用超长指令字(VLIW)和单指令多数据流(SIMD)架构的针对高性能计算领域而设计的32位静态标量数字信号处理器,其指令级并行(ILP)主要是通过其特殊的分簇体系结构和SIMD指令来实现,然而现有的编译框架无法对这些特殊的SIMD指令提供支持。由于BWDSP100拥有丰富的SIMD向量化资源,且其所运用的雷达数字信号处理领域对程序的性能要求极高,因此针对BWDSP100结构的特点,在传统Open64编译器中SIMD编译优化框架的基础上提出并实现了一种支持单双字模式选择的SIMD编译优化算法,通过该算法可以显著提高一些在DSP上有着广泛运用计算密集型程序的性能。实验结果表明,与优化前相比,该算法方案在BWDSP编译器上的实现能够平均取得5.66的加速比。     

Matrix编译器If转换算法的实现

指令级并行在提高处理器运行速度方面显得越来越重要,if转换技术是一种在处理器支持条件执行的前提下,有助于提高指令级并行度的编译优化技术。在详细分析GCC(GNU Compiler Collection)内部if转换技术的实现机制和算法的基础上,针对matrix体系结构特点,对GCC中现有if转换算法进行了移植与改进,实现了matrix编译器的if转换算法。实验证明,改进后的if转换算法能够更有效地移除分支,减少基本块的数量,扩大单个基本块的范围,有助于编译器生成更加优化的代码。     

分簇结构谓词以及编译优化框架研究

谓词执行是在控制流存在的条件下可以有效挖掘指令级并行性的硬件机制。而在分簇结构上实现谓词机制,可以提高分簇结构上条件的执行效率。本文针对分簇结构展开谓词体系体系结构的研究,提出了分簇结构部分谓词的高效实现方法,以及基于循环展开的分簇结构部分谓词支持框架。实验表明,本文提出的分簇结构部分谓词及编译框架可以很好地提高条件执行程序的执行效率。     

改进的指令总线功耗优化策略

针对编译器系统设计和编译中的低功耗优化,基于可重定向编译器,实现在编译器后端对VLIW指令总线进行功耗优化的策略.通过对编译生成的二进制目标码进行横向再调度来减少指令总线上的高低电位切换次数,达到降低系统功耗的目的.对编译后端的软件流水和超块调度两种性能优化策略进行对比实验,表明其优化效果在30%以上,并且代码的指令级并行性(Instruction Level Parallelism,ILP)与优化效果存在明显的相关性.最后,通过ILP对该策略提出改进,以指令级并行信息指导功耗优化,在功耗优化效果损失不大的前提下,可节省多达20%的算法开销.     

基于BDD的谓词分析与优化

为对带谓词的数据流进行准确而有效的分析,首先介绍了John W.Sias等人提出的一种基于二进制决策图(BDD)的谓词分析系统(PAS);然后在其基础上,提出了结合芯片自身体系结构特点的谓词优化算法。将PAS及优化算法在学院研制的FT_D4芯片的编译器上实现,实验结果表明,这种基于BDD的谓词分析与优化方法简化了程序控制结构,减少了对谓词寄存器的使用,缩短了代码执行时间,性能获得了较大的提高。     

BWDSP SIMD编译的寄存器分配优化技术研究

BWDSP是一款自主设计的国产VLIW(超长指令字)数字信号处理器,支持SIMD技术,其SIMD指令可以在4个宏上同时执行4个32位计算,对寄存器使用有特殊规则,Open64编译器的寄存器分配策略并不适用于这种规则.本文对BWDSP SIMD指令的寄存器分配优化技术进行了研究,并在BWDSP的编译器OCC上得以实现.     

DSP分块内存和多AGU的编译指示优化

分块内存和多地址生成器(AGU)是DSP普遍采用的体系结构.传统的C语言编译器没有针对分块内存和多AGU结构进行代码优化,导致生成代码无法满足性能需求,影响了C语言编译器在数字信号处理领域的应用.为了解决这个问题,提出基于编译指示,与分块内存和多AGU结构相关的编译优化算法.该算法利用定义引用链和引用定义链中的数据流信息,为地址计算指令和访存指令分配AGU,从而提高生成代码的指令级并行度.实验结果表明此算法能够达到较好的优化效果.     

魂芯DSP上复数类型的支持和优化

魂芯DSP是一款采用VLIW和SIMD架构的针对高性能计算领域而设计的32bit静态标量数字信号处理器.为了满足数字高性能计算的性能要求,魂芯DSP提供了丰富的复数指令,而编译器不能直接利用这些复数指令来提升编译性能.因此针对魂芯DSP芯片提供了大量的复数类操作指令的特点,在传统开源编译器Open64的编译框架基础上进行研究,实现了复数作为编译器基础类型和复数运算操作的支持.同时,通过识别特定的复数类操作的模式利用魂芯DSP上的复数类指令对程序编译优化.实验结果表明,该实现方案在魂芯DSP编译器上对复数程序优化后能够取得平均5.28的加速比.     

面向BW104x软流水框架

现代高性能数字信号处理器大多数采用超长指令字体系结构,通过在同一时钟周期发射多条指令以便获得更高的运算性能来发掘目标机器指令级别并行性.介绍了BW104x目标体系特征,BWDSP104X是一款针对高性能计算领域设计的处理器,采用16发射、单指令流,多数据流架构.为了充分利用多簇及簇内硬件资源,基于open64编译基础设施提出了后端软流水优化,其中包括循环选择,资源依赖数据依赖计算,采用经典的模调度方法进行软流水调度,为解决不同迭代变量冲突引入模变量拓展模块.实验结果证明流水后性能相对流水前有了很好的提升.     

面向多簇架构DSP的树匹配向量化算法

BWDSP是针对高性能计算设计的一款新型的处理器, 采用多簇超长指令字体系结构和SIMD架构, 有丰富的指令集. 为充分利用BWDSP提供的向量化资源, 迫切需要提出一种向量化算法. 本文在open64基础上研究并实现了面向多簇超长指令字(VLIW)DSP的SIMD编译优化算法. 算法基于OPEN64的中间语言WHIRL, 能够充分地利用BWDSP丰富的硬件资源和向量化指令. 最终实验结果表明, 对于能够合成双字和单字的循环程序, 该优化算法能够平均取得6倍和4倍的加速比.     

PCC中数组边界检查的优化和生成

PCC的数组边界检查存在着由于无法确定数组下标表达式符号值的范围，而造成拒绝执行一些安全的移动代码等问题。本文给出的一种数组边界检查的优化及生成算法，不仅能够比较好地解决了这一问题，同时还生成了循环不变式注解中的条件谓词。我们设计的编译器——认证编译器——已经实现了这些算法，并完成了从用C编程语言的类型安全子集编写的源程序到携带注解的Intelx86／linux汇编语言程序的编译过程。由于基于语言安全策略系统的证明是建立在携带注解的代码基础之上的，因此该认证编译器中实现的算法在移动代码安全检查中非常有用。     

基于BWDSP的字符串与内存处理函数优化

面向BWDSP的体系结构分析了字符串与内存处理函数汇编优化方法,基于向量化与软件流水的优化技术,通过利用高效访存指令、能够提升循环执行效率的零开销循环机制、指令重排技术,结合具体功能函数的循环特性,展开针对字符串与内存处理函数的指令级并行性挖掘.实验结果表明,这些库函数的优化效率能够达到硬件平台提供函数性能理论运行时间的1.5倍以下,对BWDSP平台整体性能提升具有重要意义.     

网络处理器IXP的位操作优化

该文介绍一种针对IXP网络处理器指令集的编译器优化技术,该技术将位信息记录引入到传统数据流分析过程当中,通过使用模式匹配技术生成高效的目标代码,试验数据表明利用位操作优化最终生成的指令数可以减少1.1%-3.7%。     

众包环境下多谓词查询优化

近年来,众包查询优化得到了数据库领域的广泛关注。主要研究了众包多谓词选择查询问题--借助于人力找到满足多谓词查询条件的对象。一种简单的方法是枚举数据集中的对象,对于每个对象判断是否满足每条谓词。它产生的代价是[|R|?n],其中[|R|]为数据集中对象的数量,[n]为谓词的数量。很显然,当处理大数据集或者查询包含较多谓词的时候,简单方法的代价是非常昂贵的。由于不同的谓词具有不同的选择性,如果首先验证高选择性的谓词,那么在验证剩余谓词的时候,就可以避免验证不满足高选择性谓词的对象。因此,采用一个好的谓词顺序实现众包选择查询可以显著减少人工代价。然而,实际中很难获得最佳的谓词序列。针对该问题,提出了一种基于采样的框架来获得高质量的查询序列。为了控制查询序列生成的成本,设计了基于随机序列的最优选择方法,该方法通过随机选择序列获得最终的谓词顺序。由于基于随机序列的选择方法可能产生较大的代价,为了减少开销,提出了一种基于过滤的序列选择方法。通过在众包平台上使用真实数据集评测了提出的方法,实验结果表明,该方法能够显著减少查询序列生成的代价,同时获得高质量的查询序列。     

Path Analysis and Renaming for Predicated Instruction Scheduling

Increases in instruction level parallelism are needed to exploit the potential parallelism available in future wide issue architectures. Predicated execution is an architectural mechanism that increases instruction level parallelism by removing branches and allowing simultaneous execution of multiple paths of control, only committing instructions from the correct path. In order for the compiler to expose and use such parallelism, traditional compiler data-flow and path analysis needs to be extended to predicated code. In this paper, we motivate the need for renaming and for predicates that reflect path information. We present Predicated Static Single Assignment (PSSA) which uses renaming and introduces Full -Path Predicates to remove false dependences and enable aggressive predicated optimization and instruction scheduling. We demonstrate the usefulness of PSSA for Predicated Speculation and Control Height Reduction. These two predicated code optimizations used during instruction scheduling reduce the dependence length of the critical paths through a predicated region. Our results show that using PSSA to enable speculation and control height reduction reduces execution time from 12 to 68%.