一种先进的扁平化谓词及编译优化方法

谓词执行是有效挖掘控制流程序指令级并行性的一种机制.经典的谓词实现一般局部地逐个进行谓词计算而不能进行多谓词控制,有谓词计算路径过长等问题.针对经典谓词存在的问题,提出一种先进的扁平化谓词的实现方法,这种扁平化谓词可以全局地进行谓词计算,可以自然地进行多谓词控制.在此基础上,研究扁平化谓词的编译优化方法,给出了扁平化谓词编译优化框架.实验表明,本文提出的扁平化谓词及编译优化框架可以很好地提高多条件控制程序的执行效率.     

并行编译中的区域调度问题

介绍指令级并行性(ILP)中和指令级计算(EPIC)中区域的直观概念和这些概念的形式化工作，并简单介绍区域的几个调度算法，为并行编译中的区域调度问题提供一个系统的、形式化的论述。     

基于循环展开的子字并行指令自动生成

针对向量编译的不足,提出一种基于循环展开的子字并行指令自动生成的方法.该方法利用传统的循环变换技术对多媒体应用中可以进行子字并行的循环进行优化,生成子字并行代码.首先识别出可并行的循环,然后通过循环展开、寄存器重命名、指令合并等技术来提升循环体基本块中的子字并行性.在TTA(transport triggered architecture)体系结构的编译框架下用该方法实现了子字并行指令的自动生成.实验表明该方法得到了较好的加速比.     

基于Amdahl定律的分组密码并行处理模型研究

为进行分组密码并行处理的理论研究和定量分析,构建了基于Amdahl定律的分组密码并行处理模型.通过引入分组内数据级并行性、分组内指令级并行性、分组间数据级并行性和分组间指令级并行性等并行性,建立了分组密码的多维度并行处理模型,研究了算法参数和并行参数对分组密码处理性能的影响.结果表明,并行比例大的算法其性能提升空间较大,且开发任一并行性都能够提升密码运算性能;但对于具体的应用场景,需要根据算法结构、工作模式等来进行合理的资源配置和并行性开发;该模型能够为分组密码算法的并行处理架构设计、资源配置和并行性开发等提供理论依据和指导原则.      

一种同时多线程指令队列竞争缓解策略

同时多线程结构利用线程级并行和指令级并行的优势,提高了指令吞吐率,但线程对关键资源（如指令队列）的竞争会削弱这种优势,造成资源浪费,又会降低处理器性能。提出了指令队列利用参数,通过分析指令队列利用率与处理器性能的关系,用实验评估了在四线程情况下,典型静态指令队列竞争缓解策略（如Dwarn、2OP_Block、Static）及其组合对处理器性能的影响。给出了load依赖链模型,分析了基于load依赖链的基准程序线程特性,提出了一种结合线程特性的指令队列竞争缓解策略。实验结果表明,该策略能够加速执行指令吞吐率较高的线程,通过提升此类线程的性能使整体指令吞吐率进一步增加。     

多发射处理器的指令调度算法研究

RISC体系作为精简指令集计算机的兴起,使得多发射处理器的指令调度算法成为研究热点。本文从程序块划分和执行角度,讨论了多发射处理器的指令调度算法,介绍了几种局部指令和全局指令调度的影响力较大的算法。它们通过指令调度的优化,提高多发射处理器内部功能部件的执行并行性。本文还给出了进一步研究方向,构造多发射结构多处理器并行处理系统,实现处理器之间的并行技术和处理器内部的并行技术的整合。     

多发射处理器的指令调度算法研究

RISC体系作为精简指令集计算机的兴起,使得多发射处理器的指令调度算法成为研究热点.本文从程序块划分和执行角度,讨论了多发射处理器的指令调度算法,介绍了几种局部指令和全局指令调度的影响力较大的算法.它们通过指令调度的优化,提高多发射处理器内部功能部件的执行并行性.本文还给出了进一步研究方向,构造多发射结构多处理器并行处理系统,实现处理器之间的并行技术和处理器内部的并行技术的整合.     

