谓词执行及其关键技术浅析

在超标量和VLIW微处理器的设计中,指令间的相关,尤其是控制相关和数据相关,严重限制了指令级并行(ILP)的开发,从而限制了微处理器性能的进一步提高。条件执行技术(Guarded Execution)能够将控制相关转化为数据相关来处理。具体来说,它能够将控制相关于一条分支指令的其他指令转换为数据相关于该分支条件的条件指令。条件指令与常规指令的不同之处在于它含有显式的条件指示符,其语义为:首先计算指令执行条件,如果条件为真,则执行该指令中的操作,否则将其作为空操作处理。条件执行技术实质上是一种程序变换技术,变换后的程序无论对编译优化还是对硬件调度都有很大好处,但需要专门硬件机制的支持。目前只有ARM指令集与IA-64指令集支持条件执行。     

VLIW技术的最新发展

作为一种有效提高指令级并行度的方法，超长指令字（VLIW）体系结构被看做RISC技术的自然延伸，VLIW体系结构通过编译器静脉调度发掘程序中潜在的并行性，从而有效地降低了硬件复杂度，该文结合Intel公司的IA-64体系结构与Transmeta公司的Crusoe苡片介绍VLIW技术的一些最新发展，并通过IBM的Tree-VLIW结构探讨VLIW处理器目标代码的兼容性问题。     

一种支持DSP条件执行指令的编译框架

为克服条件跳转指令的缺陷，新一代超长指令字（VLIW）体系结构的数字信号处理器（DSP）提供了对条件执行指令的支持。为使得此类指令的优势得以充分发挥，该文设计并实现了一种基于hyperblock区域结构的编译框架。实验结果表明，该框架很好地提高了指令级并行虚（ILP），减少了指令执行时间。     

VLIW DSP指令级精度模拟器的快速实现方法

为了以最小代价开发出超长指令字(VLIW)数字信号处理器(DSP)的指令级精度的模拟器,缩短开发周期,提出了一种基于开源模拟器(gem5)的开发方法.对gem5模拟器和VLIW DSP的指令执行流程分别进行分析,指出指令在gem5模拟器上以纯32位指令环境顺序执行和指令在VLIW DSP上以16/32位混合指令环境并行执行之间的矛盾是开发的难点.在gem5的顺序执行模型的基础上,通过加入并行的判决、执行机制和16/32位混合指令的取指机制建立了VLIWDSP的模型,并具体实现了一款VLIW DSP的模拟器.通过一组针对每条指令的测试程序和一组DSP典型应用程序验证了该方法的正确性和可行性.     

一个RISC流水结构机器QHRC上的编译时指令调度器

RISC体系结构常采用流水结构来提高机器的执行速度.然而,指令互锁现象的频繁出现严重影响了机器的执行效率.本文给出了一个流水结构机器上的基于机器描述表格化及参量化的指令调度算法。并利用该指令调度器作为工具,对多种解决指令互锁方案效果进行分析.最后,给出了一种兼顾硬件可行性与软件有效性的解决指令互锁的高性能方案。该算法的复杂度为O(n~2)。     

分簇结构超长指令字DSP编译器的设计与实现

超长指令字（VLIW）是高端DSP普遍采用的体系结构。VLIW DSP在硬件上没有调度和冲突判决的机制，其性能的发挥完全依靠编译嚣的优化效果．基于可重定向编译基础设施IMPACT，为分簇VLIW DSP YHFT—D4设计与实现了优化编译器．其中着重讨论了可重定向信息的定义、代码注释、SIMD指令的支持、分簇寄存器分配以度指令级并行开发和资源冲突解决等内容．实验结果表明该编译器可以达到较好的优化效果．     

GCC下基于引用次数的VLIW编译技术研究

VLIW机器的并行特性,导致其以最大限度地提高执行效率作为评判编译器性能的依据,而现今局部调度的使用已达到瓶颈.本文讨论了基于引用次数的全局trace调度在VLIW结构的MISC3270系统上的实现,它克服了目前局部list调度只能在基本块内部进行优化的限制,大大提高了系统的ILP.     

