可定制Tcore处理器指令调度设计

魏继增，郭 炜，孙济洲

(天津大学计算机科学与技术学院，天津 300072)

当前，嵌入式微处理器在很大程度上决定了嵌入式系统的性能，主流微处理器,如 ARM、MIPS、PowerPC等均是基于通用目的设计的，功能强大，支持多种运算及数据类型．但由于嵌入式系统面向多个领域，处理的问题千差万别，导致这种通用性大大限制了其开发特定领域并行性的可能，出现整个系统速度偏低、成本较高的问题．一个解决办法是针对特定应用设计专用集成电路(application specific integrated circuit，ASIC)，但 ASIC 缺乏灵活性且设计成本高、设计周期过长．

专用指令集处理器(application specific instruction processor，ASIP)的出现克服了上述缺点，可针对特定任务定制指令集及处理器架构，既保持了处理器的灵活性也使性能接近 ASIC，系统具有实时、功耗小、成本低、上市时间短等优势[1]．在国外，ASIP的研究开展得很早，各研究机构以及工业界已取得了很大的进展，如 Tensilica公司的 Xtensa[2]和 Improv公司的Jazz都已得到广泛应用，而针对ASIP的编译器设计是重中之重，直接关系到ASIP的成败．

Tcore处理器是天津大学超大规模集成电路设计与应用研究所设计的具有自主知识产权的基于传输触发体系结构(transport triggered architecture，TTA)的 ASIP，并已完成多款不同配置的 0.13,μm 宏利下的工艺流片，工作主频可达到 200,MHz，拥有良好的产业化前景．Tcore处理器采用指令级并行技术，其最大特点是数据传输细节在体系结构级可见，因而拥有理想的性能/价格比，与其他ASIP相比具有巨大优势．但其将硬件设计复杂度转移到软件之上，大大加重了可重定目标编译器的负担，因此如何设计出高效编译器将成为Tcore处理器得以广泛推广的关键．笔者提出一种基于 Tcore处理器的编译器架构，并主要针对后端编译中的指令调度问题进行阐述．

1 传输触发体系结构及Tcore处理器

1.1 传输触发体系结构

传输触发体系结构是类似于超长指令字(very long instruction word，VLIW)结构，两者均包含多个功能单元(function unit，FU)．但 TTA 指令不是传统的通过对 FU进行编程触发数据传输，而是通过对数据传输进行编程触发不同的 FU 操作[3]，其体系结构如图1所示．TTA核心为数据传输网络，由多条总线构成．所有的功能单元以及寄存器堆(register file，RF)通过标准接口与总线进行互连．此接口使得 FU、RF与总线松耦合连接，用户可根据应用通过增减FU以及改变总线数目与宽度满足特定的性能要求．另外，TTA不同于传统 VLIW 的另一个特点是 FU、RF与总线为非全连接机制，通过去除不必要的连接实现低功耗的要求．

图1 TTA体系结构Fig.1 Architecture of TTA

基于TTA指令只包含一种操作：move，其与传统RISC指令对比如下所示：

每个 FU包含 O、T和 R三类寄存器，当数据被传送到寄存器 T便触发相应 FU的操作．TTA最大的优势是使数据传输在体系结构级可见，程序员可以对处理器进行更细粒度的控制，去除很多不必要的数据传送．为了充分发挥TTA架构处理器的性能，必须在同一指令内包含多条独立的数据传输以增加并行性，导致属于同一 FU操作的多条数据传输由于依赖性被分配到不同的指令中，增加了指令调度与寄存器分配难度[3]．

1.2 Tcore处理器

Tcore虽然采用了TTA架构，但根据 ASIP的要求进行了优化，其特点如下所述．

(1)Tcore被设计为一种轻量级处理器，去除了原先基于 TTA架构处理器中对于操作系统的支持，被定位为协处理器，主要负责计算密集型的任务，以配合功能强大的通用处理器工作．

(2)Tcore采用了混合立即数指令格式，与传统TTA处理器相比具有更高的指令密度．

(3)Tcore增加了调试模块，使得程序设计者可以方便地对程序进行硬断点以及硬单步调试．

2 基于Tcore的编译器架构

