IA-64二进制翻译中旋转寄存器的处理方法

寄存器旋转技术为每一个循环迭代都提供一组专用的寄存器,从而减少对循环展开的需求。针对如何在IA-64二进制翻译中处理旋转寄存器的问题,提出一种在二进制翻译器的后端直接模拟寄存器旋转特性的解决方案,实验结果证明了该方法在二进制翻译中处理软件流水操作代码的有效性。     

IA-64二进制翻译中软件流水代码消除技术

IA-64体系结构使用软件流水提高程序的执行性能,但产生的二进制代码跟机器特性紧密相关,给代码跨平台移植造成了困难。该文针对IA-64体系结构下软件流水的特点,提出2种软件流水代码消除方法,它能够将软件流水代码转换成语义等价无硬件依赖的串行代码,实验验证了这2种方法的有效性。     

IA-64二进制翻译的软件流水消除技术

在逆向工程中,软件流水循环为逆向翻译带来了困难。针对如何在IA-64二进制翻译中处理软件流水循环提出一种解决方案,采用直接语义映射算法,并通过实验验证该算法在二进制翻译中处理软件流水代码的有效性,为在IA-64二进制翻译中处理软件流水代码奠定了基础。     

IA-64软件流水的反流水算法研究

软件流水是一种开发循环程序指令级并行性的技术, 它通过并行执行连续的多个迭代来加快循环的执行速度。而在逆向工程中,软件流水却为逆向翻译带来了困难。为此,基于IA-64平台,提出了一种反流水算法,针对循环中包含软件流水的汇编代码进行处理,将其反向转换成语义等价的串行代码,并通过实验验证了该算法的有效性,为在二进制翻译中处理软件流水代码奠定了基础。     

一种IA-64下的反软件流水算法

软件流水是一种循环程序的优化技术,它可以有效地提高指令级并行性。由于处理机的实现方法各不相同,在一种处理机上经过软件流水优化后的循环代码很难在其它处理机中移植和使用。反软件流水是软件流水的逆向操作,它可以消除循环代码中的软件流水特性,以便于代码在不同平台上的移植。基于IA-64体系结构,分析了软件流水的代码特点,提出了反流水算法,用于将ICC编译器编译后的可执行二进制代码消除软件流水特性,转换成语义等价的C代码。     

IA-64中软件流水的寄存器需求研究

软件流水是开发循环程序指令级并行性的重要方法之一,IA-64是支持软件流水的EPIC体系结构,通过对NAS Benchmarks中可软件流水循环所需的寄存器进行量化分析,提出了一种限制循环展开因子的启发式算法,有效地解决了因可用寄存器不足而导致软件流水失败的问题,并提高了应用程序的执行速度。     

IA-64二进制翻译中跳转表恢复技术

基于IA-64体系结构下二进制翻译系统,本文提出了应用过程内静态切片技术恢复索引跳转中跳转表以及目标地址的解决方案。并通过在IA-64体系结构上对C和C 编译器产生的代码进行测试,表明通过该技术可以很好的解决二进制翻译中跳转表的恢复问题,提高二进制解码的覆盖率。     

IA-64二进制翻译中跳转表恢复技术

基于IA-64体系结构下二进制翻译系统,本文提出了应用过程内静态切片技术恢复索引跳转中跳转表以及目标地址的解决方案.并通过在IA-64体系结构上对C和C++编译器产生的代码进行测试,表明通过该技术可以很好的解决二进制翻译中跳转表的恢复问题,提高二进制解码的覆盖率.     

IA-64二进制翻译中指令束特性的消除技术

目前对处理器速度的追求促使指令集体系结构不断发展,但是软件的支持却不能与其匹配,造成新体系结构推广的困难,研究、解决代码迁移问题的二进制翻译方法应运而生。文中介绍了二进制翻译中解码器的功能,并结合IA-64的指令特点,设计出基于指令束的解码算法。根据测试中发现该算法存在的问题,提出了改进方案,消除束的特性,给每条指令赋予唯一地址并按此地址进行解码。在IA-64至Alpha的二进制翻译课题中,对该算法进行了工程实现。     

基于加载机制分析的ELF文件main函数定位技术

当前二进制翻译中通用的main函数定位方法依赖于符号表,随着strip工具的普遍应用,二进制可执行文件中往往不存在符号表。该文描述了strip工具的应用目的,分析了其应用对二进制翻译的影响,基于ELF文件加载机制的分析,提出了一种新的main函数定位技术,通过对IA-32及IA-64下ELF格式二进制文件的翻译,证明该技术是有效的。     

3种提高软件流水有效性的算法:比较和结合

软件流水是开发循环程序指令级并行性的技术,它通过并行执行连续的多个循环体来加快循环的执行速度.在软件流水中,循环体的重叠增加了寄存器需求,导致寄存器压力增大,当目标处理机所提供的寄存器不足时,软件流水可能失败.在Itanium处理机上评估了NAS和SPEC2000基准程序中的软件流水循环的寄存器需求,发现静态寄存器不足是造成软件流水失败的主要原因,提出了3种增加软件流水个数、提高软件流水有效性的算法:限制循环展开因子的算法(register sensitive unrolling,简称RSU)、堆栈寄存器分配算法(stacked registerallocation,简称SRA)以及变量类型转换的算法(variabletype conversion,简称VTC).RSU根据静态寄存器需求确定一个合理的展开因子,增加了软件流水的成功率;SRA和VTC分别使用空闲的堆栈寄存器和旋转寄存器来充当静态寄存器,提高了寄存器的利用率.在面向Itanium处理器的开放源码编译器ORC(open research compiler)上实现了这3种算法,通过NAS程序的测试比较了这3种算法的有效性,同时对它们的结合应用进行了研究和实验.     