基于GCC的VLIW编译系统研究

VLIW机器在单个机器周期中同时发射并执行多个的并行操作,从而获得较高的指令级并行度,这些操作之间的依赖分析和调度工作则被完全交给相应的编译器执行,因此VLIW的并行性能能否充分发挥取决于VLIW体系结构相关编译器的质量。GNU开发的GCC是被最广泛使用的编译系统之一,它具有多语言、多平台支持的能力和开放的结构,能够运用各种成熟的常规编译优化技术生成高效的代码。文章分析了VLIW及GCC的结构特点,提出了一种基于GCC的VLIW编译系统设计方案,利用GCC进行RTL中间代码一级的体系结构无关优化和少量体系结构相关优化,在汇编代码一级针对VLIW结构进行体系结构相关的优化,从而充分利用GCC的成熟编译技术快速开发高效的VLIW多语言编译系统。     

一个基于DAG图的指令调度优化算法

指令调度是优化编译技术中一项关键技术,对于VLIW体系结构的CPU,指令调度显得尤为重要。指令调度是在保证语义正确的前提下,改变指令的执行顺序,减少流水线中的空闲周期,从而提高CPU性能的一种优化方法。文章着重分析了优化编译中的指令调度问题,提出了一个指令调度算法和DAG图的一种化简方法,证明了算法的正确性,分析了算法的效率,比较了生成的新指令序列和最优的指令序列总的执行时间的差别。同时,针对目前流行的编译器GCC的指令调度算法中存在的问题,提出了一个较好的解决途径。     

面向VLIW处理器的分支调度优化算法

分支调度是一种有效消除分支指令延迟的指令调度技术,对于提升VLIW类处理器的性能非常重要。提出了一个针对分支延迟槽的指令调度优化算法。该算法面向VLIW体系结构,根据程序依赖图选择合适的候选指令序列;通过建立代价收益模型为分支延迟槽产生一个收益较大的指令调度序列。实验数据表明,分支调度算法可以平均提升12.9%的应用程序性能。     

协作式全局指令调度与寄存器分配

指令级并行是现代高性能代理器的重要特征,对于发挥这类处理器所具有的并行处理能力来说,编译器有至关重要的影响。文中讨论指令级并行编译中的核心问题－全局指令调度与 器分配,并以作者为一种新型的显式并行体系结构微处理器的编译系统为背景,介绍了此类编译器后端设计中面临的指令调度与寄存器分配的时序问题,以及为解决这一问题而提出了的一种协作式全局指令调度与寄存器分配方法。     

分簇VLIW DSP调度技术*

分簇VLIW DSP在减少硬件设计复杂性的同时,显著地增加了编译器进行指令调度的难度。提出通过在调度中首先进行指令簇划分然后再簇内调度,这样在增加很少几条拷贝指令的条件下充分利用分簇的特性提高指令的并行度,减小调度时间。     

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

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

On the Boosting of Instruction Scheduling by Renaming

Speculative execution is the execution of instructions before it is known whether these instructions should be executed. In the speculative execution for instruction level parallelism (ILP) processors, the concept of shadow register provides a hardware solution to maintain semantics of a program from the pollution of boosted instructions that are incorrectly predicted. In a recent study, Chang and Lai proposed a special register file based on shadow register, named conjugate register file (CRF), to support multilevel boosting in speculative execution. They also proposed a scheduling heuristic named frequency-driven scheduling to incorporate with CRF for execution. However, the ability of boosting is still constrained since the concept of register pair will force the results produced speculatively be stored in dedicated locations. Moreover, when the parallelism potential increases to tens through the advancement of hardware techniques, the heavy demand on register usage and the complexity of register file may well become a serious bottleneck for the exploitation of ILP.In this paper, the algorithm of frequency-driven scheduling is modified by replacing the function of hardware CRF with the technique of variable renaming during compilation. The new scheduling technique, named LESS, can exploit the parallelism efficiently with limited number of registers. Moreover, since the technique can benefit ILP without any special hardware support, it can be incorporated with any other ILP architecture without changing its instruction set architecture (ISA).Simulation results show that the performance achievable by LESS is better than other existing methods. For example, under the ILP model with an issue rate of 8, the speculative execution can achieve an increase of 34% in parallelism, as compared to 18% in CRF scheme.     