传统的基于TTA架构处理器的编译器主要是通过 GNU GCC技术组织实现，如 Delft大学的MoveFramework[4]．采用这种方式，串行的 TTA 指令被表示成二进制文件格式．而这种格式灵活性很低，缺少程序剖析信息，即使存在，这些信息也被独立组织，缺乏和程序本身的联系，势必造成在后端编译过程中无法生成高质量的指令级并行代码．因此采用中间格式来代替这种二进制格式将解决上述问题，因为中间格式更利于保存和组织大量剖析信息，从而能够进行更加复杂的代码分析和代码转化．基于此思想组织的Tcore编译器架构如图2所示[5]．

此架构采用由 Stanford大学开发的 SUIF2与MACHSUIF构造编译器前端．SUIF2负责将应用的高级语言描述转化为第一级中间表示 SUIF IR并将其输入给 MACHSUIF进行后续处理．MACHSUIF是一个便于构造编译器后端的，可扩展的编译框架．利用它可以快速地构造机器语言级中间格式．MACHSUIF将SUIF IR转化为面向其内部定义的虚拟机的机器语言级中间表示，即第二级中间表示SUIFVM．MACHSUIF的一个重要组件 Machine Library Interface为用户提供了统一标准的接口以扩展用户所需机器架构，如 x86、alpha、Tcore等，并将SUIFVM 转化为串行 Tcore处理器代码[6]．串行的Tcore代码被输入到编译器后端即代码生成器以得到特定架构Tcore处理器的指令级并行程序．

代码生成器主要完成两个 NP完全问题：指令调度与寄存器分配．本架构采用启发式算法如表调度、线性规划[7-8]、模拟退火和遗传算法[9-10]等完成上述任务．此外由于不同应用具有各自特点，用户对程序编译性能要求也可能千差万别，本文所给出的编译器架构与传统的架构相比增加自适应中间层通过超启发式算法自动地根据各种限制条件与约束选择合适的算法完成这两部分任务．

图2 基于Tcore的处理器的编译器架构Fig.2 Compiler structure based on Tcore processor

3 基于Tcore的处理器的指令调度

3.1 体系结构描述文件

基于TTA架构的Tcore处理器随应用不同而不同．因此，编译器的设计必须考虑可重定目标的要求，每款 Tcore处理器体系结构参数被有机组织起来便于编译器使用．如图 2所示的编译器架构，其中体系结构解析器模块便是完成这项工作的．处理器所有体系结构信息被记录到一个称为 Tcore体系结构描述文件的文件中，如表1所示．ADT中的所有参数设置被组织为 XML格式，便于编译器后端进行解析．

表1 ADT中Tcore处理器参数设置Tab.1 Parameters of Tcore processor in ADT

3.2 基于表调度与关键路径的混合指令调度策略

表调度是一种解决任务调度问题的优秀算法，目前已被广泛应用到指令级并行处理器的编译器设计中，以获得较短编译时间以及较好的编译质量[11]．表调度的本质就是按照操作的拓扑顺序对其进行选取，然后将这些操作分配到各个指令当中去．拓扑顺序由一个称为数据依赖图的带权有向图决定．

定义 1GDDG=(N，E)，其中 N 是所有操作的集合，每个操作对应 N中的一个顶点，E是所有数据依赖边的集合，即 E={(ni，nj)|,ni，nj∈N,∧,ni必须在 nj之前执行}，每条数据依赖边上的权值表示 ni操作的延时．

一个操作被调度必须等到它的所有前序操作都已调度完．表调度共有两种类型：基于指令的调度和基于操作的调度．前者指以指令为分配单位，一次须选取尽可能多的操作安排在当前指令中，直到当前指令不能再分配才去处理下一条指令．而后者正好相反，以操作为分配单位，一次只选取一个操作安排到相应指令中，不要求必须将一条指令全部处理完．从实现难度上，基于指令的调度更容易，已有的基于TTA架构的编译器如MoveFramework正是基于此调度的．但基于 TTA架构的处理器将数据传输作为基本单位，若采用基于指令的调度可能会造成多个功能单元竞争计算资源产生死锁．此时 MoveFramework会通过延迟调度释放资源，这样势必降低并行度增加了程序运行时间，从而影响系统性能．本文提出的算法将使用基于操作的调度，在选取时可将包含若干数据传输的一个完整操作作为单位，而在调度时以数据传输为单位，这样将会避免死锁的出现．