类簇级测试任务并行化研究

为了提高传统串行类簇级测试速度, 对类簇测试任务并行化方法进行研究。使用类间依赖关系和类测试依赖关系分析方法将类簇级测试任务并行化问题转化为求解对象关系图中节点的并行性。复杂的类簇关系会形成有向环路, 为确定环路中测试的起始位置需要将环路打破, 提出了综合考虑节点度数、环路数和测试桩复杂度3 种因素的破环方法; 对消除环路的对象关系图进行并行性分析, 并设计了一种分层并行算法。通过实验对串行方案和分层并行方案进行对比, 证明了分层并行方案的有效性。     

扩充OpenMP并行编程模型支持事务存储执行

虽然OpenMP是多核体系结构上的流行多线程并行编程模型,但是OpenMP编译器不检查数据相关性、访问冲突和其他可能导致程序错误执行的问题,这些问题传统上完全依赖用户使用锁机制来保证程序的正确性.锁机制的并行编程中存在并行程序效率和并行编程难度的矛盾.粒度大的锁机制编程容易,可应用的并行性挖掘比较差;粒度小的锁机制应用的并行性挖掘较好,可编程难度大,容易带来优先权倒置、死锁和锁护航等问题.通过动态二进制插桩技术,扩充OpenMP支持事务存储执行功能,可有效缓解OpenMP并行编程中并行程序效率和并行编程难度之间矛盾.     

并行查询优化中的负载平衡问题研究

在现有工作的基础上，引入数据偏斜因子，在并行查询优化阶段考虑负载平衡问题，提出了一种并行查询优化方法，用算子间并行性来弥补由数据偏斜引起的算子内并行性下降而造成的影响，提高了查询执行效率，减少了查询时间。     

基于多线程归并排序算法设计

为解决传统递归方式的归并排序算法串行执行效率低的问题, 使用数据依赖关系分析方法对归并排序算法进行并行性分析。通过分析发现算法本身具有并行的特征, 在多核处理器下使用OpenMp编译制导语句对算法进行直接并行化处理。在数据量较大的情况下, 为了使算法执行的速度更快, 在多核处理器系统中设置多个线程, 并将序列分成多个组, 每个线程操作一组数据, 最后对多个局部有序的结果进行逐一合并。实验验证结果表明, 该并行化算法可使执行速度提高50%以上。     

一种结合混淆思想的代码虚拟化保护方法

为了提高虚拟机软件保护方法的抗逆向效果,研究并实现了保护系统OB-VMP(obscure virtual machine protection)。在OB-VMP中,多套虚拟机环境被随机选择来执行构造的混淆基本块和关键代码,私有的虚拟环境使得混淆基本块难以去除;同时混淆基本块让攻击者难以定位关键代码和关键代码所基于的虚拟环境,提高了虚拟机的保护效果。另外,在被保护代码的不同执行阶段,字节码和不同的虚拟指令映射,攻击者不能基于累积的字节码知识进行后续分析,进一步增加了OBVMP的抗逆向效果。理论分析和实验结果显示:OB-VMP能够在较小时空消耗基础上,显著提高逆向分析的难度,提高软件的安全性。     

基于图形处理单元架构的合成孔径雷达回波仿真实现与优化

为了能够有效提高基于时域的SAR回波仿真的运行速度,提出了一种基于图形处理器(GPU)架构的SAR回波仿真优化实现方法。该方法结合GPU的计算密度高、高度并行的特点并利用CUDA流在GPU上同时执行多个任务,实现任务并行、指令并行和数据并行的三重并行,极大地挖掘了回波模拟全过程的并行性,缩短了回波仿真的运算时间。实验结果表明,该方法相对于传统的CPU上的串行算法平均加速比达到128倍,可用于实时信号处理。     

基于GPU架构的SAR回波仿真实现与优化