全局指令调度综述

指令调度通过调整指令之间的顺序来提高指令级并行度(ILP)。然而基本块通常很小,因而潜在的ILP也很小。随着芯片设计技术的发展,现代的处理机所包含的资源却越来越丰富。指令调度只有跨越基本块的边界(即全局指令调度)才能够充分发挥处理机潜在的和程序中固有的ILP。全局指令调度可划分为有环和无环两种。该文介绍了无环全局指令调度的几种影响力较大的算法。同时还简单介绍了有关全局指令调度的新的热点。     

寄存器堆互连的VLIW结构及其指令调度算法

超长指令字(Very Long Instruction Word,VLIW)处理器一般采用总线互连的多簇结构,每个簇中的功能单元共享一个本地寄存器堆,簇间采用总线传输数据,以避免功能单元增多时,全连通结构的延时、面积和功耗的快速增长;但簇间数据共享时的拷贝和延时,使得处理器在性能上有所下降.文中提出了一种寄存器堆互连的多簇VLIW结构,采用寄存器堆来连接各个簇,从而可以避免簇间数据传输的延时和额外的数据拷贝操作.同时也提出了针对这种结构的指令调度算法,以提高指令调度的性能.实验结果表明,与全连通的VLIW结构相比,寄存器堆互连结构在性能上仅有13%左右的性能下降,代码长度则基本不变;这都优于总线互连的多簇结构.     

The superblock: An effective technique for VLIW and superscalar compilation

A compiler for VLIW and superscalar processors must expose sufficient instruction-level parallelism (ILP) to effectively utilize the parallel hardware. However, ILP within basic blocks is extremely limited for control-intensive programs. We have developed a set of techniques for exploiting ILP across basic block boundaries. These techniques are based on a novel structure called thesuperblock. The superblock enables the optimizer and scheduler to extract more ILP along the important execution paths by systematically removing constraints due to the unimportant paths. Superblock optimization and scheduling have been implemented in the IMPACT-I compiler. This implementation gives us a unique opportunity to fully understand the issues involved in incorporating these techniques into a real compiler. Superblock optimizations and scheduling are shown to be useful while taking into account a variety of architectural features.     

Code scheduling for multiple instruction stream architectures

Extensive research has been done on extracting parallelism from single instruction stream processors. This paper presents our investigation into ways to modify MIMD architectures to allow them to extract the instruction level parallelism achieved by current superscalar and VLIW machines. A new architecture is proposed which utilizes the advantages of a multiple instruction stream design while addressing some of the limitations that have prevented MIMD architectures from performing ILP operation. A new code scheduling mechanism is described to support this new architecture by partitioning instructions across multiple processing elements in order to exploit this level of parallelism.     

Combining Height Reduction and Scheduling for VLIW Machines Enhanced with Three-Argument Arithmetic Operations

In here we consider a technique to automatically extract three-argument instructions from sequential arithmetic code. The instructions include: multiply and add, three argument additions and three argument multiplications (MUL3). The proposed solution combines a height reduction technique that generates three-argument instructions and a VLIW scheduling that can benefit from these instructions. The proposed height reduction technique is based on a known theoretical algorithm (MRK) that in some cases can evaluate an algebraic circuit faster than its depth. We modified the MRK algorithm to generate less instructions and emit VLIW instructions. The modified MRK algorithm was implemented in the LLVM compiler and the potential usefulness was measured. Our results show that for arithmetic benchmarks the proposed technique can improve the VLIW scheduling while emitting three-argument instructions. The contribution of this work includes: the modified MRK algorithm as a new technique for height reduction optimizations and the study of the potential usefulness of three-argument instructions. Though our results are for a non existing hardware they show the usefulness of adding such instructions to VLIW CPUs. Note that a previous research showed that MUL3 can be executed as fast as MUL2.