除了考虑指令调度所选取的算法外，指令调度的范围也至关重要，主要包括基于基本块的调度和基于全局的调度．本文采用的是基于基本块的调度．基于Tcore处理器的基本块范围内的表调度算法如图3所示，包含两个关键部分，操作选取阶段OpSelect Phase(ready)以及调度阶段SchedulePhase(o)．

OpSelectPhase(ready)按照 GDDG的拓扑顺序，从ready集中选取当前可以调度的操作．当有多个操作可供选择时，选取的顺序将在很大程度上影响最后的性能．MoveFramework使用随机选取方式，即当有多个操作可调度时随机选择一个进行调度，此方法将平等对待所有可调度操作，没有考虑各操作对系统性能的影响，严重影响了目标代码的性能．本文将采用基于关键路径的方法对操作进行选取，位于此路径上的操作是影响整个系统的瓶颈，应该尽可能早的被调度．被选取调度的操作Os可由文献[12]的式(1)式(3)计算所得，est(oi)、lst(oi)分别是操作 oi最早和最晚可调度时刻，cp是关键路径长度(关键路径上所有操作的延时之和)，latency(oi，oj)表示两个操作之间的延时，即GDDG中连接oi和oj的边上的权值．

图3 基于Tcore的基本块范围内的表调度算法Fig.3 List scheduling algorithm based on Tcore in filed of basic block

为了避免死锁，此时 GDDG中所有节点代表的都是一个具有独立功能的操作，每个操作可能包含一个或若干个数据传输．所有的操作可分为以下几类：单一数据传输、子函数调用、分支以及数据计算．前 3类操作一般只包含一个数据传输，调度简单．而数据计算类操作，如加法运算、乘法运算和逻辑运算等都需要多个数据传输才能完成，调度较复杂．因此只讨论数据计算类操作的调度．

3.3 数据计算类操作的调度策略

任意一个数据计算类操作 o均包括若干个数据传输dmv．这些数据传输分别是将各种数据传送到相应功能单元FU的O类、T类寄存器以及将计算结果从 R类寄存器送到总线，将此 3种传输分别记作Odmv、Tdmv和Rdmv．在图3所述算法中，Schedule-Phase(o)针对数据计算类操作要分别完成对这 3种传输的调度．调度的原则除了要遵循数据依赖这个重要约束外，根据 Tcore处理器的特点还应满足以下约束．

(1)同一操作的T类寄存器的数据传输不能早于O类寄存器的数据传输之前完成，即 Instruction-Num(Tdmv)≥InstructionNum(Odmv)，其中 InstructionNum()指相应数据传输所在指令的序号．

(2)R类寄存器的数据传输不能在相应 FU计算完成之前启动，即 InstructionNum(Rdmv)≥InstructionNum(Tdmv)+latency(o)．

(3)在同一时刻，不能向任何相同寄存器同时写入任何数据．

(4)除了以上数据传输的约束之外，调度时还需考虑此刻是否有足够的硬件资源进行分配，包括 FU的分配、总线的分配以及连接的分配．

数据计算类操作的调度算法如图 4所示．其中，EInstructionNum()为某个数据传输 dmvi最早可被调度分配的指令序号，通过式(4)进行计算．sset(dmvi)指与数据传输 dmvi存在数据依赖且已完成调度的所有传输的集合．策略第二步判断当前时刻是否有合适的FU分配给操作o，Oset(fu)指此FU所包含的操作的集合．

图4 数据计算类操作的调度算法Fig.4 Scheduling algorithm of data computation operations

ScheduleTdmv()、ScheduleOdmv()以及 Schedule Rdmv()分别表示对T、O、R三类寄存器传输的调度，如图5～图7所示．

图5 ScheduleTdmv()Fig.5 ScheduleTdmv()

图6 ScheduleOdmv()Fig.6 ScheduleOdmv()