为了能够有效提高基于时域的SAR回波仿真的运行速度,本文提出了一种基于GPU架构的SAR回波仿真优化实现方法。该方法结合GPU的计算密度高、高度并行的特点并利用CUDA流在GPU上同时执行多个任务,实现任务并行、指令并行和数据并行的三重并行,极大地挖掘了回波模拟全过程的并行性,缩短了回波仿真的运算时间。实验结果表明,该方法相对于传统的CPU上的串行算法平均加速比达到128倍,可用于实时信号处理。     

基于丛生树的可调节的并行查询优化算法研究

在分析现有的并行查询优化算法的基础上，提出了一种新的并行查询优化算法，该算法充分考虑并行计算机的物理限制，以丛生树为模型，利用大关系的数量对操作内的并行性，操作间的独立并行性以及操作间流水并行性进行调节，从而保证了高效的并行查询计划的产生。     

基于分治法求解对称三对角矩阵特征问题的MPI/Cilk混合并行算法

对称稠密矩阵特征问题的求解通常转化为三对角矩阵特征问题的求解,基于对称三对角矩阵特征求解的分而治之方法,提出了一种基于消息传递接口(message passing interface,MPI)+Cilk多任务并行模型的混合求解算法,采用进程间数据并行和进程内多线程任务并行的方法,实现了对分而治之算法中分治阶段和合并阶段的多任务划分和动态调度。进程内利用Cilk任务执行的有向无环图模型,解决了线程级并行的数据依赖和饥饿等待等问题,提高了程序的并行性;进程间通过粗粒度计算任务的划分,优化了MPI部分的数据通信流程和负载均衡问题。数值实验表明,混合并行算法在计算性能和可扩展性方面都要优于纯MPI并行算法。     

IA-64中软件流水失败的解决方法

软件流水是开发指令级并行性的重要方法之一.IA-64是支持软件流水的EPIC(显式并行指令计算)体系结构.通过对NAS Benchmarks和MediaBench中软件流水所需的寄存器进行分析,指出静态通用寄存器是导致软件流水失败的主要因素.提出了解决IA-64中软件流水失败的两种方法限制循环展开因子的启发式算法(RSU)和堆栈寄存器分配算法(SRA).RSU通过适当减小循环展开因子,增加了软件流水的成功率;SRA在静态寄存器和旋转寄存器之间达到了动态的平衡,提高了寄存器的利用率,更有效地提高了编译器的性能.     

一种应用于指令级并行处理器的低功耗并行度调整方案（英文）

对于指令级并行处理器(ILP,instruction level parallelism),在执行不同应用程式时,硬件资源的需求量差异很大,甚至在同一支程式中也是如此,某些空闲的硬件资源会产生额外的静态能量,提出重新设置应用程式中不同区块的执行并行度,把空闲的硬件资源关断来降低静态能量的方案,利用Core Mark Pro的标准测试集中的应用程式进行测试,静态能量降低超过40%且执行时间增加少于10%.     

嵌入式Java虚拟机实现中的代码优化

代码优化是提高Java虚拟机执行速度的重要手段之一。本文提出了一种基于预处理的代码优化方法。预处理模块与嵌入式Java虚拟机并行工作，为其标注基本块、循环等结构，并通过数据流分析收集各方法、各变量的引用次数。Java虚拟机利用预处理模块所收集的信息，判定各块程序的执行频率，对高频部分进行内联、寄存器分配等优化处理。本文还讨论了Java虚拟机实现中的若干事项。     

为具有复杂指令的嵌入式DSPs进行代码选择

研究了嵌入式数字信号处理器进行代码产生时的指令选择问题,研究复杂指令如何影响寻求最优的树覆盖,同时介绍一个两遍指令选择模型,这种选择模型能够很好的开发和利用可用的指令级并行性.这种技术和以前的工作相比能显著的提高代码的质量,这一点已经在很多的DSP上得到了验证.