Time Optimal Software Pipelining of Loops with Control Flows

Software pipelining is widely used as a compiler optimization technique to achieve high performance in machines that exploit instruction-level parallelism. However, surprisingly, there have been few theoretical or empirical results on time optimal software pipelining of loops with control flows. In this paper, we present three new theoretical and practical contributions for this underinvestigated problem. First, we propose a necessary and sufficient condition for a loop with control flows to have an optimally software-pipelined program. We also present a decision procedure to compute the condition. As part of the formal treatment of software pipelining, we propose a new formalization of software pipelining. Second, we present two software pipelining algorithms. The first algorithm computes an optimal solution for every loop satisfying the condition, but may run in exponential time. The second algorithm computes optimal solutions efficiently for most (but not all) loops satisfying the condition. The former one proves the sufficiency of the condition and the latter one suggests a practical optimal software pipelining algorithm. Third, we present experimental results which strongly indicate that achieving the time optimality in the software-pipelined programs is a viable goal in practice with reasonable hardware support.     

Optimizing modulo scheduling to achieve reuse and concurrency for stream processors

Both reuse and concurrency are performance-critical for stream processors. When applying loop unrolling and software pipelining separately to stream-level loops, either reuse or concurrency or both may be inadequately exploited. In this paper, we optimize modulo scheduling to maximize stream reuse and improve concurrency for stream-level loops. The key insight is that an unrolled and software-pipelined stream-level loop could be described by a set of reuse equations. Guided by reuse equations, a reuse-aware modulo scheduling algorithm is developed to simultaneously optimize the two performance objectives, reuse, and concurrency, for a loop in a unified framework. Moreover, we describe a code generation algorithm to automatically produce the optimized loop from a given loop. The experimental results obtained on FT64 and by simulation demonstrate the effectiveness of the proposed approach.     

Minimizing Register Requirements of a Modulo Schedule via Optimum Stage Scheduling

Modulo scheduling is an efficient technique for exploiting instruction level parallelism in a variety of loops, resulting in high performance code but increased register requirements. We present an approach that schedules the loop operations for minimum register requirements, given a modulo reservation table. Our method determines optimal register requirements for machines with finite resources and for general dependence graphs. Measurements on a benchmark suite of 1327 loops from the Perfect Club, SPEC-89, and the Livermore Fortran Kernels show that the register requirements decrease by 24.8% on average when applying the optimal stage scheduler to the MRT-schedules of a register-insensitive modulo scheduler.     

一种软件流水的反流水算法

软件流水是一种循环程序的优化技术,已经广泛应用于现代优化编译器中.为了充分利用VLIW DSP处理机的指令级并行性,必须使用软件流水技术对DSP程序进行优化.然而,在串行源代码不存在的情况下,对软件流水后的原始代码进行变换、理解、测试和调试,并转换成其他处理机的代码是非常困难的.提出了一种反流水技术,它能够将软件流水后的优化汇编代码反向转换成语义等价的相应代码.通过20个程序的初步实验,验证了所提出的反流水算法的正确性.     

一种支持多重循环软件流水的寄存器结构

寄存器结构及其分配是软件流水算法的关键之一.为支持多重循环的软件流水,该文提出一种新颖的寄存器结构：半共享跳跃式流水寄存器堆.它可以有效地解决多重循环软件流水下的特殊问题,即：同层次和跨层次的寄存器重命名问题以及断流问题;有效地消除外层循环的体间读写相关,提高程序的指令级并行度.它有3种分配方式可供灵活使用：单个寄存器、流水寄存器和寄存器组方式.流水寄存器方式对生存期确定的、局限于一个循环层次的寄存器重命名问题提供简单而有效的支持.寄存器组分配方式解决了多重循环软件流水时变量生存期不确定的情况.跳跃操作为     

依赖距离主导的向量化方法研究*

向量寄存器的非满载使用方式为大量迭代次数不足的循环提供了向量化的机会,但也导致向量化的并行宽度不固定,传统的向量因子主导的依赖测试方法不再适用。本文提出了一种依赖距离主导的依赖测试方法,通过分析依赖图中所有依赖环的破环关键边所携带的依赖距离,选择其中最小的依赖距离来决定并行宽度,破除依赖环,实现基于向量寄存器非满载使用方式的向量化。实验结果表明,该方法能够有效增加循环向量化的机会和提高向量寄存器的使用率,测试用例的向量化加速比平均提高14.6%。     

基于梯度方向角量化的匹配新算法

提出了一种在复杂光照环境下具备旋转不变识别能力的匹配新算法。图像梯度方向角是一种在光照变化及目标发生旋转的情况下保持相对稳定的特征量。通过对该特征量的量化与统计分析,分2步实现在变化的光照条件下旋转目标的识别：(1)统计子图像块梯度方向角量化值的直方图,大概确定出目标旋转的角度;(2)利用确定的角度值对模板图像的梯度方向角量化值与子图像的量化值进行旋转匹配。实验证明该算法具有较强的鲁棒性。     

SIMD向量指令的非满载使用方法研究

大规模SIMD体系结构提供了更强的向量并行硬件支持,但是,大量迭代次数不足的循环由于不能提供足够的并行性,难以用等价的向量方式实现。为了更有效地利用SIMD,提出了一种非满载地使用SIMD指令的向量化方法。研究了向量寄存器的使用方式,基于非满载的向量寄存器使用方式实现了非满载的向量操作和短循环的向量化,并将非满载的向量化方法用于一般循环的向量化。提供了收益分析方法来为本向量化方法作精确指导。实验结果表明了该方法的有效性,所选测试用例的目标循环被向量化,平均加速比达到1.2。