对于 ScheduleTdmv()，首先判断此 FU的 T类寄存器是否被占用，以保证约束(3)．然后分别判断是否在指令 i中有空闲的总线和连接资源可用，当以上3个条件任何一个不符合时，ScheduleTdmv()调度失败，将对此T类寄存器数据传输最早可调度的指令序号 i，即 EInstructionNum (Tdmv(o))进行递增，直至找到可调度安排此数据传输的指令．

对于 ScheduleOdmv()，首先判断是否满足约束(1)．对 O 类寄存器的数据传输进行调度时，调度范围为[EInstructionNum(Odmv(o))，i]，开始时将对此数据传输调度的指令序号设为 i，即与同一操作的 T类寄存器的数据传输在同一指令中被调度．否则可能出现对O类寄存器和T类寄存器的数据传输调度的位置相差太远的问题，从而导致在这一时间段硬件资源一直被占用，进而影响调度的性能．调度过程中所需判断的条件与 ScheduleTdmv()相同．每个 FU可能有多个 O类寄存器，因此要对每个 O类寄存器的数据传输均要完成上述步骤．

对于 ScheduleRdmv()，为了满足约束(2)，R 类寄存器数据传输可被调度的起始指令编号必须取同一操作 o的T类寄存器数据传输所调度的指令编号与此 FU的延时之和与 EInstructionNum(Rdmv(o))的最大值．Conflict(fu，i′)为了避免在调度过程中可能出现的某个FU的R类寄存器的值还没有被使用，即被后续运算的新值所覆盖，从而造成程序执行结果发生错误．同样 ScheduleRdmv()也应考虑当前指令是否有合适总线和连接可以分配．

图7 ScheduleRdmv()Fig.7 ScheduleRdmv()

4 实验结果与分析

为了评价所提出的面向 Tcore处理器的基于表调度的指令调度策略的性能，选择了两种架构 Tcore处理器作为评价所用的目标机．在这两种配置中，假设所用功能单元与总线采用全连接方式．

(1)具有 4条总线，1个 load_store单元(用于从存储器中读取数据)，1个算术逻辑单元，1个乘法功能单元，1个比较功能单元，1个移位功能单元，1个全局控制单元．

(2)具有 4条总线，2个 load_store单元(用于从存储器中读取数据)，2个算术逻辑单元，2个乘法功能单元，1个比较功能单元，1个移位功能单元，1个全局控制单元．

实验采用C语言描述的TI C64 plus系列DSP测试程序[13]作为基本测试用例，性能分析如表 2所示．同时通过 MoveFramework工具集完成相同的硬件配置，在其上运行同样的基本测试用例，与本文所提出方法进行比较以验证所提出方法的高效性，其结果如表3所示．由于Tcore处理器采用的是传输触发体系结构，而 MoveFramework也是基于此架构设计的，因此具有可比性．测试所用 DSP算法中，向量内积与向量矢量加法所使用的一维向量均包含16个元素．为了提高并行性，在测试程序的高级语言描述一级手工完成循环分解以及函数内联．

由表 2、表 3的实验结果可知，情况(1)配置下本文所提出的算法与MoveFramework的平均指令级并行度较低，分别为1.55和1.28．这主要因为在情况(1)配置中虽然并行数据传输能力较高，为 4条总线，但每种计算功能单元只有 1套，存取数单元也只有 1套，因此同一时刻同种运算只能进行一次．而所选取的 DSP测试用例均具有对不同的数据进行相同计算的特点(计算密集型)，所以在情况(1)配置下性能提高有限．但本文所提出调度算法的并行度比 Move-Framework仍提高了 0.17倍，主要因为 MoveFramework采用传统的GCC二进制格式构建串行代码，缺乏剖析信息，无法深层次挖掘数据传输上的并行性．而本文所提出的算法采用中间语言格式，具有大量传输统计信息，有利于构建高效编译器后端．

表2 基于中间格式的表调度与关键路径混合指令调度算法性能分析Tab.2 Performance analysis of instruction scheduling based on intermediate format and critical path

表3 基于GNU GCC的MoveFramework指令调度性能分析Tab.3 Performance analysis of MoveFramework instruction scheduling based on GNU GCC

