一个适合于VLIW体系结构的通路选择算法.doc

一个适合于VLIW体系结构的通路选择算法摘要：所以，在本文中，提出了一个基于这种VLIW体系结构的CPU的通路注选择算法，用它来 . 该算法实施的基础是：一串使用了一定的调度算法而生成的没有数据依赖的操作。 .关键词：结构,算法,数据类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！VLIW体系结构相关的通路选择算法李淼 王雷 刘志成 周伯生摘要：针对特定处理器的程序设计需要解决和底层体系结构相关的复杂的资源限制问题1。本文所研究的VLIW目标机具有部分互连特性，该特性要求作为操作数的寄存器需要通过子通路和通路来选通。因此，在该硬件平台上进行指令调度时，除了要考虑一般VLIW处理器指令调度中遇到的数据依赖问题外，还需要解决硬件结构带来的限制问题。本文针对部分互连特性，提出了一个通路选择算法，这个算法应用于传统的指令调度技术基础之上，并配合这些技术一起完成整个调度过程。Abstract: Programming specialized processors requires solving complex resource constrains related to the underlying architecture.1 The target machine mentioned in this paper has the characteristic of partial connection, which requires registers as operands must be connected through subpath and path. Therefore, when performing the instruction scheduling on the hardware platform, we need consider not only the data dependence problems of general VLIW processor, but also the restrictions brought by hardware. In allusion to the partial connection problem, this paper proposes an algorithm to select subpaths and paths. The algorithm is based upon the traditional instruction scheduling techniques, and can perform the scheduling process along with them. 一、 引言超长指令字（VLIW）体系结构是挖掘程序中指令级并行度（ILP）的一个很好选择2。这种体系结构的基本特性是：一个中央控制器在每个周期发射一个长指令字；每个长指令同时启动许多独立的操作；每个操作需要一个可静态预知的执行周期数；每个操作都能够流水执行。3VLIW体系结构指令的并行执行度是由编译器来发现的，而处理器的控制逻辑就相对简单，因为它不需要对操作进行动态调度和重排序1。在很多作为商业产品和实验室研究成果的处理器设计中，除了拥有VLIW体系结构的上述特点外，还各具特色。比如，philip设计的TriMedia-VLIW处理器1，Multiflow Computer Inc.制造的一款名为TRACE的VLIW处理器3，INTEL的IA64微处理器4等。本文所研究的微处理器，是对国内某公司的一款VLIW处理器的改进，和其它处理器相比，它的独特之处在于：对程序员暴露了结果寄存器和部分互连特性。VLIW处理器的并行处理能力是由编译器来发现的，编译器根据程序指令级的可并行性进行优化调度，按照一定处理要求生成多个可以同时执行的操作，并将它们装入一个指令字中。前人已经研究出了很多指令调度的方法，包括：list调度、basic-block调度、branch调度、cross-block调度、software pilelining、tarce调度、percolation调度等5，这些方法对于VLIW处理器的指令调度具有一定的通用性，在本文研究的体系结构中也借鉴了list5调度的成果。但是，对于该体系结构中所特有的部分部分互连特性，则没有相关的研究。所以，在本文中，提出了一个基于这种VLIW体系结构的CPU的通路注选择算法，用它来解决我们在指令调度中遇到的问题。该算法实施的基础是：一串使用了一定的调度算法而生成的没有数据依赖的操作。该算法的任务是：对上述操作串进行子通路和通路的选择，同时尽可能保证操作串中的操作都能够被并行执行。该算法的作用是：作为指令调度的一部分，完成对操作串的子通路和通路分配，如果分配不成功给调度函数返回失败信息。注：此处所说的通路选择算法是对该算法的一个命名，它包括对通路和子通路的选择，和后面所说的通路算子中的通路不等价。二、 目标机体系结构说明本文所研究的通路选择算法是基于VLIW体系结构的理想机器模型进行的，该机器模型是以国内某公司生产的一款CPU为原型改造而来的。理想机器模型的指令系统使用了基于算子的设计方法，在该体系结构中，算子是硬件暴露给软件的最低层，分别对应着各类硬件单元，是相应硬件单元的控制编码表示。本文中使用的通路算子就是算子的一种，作为简化，在后面的描述中，我们将通路算子简称为通路。本文针对的理想机器模型的特性是部分互连，即每个功能部件和每个寄存器不是全部直接互连的，大部分寄存器在使用时都需要事先由子通路来选通。每个功能部都包含和其参数个数相等的数据来源表，每个表记载了作为此功能部件的某个参数可以来源于哪些子通路或寄存器。如果作为某个操作的参数的寄存器出现在该参数的数据来源表中的话，就可以直接使用此寄存器；否则，需要通过子通路选通此寄存器后才能使用。在任何时间段内每个参数只能来自于表中的一个数据来源，如果选择了子通路作为数据来源，那么要将子通路和寄存器相连的信息保存在通路算子中。三、 引入通路选择算法的原因为了说明引入通路选择算法的必要性，我们先给出一个简单的例子。假设根据输入的操作串构造的寄存器（r1r3）、子通路（s1s3）和通路（t1）在初始状态的关系图如下所示（其中，寄存器和子通路之间的边表示寄存器能够被子通路选通的关系；子通路和通路之间的边表示通路包含子通路的关系）：图1一个简单的实例如果不使用一定的分配策略，而是简单的按照编号的顺序对寄存器、子通路和通路进行处理我们称之为笨办法，就会出现以下情况：对寄存器的处理顺序是r1、r2、r3，对子通路的处理顺序是p1、p2、p3。按照这样的顺序，为寄存器r1分配的子通路就是p2，为r2分配的子通路就是p1，对于r3来说已经没有子通路可以分配了，因为唯一可以选通它的子通路p1已经被分配给r2了。这就意味着输入的操作串中的操作不能并行执行。然而，实际上，存在一个可以满足这三个寄存器要求的分配，即：，。所以，为了提高指令的并行执行度，就需要设计一个比较合理的通路选择算法。四、 基本概念的描述定义1所用到集合的表示： RS表示寄存器集合；SS表示子通路集合；PS表示通路集合；Regs(s)表示子通路（s）可以选通的寄存器集合；PPt(p)表示通路（p）所包含的子通路集合。定义2操作（op）：op = ，其中name表示操作符，args表示参数集合，在实际运算过程中每个参数对应着一个寄存器。op中参数（arg）的数据来源表Tab(op,arg) = m | m是操作op中参数arg的数据来源。定义3寄存器（r）和操作(op)相关：如果rop.args，称寄存器r和操作op相关，记作：ReltROP(r,op) = 1, 如果r和op相关； 0, 否则。定义4寄存器（r）和子通路（s）相关：如果rRegs(s)，称寄存器r和子通路s相关，记作：ReltRS(r,s) = 1，如果r和s相关；0， 否则。定义5和寄存器（r）相关的数据来源集合TabR(r)：TabR(r)的构造过程为：选出满足ReltROP(r,op)=1的操作op，如果r是作为op的参数arg，就将Tab(op,arg)加入到TabR(r)中。定义6操作串：作为输入的操作串用OpL表示，OpL用到的寄存器集合R_Ops(OpL) = ；OpL中不需要子通路选通的寄存器集合R_NO_P(OpL) = R_Ops(OpL)。定义7阶段：将进行了一次寄存器、子通路和通路的选择后各集合所处的状态称为一个阶段，并令初始状态对应阶段0。同时定义R(q)为阶段q要处理的寄存器的集合；S(q)为阶段q可用的通路集合；P(q)为阶段q可用的通路集合。定义8阶段q中寄存器、子通路、通路三者关系的有向图（简称为三者关系图）表示G(q)：G(q) =，V=R(q)S(q)P(q)，EVV，其中V为顶点集合，E为边的集合，并且满足如下条件： 如果a,bR(q),那么，E，即寄存器顶点和寄存器顶点之间没有边；如果a,bS(q),那么，E，即子通路顶点和子通路顶点之间没有边；如果a,bP(q),那么，E，即通路顶点和通路顶点之间没有边；如果aR(q),bP(q),那么，E，即寄存器顶点和通路顶点之间没有边；如果aR(q), bS(q)，那么E，当且仅当aRegs(b)，并且bTabR(a)，但E，即寄存器顶点和子通路顶点之间的边是以寄存器顶点为起点，子通路顶点为终点，而反方向的边不存在；如果aS(q), bP(q)，那么E，当且仅当aPPt(b)，但E，即子通路顶点和通路顶点之间的边是以子通路顶点为起点，通路顶点为终点，而反方向的边不存在。 下图为三者关系图的一个实例。图2寄存器、子通路和通路三者关系的实例图其中，r1，r2，r3R(q)，s1，s2，s3，s4S(q)，p1，p2P(q)。该图表示的意义是：寄存器r1可以由子通路s1、s2来选通；寄存器r2可以由子通路s2、s3、s4来选通；寄存器r3可以由子通路s4来选通；通路p1包含子通路s1和s3；通路p2包含子通路s2 和s4。定义9图G(q)中顶点I的入（出）度和输入（出）集：顶点I的入度InD(I,q) =图G(q)中以顶点I为终点的边的数目；顶点I的顶点出度OutD(I,q) =图G(q)中以顶点I为起点的边的数目；顶点I的输入集InNodes(I,q) =图G(q)中以顶点I为终点的弧的起点构成的集合；顶点I的输出集OutNodes(I,q) =图G(q)中以I为起点的弧的终点构成的集合；分别用|InNotes(I)|和|OutNotes(I)|表示该这两个集合中元素的个数。五、 规则描述1 子通路的选通规则我们把二元组称作一个子通路的选通，记作L，其中r表示寄存器，s表示子通路。若两个子通路的选通L1，L2满足：L1.p = L2.p 并且L1.rL2.r，就称L1和L2冲突，表示为：L1L2 = 1（L1与L2冲突），0（L1与L2不冲突）。 在一个周期内的任何两个子通路的选通La和Lb，应该满足LaLb=0。1）若子通路s选通了寄存器r，就表示为ConSR (s,r) = 1，否则ConSR (s,r) = 0;在任何时间内满足： sS(q)，12) sS(q)，rR(q)，ConSR(s,r) =1 (sTabR(r) 3)其中，2）表示：在任何时间内每个子通路只允许选通一个寄存器；3）表示：如果子通路s选通了寄存器r，那么该s一定在和r相关的数据来源表中出现。2 通路的选择规则一个通路可以同时选通它所包含的所有子通路，若子通路s选择了通路p，记作：ConSP(s,p) = 1，否则ConSP(s,p) =0。通路的选择应该满足：sS(q)，pP(q)，(ConSP(s,p) = 1) sPPt(p)4)4)表示：子通路所应该放入实际能包含它的那个通路中。3 选择策略定义10选择策略：将在当前阶段所选定的寄存器（r）、子通路（s）和通路（p）构成的三元组称为一个选择策略，记作。定义11阶段q的选择格局D(q)：D(q)是从阶段0到阶段q所有选择策略的叠加。如果将叠加到D(q)时能够满足上面列出的条件1)4)，那么就可以形成一个新的选择格局D(q+1)，D(q+1) = D(q)。在初始化时，D(0)=。通路选择算法就是要在当前已有选择格局的基础上，选用适当的选择策略，形成新的选择格局，如此不断重复，直到形成最终的选择格局。六、 算法描述本算法是一种双向选择算法，在三者关系图中体现为从左到右和从右到左两个选择过程。从左到右的过程依次实现对寄存器、子通路和通路的选择；而从右到左的过程则是利用从左到右过程中选择的通路，本着充分利用该通路的原则，依次选择子通路和寄存器。将每个阶段对寄存器、子通路和通路的选择结果分别记录到reg，subpath和path中。1 公共函数说明（1） creat_graph（）根据定义8和输入的操作串（OpL）构造寄存器、子通路和通路三者在初始状态的关系图G(0)。（2） clip_graph（q）说明：根据阶段q的R(q)、S(q)和P(q)，修剪三者关系图G(q)。need_clip=TRUEwhile(need_clip)need_clip=FALSE;for(G(q)中的每个顶点v) if(v(R(q)S(q)UP(q) 删除v，以及所有和v关联的边；need_clip=TRUE; if( (v是子通路，且v的入度或出度为0) )或者（v是通路，且v的入度为 0）) 删除v，以及所有和v关联的边；if(vS(q)S(q)= S(q) v;if(vP(q)P(q)= P(q) v;need_clip=TRUE; （3） adjust_sets（q）说明：根据阶段q各个集合生成阶段q+1的各个集合。=;/生成当前阶段的选择策略D(q+1)=D(q);/生成当前阶段的选择格局q= q+1;R(q) = R(q-1)-reg;/删除已经处理过的寄存器S (q) = S(q-1)- subpath;/删除已经处理过的子通路P(q) =P(q-1);PPt(path) = PPt(path)-subpath;if(PPt(path) =)P(q) = P(q) path;G(q)= G(q-1);2 从左到右选择过程的函数描述（1） choose_reg_LTR（q）目标：从所有需要处理的寄存器集合中选出阶段q要处理的寄存器reg。方法：reg=满足|OutNodes(r,q)| 的r。该方法的意思是：优先选择和其相关的子通路个数最少的那个寄存器。（2） choose_subpath_ LTR（q）目标：在阶段q，已经选择出所要处理的寄存器reg后，为该reg选择子通路subpath。方法：if (OutD(reg,q) = 1)选择OutNotes(reg,q)中唯一存在的那个元素作为subpath；else if (OutD(reg,q) 1) subpath = 满足 InD (s,q) 的s。else subpath = 。该方法的意思是：如果寄存器reg只能由一个子通路来选通，那么就选择该子通路作为subpath；如果寄存器reg可由多个子通路来选通，那么subpath就选择和reg相关的子通路中可以选通的寄存器数量最少的那一个；否则，subpath为空。（3） choose_path_ LTR（q）目标：在阶段q，已经选择出reg、subpath之后，将它们放入一个通路path中。方法： path = 满足|InNodes(p,q)| 的p。该方法的意思是：选择那个包含了subpath，并且能够选通的子通路个数最多的那个通路。3 从右到左选择过程函数描述说明：该过程在已经通过从左到右的选择，生成了一个选择策略之后进行，它要用到中的通路信息作为path，然后依次选择子通路（subpath）和寄存器（reg）。（1） choose_subpath_RTL（q）目标：在阶段q已经选择出path的情况下，选择子通路subpath。方法：subpath = 满足 | InNodes (s,q) | 的s。（2） choose_reg_RTL（q）目标：在阶段q已经选择出path和subpath的情况下，选择寄存器reg。方法：reg = 满足 | OutNodes (r,q) |的r。4 通路选择算法(1) 从左到右选择函数choose_LTR（q）clip_graph(q);choose_reg_LTR(q);choose_ LTR (q);if (subpath = )print(“cant find subpath for reg!”);exit();choose_path_ LTR (q);adjust_sets(q);(2) 从右到左选择函数choose_RTL（q）while(InD(path,q)0 AND R(q)clip_graph(q);choose_subpath_ RTL (q);choose_reg_ RTL (q);adjust_sets(q);(3) 通路选择算法描述q = 0;R(0) = R_Inst(OpL) R_NO_P(OpL) ；S(0) = SS；P(0) = PS；create_graph();D(0) = ；while (R(q)choose_LTR();choose_RTL();七、 对算法的扩展1 背景上述算法假设在一个操作串中不会出现多个操作访问同一个寄存器的情况，但是在实际处理过程中却常常会出现这种情况。所以，有必要对上述算法进行扩充。2 对图形表示法的扩展定义12虚拟寄存器：为了满足上述情况，需要对操作串中用到的寄存器进行扩展，我们为OpL中每个作为op操作数的寄存器按照其出现顺序编号，并将编号后的寄存器称为虚拟寄存器，这样操作串中不会出现编号相同的虚拟寄存器。每个虚拟寄存器具有它所对应的真实寄存器的所有性质，同时增加了rname属性，来表示它所代表的真实寄存器。前面所列出的定义和公式，如果无特别说明，用到寄存器的地方，都可以替换为虚拟寄存器。图3对三者关系图的扩展：从与图2的比较中可以看出，原来表示寄存器的顶点在该图中表示虚拟寄存器，并增加了从虚拟寄存器顶点r1到r2的边，来表示这两个寄存器的同名关系。这种关系具有传递性，即如果存在边和边，那么暗含着存在边，这条边可以不用在图中表示出来。在这个图中，我们使用了虚线来表示虚拟寄存器之间的同名关系，是因为这种边只是一种概念上的边，在实际对图的处理过程中，可以当它不存在，即它的存在不会影响对InNodes、OutNodes、InD、OutD等函数的计算。3 对算法的扩充（1） 增加变量RSel，来表示选中的虚拟寄存器集合；（2） choose_reg_LTR_new (q)（对choose_reg_LTR(q)的扩充）步骤：1）用choose_reg_LTR（q）中使用的方法，选择reg；2）将reg加入到RSel集合中。（3） choose_subpath_RTL_new(q)（对choose_subpath_RTL(q)的扩充）步骤：1） 在已经使用choose_reg_LTR_new选择出所要处理的寄存器reg后，通过reg的rname属性找出所有与它同名的虚拟寄存器，构成一个集合REG。2） 选择subpath：如果： raREG，rbREG，rarb， OutNodes(ra) OutNodes(rb) subpath=满足的s同时，将所有满足rREG，且ReltRS(r,subpath) = 1的虚拟寄存器加入到集合RSel中。否则：使用原有的子通路选择算法。（4） choose_reg_RTL_new(q)（对choose_reg_RTL(q)的扩充）步骤：1）用choose_reg_RTL(q)中使用的方法，选择reg；2）将reg加入到RSel集合中。3）扩充RSel对所有虚拟寄存器r，如果满足：r.rname = reg.rname 并且subpathOutNodes(r) ，将r加入到RSel集合中。（5） adjust_sets_new(q)（对adjust_sets(q)的扩充）PPt(path) = PPt(path)-subpath;for(RSel中的每个元素r)reg = r;=;D(q+1)=D(q);q= q+1;R(q) = R(q-1)-reg;S(q) = S(q-1)- subpath;P(q) =P(q-1);if(PPt(path) =)P(q) = P(q) path;G(q)= G(q-1);（6） 对choose_LTR（）和choose_LTR（）的修正用choose_reg_LTR_new、choose_subpath_LTR_new以及adjust_sets_new代替choose_LTR中的choose_reg_LTR、choose_partapth_LTR和adjust_sets。用choose_reg_RTL_new、以及adjust_sets_new代替choose_RTL中的choose_reg_RTL、和adjust_sets。（7） 对通路选择算法的修正构造虚拟寄存器集合R(OpL)；q = 0;R(0) = R(OpL) R_NO_P(OpL) ；S(0) = SS；P(0) = PS；create_graph();D(0) = ；while (R(q)修正后的choose_LTR();修正后的choose_RTL();4八、 算法举例下面举一个例子来解释一下该算法是如何运行的。1 一个假设的目标机概述假设目标机所给的寄存器集合、子通路集合以及通路集合的状况如下：RS = R1，R2，R10；SS = s1，s2，s5；PS = p1，p2，p3；各个子通路的可选通寄存器集合如下：Regs(s1) = R1，R2，R5，R6；Regs(s2) = R2，R4，R8，R9；Regs(s3) = R2，R3，R5，R10；Regs(s4) = R2，R3，R6，R7；Regs(s5) = R7，R8，R9，R10；各个通路所包含的子通路集合如下：PPt(p1) = s1，s3，s4；PPt(p2) = s1，s2，s5；PPt(p3) = s2，s3，s4；2 输入的操作串及各操作对应的数据来源表输入的操作串为OpL = op1 R1 R2；op2 R2 R3；op3 R4 R5 （；只是作为两个操作之间的分割符，没有其它意义）各个操作的数据来源表如下：op1中参数1和参数2的数据来源表：s1，s3，s4，R8，R9；op2中参数1和参数2的数据来源表：s2，s3，s4，s9，R10；op3中参数1和参数2的数据来源表：s4，s5，R4，R5，R7；3 执行通路选择算法（1） 阶段0（经过裁剪后的状态）虚拟寄存器集合为：R (OpL)= r1，r2，r3，r4，r5，r6，其中r1.rname=R1，r2.rname=R2，r3.rname=R2，r4.rname=R3，r5.rname = R4，r6.rname = R5；图4 阶段0经过修剪后的三者关系图q = 0;R(0) = r1，r2，r3，r4; S(0) = s1，s2，s3，s4;P(0) = p1，p2，p3;D(0) = ;G(0)（已经过裁剪）如图?；subpath = s1；path = p1；Rsel = r1;reg = r1=；（2） 阶段1（从左到右选择）D(1) = ；图5 阶段1经过修剪后的三者关系图R(1)= r2，r3，r4；S(1) = s2，s3，s4；P(1)= p1，p2，p3；G(1)（已经过裁剪）如图?；path = p1；subpath = s3；Rsel = r2，r3；reg = r2；=；（3） 阶段2（从右到左选择）D(2) = ，；图6 阶段1、阶段2选择了同名寄存器r2、r3，它们共用一个子通路和通路，该图为阶段3经过修剪后的三者关系图R(2) = r3，r4；S(2) = s2，s3，s4；P(2) = p1，p2，p3；G(2)（已经过裁剪）如图?；path = p1；subpath = s3；Rsel = r2，r3；reg = r3；=；（4） 阶段3（从右到左选择）D(3) = ，；R(3) = r4；S(3) = s2，s4；P(3) = p1，p2，p3；G(3)（已经过裁剪）如图?；path = p1；subpath = s4；Rsel = r4;reg = r4；=；（5） 阶段4D(4) = ，；R(4) = ；S(4) = s4；P(4) = p2，p3；G(4)（已经过裁剪）如图?；算法结束九、 结束语VLIW处理器中指令级并行度需要由编译器来保证，而编译器在设计时还需要考虑和硬件相关的底层体系结构的限制。在我们所研究的目标机中就受到了“部分互连”特性的限制，针对该特性本文提出了一个双向的通路选择算法，该算法较好地解决了在指令调度过程中目标机的上述限制。这个算法虽然是为我们所研究的理想机器模型设计的，但是对于具有其它硬件限制的VLIW体系结构的处理器的指令调度和资源分配仍然具有参考意义。本文所使用的双向选择方法，不仅适合于硬件资源的分配，而且适用于求解多种资源寻求较优匹配的问题。参考文献：1 Erven Rohou,Christine Eisenbeis and Zbigniew Chamski. Flexible issue slot assignment for VLIW architectures. In 4th Int