基于Define-Use图的MPI通信求解算法

针对分布存储计算机系统并行编译过程中,为维持数据一致性而产生冗余通信的问题,提出一种优化的通信求解算法。该算法基于依赖关系分析和过程间数据流分析,通过遍历Define-Use图,获得更精确的通信数据,消除过程调用时产生的冗余通信。实验结果表 明,将算法所得结果作为后端生成MPI通信代码的依据,可以有效减少通信量,加速比接近手工MPI并行程序。     

基于跨基本块变换和循环分布的SLP优化技术

现有的SLP优化算法无法处理内层循环中存在的依赖环和归约,并且在基本块边界产生大量的冗余拆包和赋值语句,从而导致向量化效率不高.针对该问题,提出了一种基于跨基本块变换和循环分布的SLP优化算法.该算法以控制流图为基础,根据基本块间各数组变量的Define-Use关系以及跨越基本块之间的数据依赖关系进行跨基本块的向量化变换,有序地采用跨基本块变换和循环分布,尽可能发掘最内层循环基本块内语句的并行性,使SLP自动向量化编译器生成具有更多SIMD指令的向量化代码.实验结果表明,该算法能够隐藏更多跨基本块冗余操作的开销,同时利用跨基本决的数据依较生成更优的SIMD指令,有效地提高了向量化程序的加速比.     

程序自动并行化中的数组终写关系分析

在程序自动并行化中过程中,数据收集阶段可能产生冗余通信,该文利用数组终写关系分析的方法来消除冗余通信,实现嵌套循环中数组数据最后写关系的快速求解,并将结果提供给编译器后端,生成精确数据收集代码。描述数组终写关系的研究目的和内容,将所处理的嵌套循环根据其结构特征进行分类,给出实现算法的过程。测试结果证明了该算法的正确性和高效性,所产生的精确数据收集代码能够有效地消除部分冗余通信,从而优化和提高了并行化程序的性能。     

并行编译中对维内通信的通信优化

代码生成作为并行编译器的后端,其生成代码的优劣直接影响着并行程序的执行效率。并行分解的维内存在偏移会产生维内通信,传统算法生成的维内通信代码不够精确,会产生冗余通信。提出了通过合并数组变量生成通信链,并按照通信链生成通信代码的维内通信优化算法来消除此类冗余,对传统算法进行了改进和优化。测试结果表明该算法对维内通信的优化效果明显。     

消除冗余通信的暴露集求解算法

针对分布存储结构计算机系统在并行编译过程中存在的问题,提出一种消除冗余通信的暴露集求解算法,分另4采用数组数据流分析和自干扰分析技术对嵌套循环中的流依赖和输入依赖进行分析,从而得到暴露集空间。仿真实验结果表明,将该算法所得结果作为后端生成数据分布通信代码的依据,可有效消除冗余通信,提高系统整体性能。     

自动并行化中不规则循环的通信代码生成

不规则计算在大规模并行应用中广泛存在。在面向分布存储结构的自动并行化过程中,较难在编译时为不规则循环生成并行代码。并行代码中的通信代码对程序运行结果的正确性以及加速效果有着严重的影响。通过分析程序的数组重分布图,使用部分冗余的通信方式来维持不规则数组访问的生产者消费者关系,可以在编译时为一类常见的不规则循环自动生成有效的通信代码。该方法使用计算分解和数组引用的访问表达式求解不规则数组在各处理器的本地定义集作为通信的数据集,分析针对此类不规则循环划分的通信策略,继而生成相应的通信代码。实验测试的结果取得了预期的加速效果,验证了方法的有效性。     

利用智能控制流方法的嵌入式软件故障检测

针对现有的嵌入式软件故障检测方法性能低、开销大的缺点,提出一种智能选择检测点的控制流方法,其创新之处主要为:使用变量的频率和基本块的执行频率用作选择重要变量和基本块的两个参数。检测的基本流程是首先过滤器还原标准C语句为伪代码语句,然后扫描仪获取伪代码,并发送它到解析器,进行程序的控制流图提取。最后,解析器提取程序的前后支配树,运用候选块寻找算法进行节点分类,获得块断言和变量。实验结果表明,固化代码中程序执行时间少于RSCFC方法,但是内存开销和代码开销几乎相同,执行时间比率接近1,显著提高故障检测率。     

利用控制流识别进行二进制翻译代码缓存压缩

为了扩展动态二进制翻译产生的本地翻译块,消除因分支目标重复产生的冗余本地代码和返回代码,降低代码缓存的内存占用,提出一种基于控制流识别的代码缓存压缩策略.通过分析投机与非投机2种扩展方式的利弊,结合嵌入式程序分支指令的特征,通过分支方向和偏移量识别对应的控制流;根据控制流选择适合本地翻译块的扩展方式,压缩动态二进制翻译的代码缓存.运行嵌入式基准测试程序时的实验数据表明,在实现该策略后,QEMU二进制模拟器代码缓存的内存占用降低了10%~40%.     

基于控制流切片的代码安全缺陷检测方法

为轻松获得程序的可能执行路径,进而实现程序变量的状态跟踪,提出了一种C/C++源代码控制流提取算法,通过该模型获取控制流切片,产生局部控制流图,将数据流异常检测与安全子集检测相结合,弥补了单独使用安全子集方法无法跟踪数据流的不足,增强代码安全隐患的挖掘能力.利用控制流图化简,排除部分不可达控制流信息,提高跟踪效率.通过对3个Linux内核源文件的检测,验证了该方法不仅可以检测出违反安全子集的代码安全隐患,同时对代码数据流异常检测提供支持,准确率达94.9％.     