情况(2)的配置与情况(1)的配置传输能力相同，但计算功能单元增加了 1倍．本文所提调度算法的平均指令级并行度大约为 3.06，性能为情况(1)配置下的 2倍左右，比 MoveFramework在相同配置下的平均指令级并行度 1.88提高了大约 0.63倍，结果令人满意．除上述中间格式所带来的优势外，最主要的原因为本文在表调度算法基础上引入了关键路径的计算，当有多个操作可调度时优先选取对系统性能影响最大的操作进行调度，从整体上缩短了代码长度，而 MoveFramework采用随机调度方法，因此性能较差．此外采用了基于操作的表调度方法，与 Move-Framework所使用的基于指令的调度方法相比，减少了发生死锁的可能，从而能够产生更高质量的代码．在后续实验中还发现即使继续增加硬件资源，并行度提高相比情况(2)的配置不会提高太多，更不可能接近最大并行度 4，这主要因为程序的各个指令之间具有数据依赖性，其执行必定要满足一定的先后顺序，不可能完全的并行化．

5 结 语

针对基于传输触发体系结构的可定制 Tcore处理器由于数据传输细节在体系结构一级可见导致的编译器效率低下的问题，构造了基于中间语言格式的可重定目标编译器架构．在此架构之下通过表调度与关键路径混合的调度策略解决了传统 TTA架构处理器编译器随机调度所带来的延迟调度问题，并以操作为基本调度单位避免了资源死锁．通过标准 DSP测试用例进行测试，与已有的基于 TTA架构处理器的编译器相比，指令级并行度提高近 40%，代码质量令人满意．

［1］Keutzer K，Malik S，Newton A R. From ASIC to ASIP：The next design discontinuity [C] //Proceedings of IEEE International Conference on Computer Design.Freiburg，Germany，2002：84-90.

［2］Gonzalez R E. Xtensa：A configurable and extensible processor [J]. IEEE Micro，2000，20(2)：60-70.

［3］Corporaal H.From VLIW to TTA[M]. Chichester，UK：John Wiley and Sons，1997.

［4］Corporaal H，Arnorld M. Using transport triggered architectures for embedded processor design [J].Integrated Computer-Aided Engineering，1998，5(1)：19-38.

［5］Wei Jizeng，Guo Wei，Sun Jizhou. Design and imple mentation of co-design toolset for Tcore processor [C]//2008IEEE Asia Pacific Conference on Circuits and Systems.Macao，China，2008：1664-1667.

［6］Holloway G，Smith M D. An Introduction to Machine SUIF and Libraries for Analysis and Optimization[EB/OL]. http：//www. eecs. harvard. edu/hube/software/nci/machine. html，2002.

［7］胡 维. 面向 TTA处理器结构的指令调度优化 [D].上海：上海交通大学电子信息与电气工程学院，2008.

Hu Wei. Optimal Instruction Scheduling Based on TTA Processor [D]. Shanghai：School of Electronic Information and Electrical Engineering，Shanghai Jiaotong University，2008(in Chinese).

［8］Winkel S. Optimal versus heuristic global code scheduling [C] //40thAnnual IEEE/ACM International Symposium on Microarchitecture.Washington，USA，2007：43-55.

［9］Ahmed Jerraya，Wayne Wolf.Multiprocessor Systemson-Chips[M]. Netherland：Elsevier，2007.

［10］Mahajan A，Ali M S. Superblock scheduling using genetic programming for embedded systems [C]//7thIEEE International Conference on Cognitive Informatics.California，USA，2008：261-266.

［11］Muchnick Steven S. 高级编译器设计与实现[M]. 赵克佳，沈志宇，译. 北京：机械工业出版社，2005.

Muchnick Steven S.Advanced Compiler Design and Implementation[M]. Zhao Kejia，Shen Zhiyu，Trans．Beijing：China Machine Press，2005(in Chinese).

［12］Hoogerbrugge J. Code Generation for Embedded System[D]. Netherland：Delft University of Technology，1996.

［13］Texas Instruments TMS320DM64x Benchmark [EB/OL]. http：//focus.ti.com/dsp/docs/dspplatformscontentaut. tsp，2005.