虚拟寄存器与并行的指令处理部件
1.处理机体系结构的进展和存在的问题
近10年来,微处理机速度每年提高50%～100%,最新的处理机速度达到2亿～3亿次/s(例如MIPSR8000、POWER620和P6),最高的可达10亿次/s(DEC Alpha21164)。显而易见,这种进展是现在带动整个计算机事业发展的最活跃的因素。高速微处理机促进了计算机与通信技术的结合;加速了多媒体技术的实际应用;影响了超级计算实现的技术途径;并且使计算机产业结构发生了深刻变化。处理机性能如此迅速的提高,要归因于RISC体系结构的发明以及指令级并行性ILP的开发。图1可以表明10多年来处理机进展的道路。70年代中期对复杂指令系统计算机CISC分析后,研究者总结成20%-80%定律,即CISC指令系统中20%的基本指令是常用的,它占去了程序平均80%的部分。在这基础上,JohnCocke提出了精简指令系统计算机RISC的设计思想。然而,实践表明,单是靠减少指令数是无法满足商业产品的需要,而RISC思想的关键不在于减少指令数,而是在于减少执行每条指令所需要的平均周期数CPI。但是,如果只限制于每个周期只发射一条指令的传统的单发射结构,那末,CPI只能接近于1而不能小于1;只有设计出每个周期可发射多条指令的多发射结构,才可能使CPI小于1,或者使每个周期执行的平均指令数IPC大于1。RISC单发射与多发射结构必须是在流水线结构基础上执行指令的。在流水线结构中,相邻周期的指令之间就有数据相关性和转移相关性;而且在使用资源时,相邻周期的指令之间还可能发生资源冲突。因此,必须采用指令调度和编译优化来解除相关性和解决资源冲突问题。指令调度技术包括了软件和硬件的措施。在多发射结构中,不仅相邻周期的指令之间,而且同一周期的多条指令之间,都存在着相关性和资源冲突问题;因此,指令调度的重要性更为显著。此外,为了解决多发射结构中多条指令使用资源的问题,所以现代新型处理机内都设有多个执行部件。只有通过指令调度技术和合理设置多个执行部件,才可以提高指令执行的并行性(简称指令级并行性ILP),从而迅速提高处理机的性能并保持软件的兼容。这已经是现代处理机体系结构的明确的发展方向。为了使多个执行部件执行流水线更为有效,INTEL的Pentium除了吸收大量RISC设计思想以外,设置了多条物理的流水线,其中有两条是执行整数运算的流水线,一条是执行浮点运算的流水线。IBMPOWER601和603设置了更多的物理流水线。Pentium与POWER目前成为世界上应用最有前途的处理机机种。日本十分注意多线程处理机。其设计思想是把指令流分成多个线程,在每周期中,从每个线程中发射出一条指令;由于线程之间的指令是没有相关性的,所以在一个周期中发射出的多条指令理论上是没有相关性的。这样,多条指令发射以后,在多执行部件或多流水线结构中执行,可以提高ILP。
2.并行执行的指令处理部件与数据处理部件在图1所示的现代处理机的发展的六个阶段中,尤其在研究者致力于减少CPI(或提高IPC)的最近几个阶段中,不难看到研究者是把注意力集中于如何提高执行对数据处理的指令并行性。换言之,是指在指令发射以后在多执行部件或多流水线结构中指令执行的并行性。作者在本文中提出的指令处理部件新概念是基于如下的思想:为什么传统上人们只注意于改进指令发射以后改进数据处理的执行并行性,而不去注意未发射的那些“躺”在存储器中的一大堆指令并不被“触动”?应该在处理发射后的指令所执行的数据处理的同时,把“躺”在存储器中的未发射的指令提前取出进行处理。换言之,未来高度并行性的新处理机应该具有两大并行处理的部件:即指令处理部件和数据处理部件,这两大部件是并行的,见图2。在数据处理部件中,由指令发射单元在每个周期中发射出多条已解除相关性的指令,提供给多个执行部件去执行,以达到高度的指令执行的并行性。这是传统的多发射RISC结构。与此同时,预取指令单元已经提前从指令存储器中先取出一批指令,送到指令处理部件中去预先处理,进行指令调度,解除其相关性。然后,把处理好的指令流送到指令发射单元。这样每个周期可以发射出去并行执行的指令数,必然会显著增加,从而较大幅度地提高指令级并行性ILP.在图2的数据处理部件中,我们使用了寄存器堆与虚拟寄存器。这些虚拟寄存器的工作原理和其优点,以及指令处理和数据处理两大部件将在下面讨论。3虚拟寄存器的功能和原理现代RISC处理机的体系结构和编译优化都专注致力于开发程序执行中的指令级并行性。然而,程序本身是内含有一定并行性的,可是在当前的处理机和编译器中,几乎无例外地都是在代码生成阶段就已经分配指定了物理寄存器,这样就把有一定并行性的程序先做了串行化的排序,然后再从“串行化”的指令流中去开发指令级并行性,这种传统做法束缚了人们思想,从而在指令级并行性开发方面带来很大局限性。此外,在分配了物理寄存器以后,基本块的大小也受到了限制。据分析统计,基本块平均只含有5～8条指令。在这样大小的基本块中很难进行有效的指令调度。当然,以后人们又研究出很多办法去扩大基本块,或跨基本块的指令调度,这些都是在静态分配物理寄存器前提下的补救办法。针对上述传统做法的局限性,我们提出了虚拟寄存器VR的概念。虚拟寄存器的物理实现是和虚拟存储器VM相似的。虚拟存储器有它的管理机构,它可通过与外存的交换,扩大用户可用的存储地址空间。虚拟寄存器VR的管理机构是通过与Cache交换,扩大用户可用的寄存器堆空间。更重要的,从逻辑上看,VR相当于程序中的中间结果。采用虚拟寄存器概念的编译器,在代码生成时分配的是一堆虚拟寄存器,而只是在程序执行时,才对实际的物理寄存器实行动态的分配。这样,在代码生成时,由于分配的是数量很大的逻辑寄存器,程序内含的并行性并没有受到很多损失;而在程序执行时,动态分配物理寄存器带有很大灵活性,从而可显著提高指令级并行性,见图
3.虚拟寄存器的动态分配还有一个明显的优点是它简化了编译器的设计。由于过去传统上的物理寄存器堆大小是有限的(一般为32,INTEL结构中更少),在生成代码时要在寄存器分配的优化上花费很大功夫。而且由于物理寄存器的数量较少,相邻的基本块很可能是使用同样的一些寄存器来表示计算的中间结果,这样会增加基本块之间的额外的相关性。如采用多窗口寄存器堆设计,每一个窗口对应一个过程,则整个物理寄存器堆很大,而且有些局部寄存器并没有充分有效利用。本文中的虚拟寄存器的分配是动态的,每个函数所占用的寄存器数是可以动态地调整的,这实际上相当于寄存器窗口大小是可适应性地变化的,从而使用效率更高,这也是虚拟寄存器的另一优点。
4.乱序执行和寄存器换名中的虚拟寄存器见图4,当代新型处理机(POWER620和INTELP6)为了提高指令级并行性,都采用了乱序(Out-of-Or-der)的指令执行。在指令Cache中预取指令时是顺序的(In-Order),经过译码器后,多条指令的操作(或分解出来的微操作)都放入重新排序缓冲(ReorderBuffer)中去,重新排序缓冲依照其相关性以及传统物理寄存器堆所提供的可用操作数的情况乱序地分发指令到多执行部件或多流水线部件中去执行,通常是把源操作数先准备就绪的指令或操作先执行,其中间结果暂时存放在传统的物理寄存器中。退休(retire)部件是一种顺序部件,它把乱序执行的中间结果,按照其原来在重新排序缓冲中记录下的特征,以及表征保存某指令操作变量于某寄存器的保存时间的“生命周期”(lifetime)值,再恢复成原来程序应该顺序执行的结果的次序,并存入(store)数据存储器。图4中采用了虚拟寄存器以后,不仅方便了中间结果的暂时寄存;而且就象虚拟存储器中的逻辑地址一样,通过“映象”机制转换成物理地址,在映象表中还可以放入虚拟寄存器的特征、生命计数器值,以及其他如保护和排序的标志,从而使退休部件可以更为有效地恢复原来顺序执行的结果。虚拟寄存器的逻辑地址映象成物理寄存器,还可使用于寄存器换名(RegistenRenaming)技术中,图5。寄存器换名技术用于消除寄存器的假相关性,例如,下一段程序中,ra可能具有假相关性,如把ra换名为rm与rn就可消除:ra:=8〔rp〕rb:=ra+156ra:=45+rk另外,寄存器换名技术最近也用于更重要的场合,即追求软件的兼容。例如,Cyrix公司最近宣称,其M1产品可做到与INTELPentium兼容,其中主要采用了寄存器换名技术,即在M1中使用了面向寄存器(32个通用寄存器)的RISC结构,而把通用寄存器用映象机制换名为INTEL体系结构中那8个寄存器,从而达到采用RISC结构优点,却与CISC的INTEL处理机兼容。图5中的结构既可用于乱序执行后退休部件的重新排序,又可用于寄存器换名技术。图中的虚拟寄存器换名表实际上是全相联的内容寻址快速存储器(CAM),它根据虚拟寄存器逻辑地址和在重新排序缓冲中记录下来的特征,按全相联方式找出换名表中的一项,该项中包含有虚拟寄存器的特征,表示生命周期的虚拟寄存器生命计数值,以及其他如保护和排序功能所需的标志,映射出所命中的物理寄存器。
5.指令处理部件指令处理部件及其与数据处理部件的配合如图6所示。从指令Cache中取出的指令流放在预取指令的队列中,在一个流水级中,要有多个译码部件对多条指令同时译码,以提高指令处理的并行性。现代处理机中都十分重视对于转移指令的处理,所以一般都设有转移处理部件,转移处理部件的功能可以是对转移的条件码进行处理,如RS6000;也可以是转移预测部件,如Pentium。译码出来的信息和转移处理的信息都送到相关性检测器与重新排序缓冲中去。那边可对相关性检测并且记录下指令的特征。重新排序缓冲将调度与操作乱序的指令执行,它与虚拟寄存器管理单元交换信息,把已解除相关性而且其源操作数已准备就绪的那些指令先送到指令发射单元,以便每个周期可确保同时发射多条指令,供多执行部件或多流水线部件去并行地执行。虚拟寄存器及其映象表的功能已在前节叙述。重新排序缓冲、虚拟寄存器映射表和多执行部件都连接到退休部件,退休部件综合这些信息,再把乱序执行的结果按原来的应该的次序返回给寄存器堆或者数据Cache中去。在指令处理部件中还有一个存储器指令多义性解析单元,它是专门用来处理指令流中的存储访问类型指令的,即解除存储访问指令中的多义性(Disambiguition)。这一方面我们将有专门的论文进行讨论。
6结论具有指令处理部件的处理机结构将显著地提高处理机内部的并行性。虚拟寄存器的新概念的引入将大大提高数据处理部件内执行指令的并行性。而在数据处理部件工作的同时,指令处理部件已预先把指令流从指令Cache中取出来处理了(而传统的处理机结构中让指令躺在指令存储中,实际上是一种“信息浪费”)。经过指令处理以后,可以解除大量的转移相关性和数据相关性,存储器指令多义性解析器又消除了大量的存储访问类型指令中的多义性。总之,从指令处理部件输送给指令发射单元的指令,其可并行执行度已经大大提高,因此,指令级并行性ILP已经充分开发出来了,而对程序员完全是透明的,从而保持软件的兼容性,相信这种新型处理机体系结构必将有很好的发展前途。
虚拟寄存器以及指令处理部件是我们提出的新概念,我们将陆续发表此领域的论文和仿真模型与实验数据.