自动并行化中不规则循环的代码生成

许多大规模计算程序包含了不规则循环,但在面向分布存储的自动并行化中,以往的研究难以在编译时为不规则循环生成并行代码。针对一类常见的不规则循环提出了一种代码生成方法, 该方法 能在编译时将串行代码转换成等价的并行计算和通信代码,通过计算分解和数组引用的访问表达式来求解不规则循环在各处理器的本地定义集,并通过部分冗余的通信来满足不规则数组引用的生产者-消费者关系。实验结果表明,该方法是有效的,并对测试用例取得了预期的加速比。     

表驱动算法及其在C-Minus词法分析中的应用

通过表驱动算法在C-minus词法分析中的应用,使得程序消除冗余性,同时能够增强代码的可读性和逻辑性,使得词法分析这种分支很多的代码变得赏心悦目。     

A hierarchical approach to instruction-level parallelization

In this paper we extend Percolation Scheduling (PS) to navigate through a hierarchical version of the Control Flow Graph (CFG) representation of a VLIW program. This extension retains the completeness of PS by allowing the “normal” PS transformations to be applied incrementally between adjacent instructions but also enablesnonincremental code motions across arbitrarily large single-entry/single-exit regions of code in constant time. Such nonincremental transformations eliminate the useless code explosions that would otherwise be caused by using incremental transformations to move operations through regions containing multiple control paths and, in conjunction with the hierarchical representation of the CFG, provide a framework for trading offuseful code explosions for increases in parallelism. Simulation results comparing nonincremental with incremental PS are presented. This work was supported in part by NSF Grant CCR8704367 and ONR Grant N0001486K0215.     

基于Zigbee的串口通信数据流循环冗余校验方法

针对传统串口通信数据流校验方法存在识别数据能力差,校验平台智能分类效果不佳问题,提出一种Zigbee的串口通信数据流循环冗余校验方法。此次研究重新设计循环冗余校验码,基于Zigbee规划数据识别流程,通过设置循环冗余校验管理逻辑;在并行控制模式下,实现对串口通信数据流的循环冗余校验。为了验证串口通信数据流校验效果,设计对比实验。实验结果表明,此次基于Zigbee的校验方法,其识别信号波形的相似系数更接近1,该方法应用下,教学平台的智能分类效果更好。由此可见,Zigbee技术能够优化循环冗余校验法。     

采用分布式编码的协作HARQ协议

为提高协作通信系统的可靠性,将分布式编码和码合并技术相结合,提出了一种新的混合自动重传协议,构造了基于分布式Turbo码的协作重传系统模型。目的终端分别采用递增冗余和Chase合并技术处理中继节点和信源的重发信息,并进行联合软判决译码。分析了系统的中断概率和平均吞吐量。仿真结果表明,在平坦瑞利衰落信道下,该分布式编码协作HARQ协议较非协作HARQ协议可获得较大的性能改善。     

基于窄带随机过程的通信监控网络信道编码

该文研究电力线通信监控网络的窄带信道编码,通过增加冗余比特,降低误码率和丢包率,提高通信可靠性和有效性。在研究信道编码差错控制原理基础上,给出了设计中低速通信网络信道编码的基本分析思路,阐明了为提高可靠性而遵循的设计原则;在研究窄带随机过程解调检测器基本原理基础上,提出在电力线窄带通信接收机中,增加一级累加器,使信号比特能量积累换取高信噪比,并在累加器后级通过大数判决来实现检错和纠错。     

Code Based Analysis for Object-Oriented Systems

Tile basic features of object-oriented software makes it difficult to apply traditional testing methods in objectoriented systems. Control Flow Graph （CFG） is a well-known model used for identification of independent paths in procedural software. This paper highlights the problem of constructing CFG in object-oriented systems and proposes a new model named Extended Control Flow Graph （ECFG） for code based analysis of Object-Oriented （OO） software. ECFG is a layered CFG where nodes refer to methods rather than statements. A new metrics Extended Cyclomatic Complexity （E-CC） is developed which is analogous to McCabe＇s Cyclomatic Complexity （CC） and refers to the number of independent execution paths within the OO software. The different ways in which CFG＇s of individual methods are connected in an ECFG are presented and formulas for E-CC for these different cases are proposed. Finally we have considered an example in Java and based on its ECFG, applied these cases to arrive at the E-CC of the total system as well as proposed a methodology for calculating the basis set, i.e., the set of independent paths for the OO system that will help in creation of test cases for code testing.     

Reducing memory space consumption through dataflow analysis

Memory is a key parameter in embedded systems since both code complexity of embedded applications and amount of data they process are increasing. While it is true that the memory capacity of embedded systems is continuously increasing, the increases in the application complexity and dataset sizes are far greater. As a consequence, the memory space demand of code and data should be kept minimum. To reduce the memory space consumption of embedded systems, this paper proposes a control flow graph (CFG) based technique. Specifically, it tracks the lifetime of instructions at the basic block level. Based on the CFG analysis, if a basic block is known to be not accessible in the rest of the program execution, the instruction memory space allocated to this basic block is reclaimed. On the other hand, if the memory allocated to this basic block cannot be reclaimed, we try to compress this basic block. This way, it is possible to effectively use the available on-chip memory, thereby satisfying most of instruction/data requests from the on-chip memory. Our experiments with this framework show that it outperforms the previously proposed CFG-based memory reduction approaches.