计算机系统结构-陈智勇-第4章-流水线计算机设计技术_第1页
计算机系统结构-陈智勇-第4章-流水线计算机设计技术_第2页
计算机系统结构-陈智勇-第4章-流水线计算机设计技术_第3页
计算机系统结构-陈智勇-第4章-流水线计算机设计技术_第4页
计算机系统结构-陈智勇-第4章-流水线计算机设计技术_第5页
已阅读5页,还剩258页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

4.8相关处理和控制机构4.9先进的流水技术—动态调度4.10超标量处理机和VLIW体系结构4.11超流水处理机4.12超标量超流水处理机习题44.1重叠解释方式和相关处理4.1.1重叠解释方式的提出解释一条机器指令的那些微操作可分解成取指令、分析指令与执行指令,从时间上看如图4.1所示。

取指令指的是按指令计数器的内容访问主存,取出该指令送到指令寄存器。指令的分析指的是对指令的操作码进行译码,按寻址方式和地址字段形成操作数的有效地址,并用此有效地址去取操作数(可能访主存,也可能访寄存器),还要为准备取下一条指令提前形成下一条指令的地址等。指令的执行则指的是对操作数进行运算、处理,或存储运算结果(可能要访主存)。

指令的解释方式可以有顺序解释方式和重叠解释方式。指令的顺序解释方式是指各条机器指令之间顺序串行地执行,执行完一条指令后才取出下一条指令来执行,而且每条机器指令内部的各条微指令也是顺序串行地执行,如图4.2所示。顺序执行的优点是控制简单。由于下一条指令的地址是在指令解释过程的末尾形成的,因此无论是由指令计数器加1,还是由转移指令把转移地址送到指令地址计数器,形成下一条指令的地址,由本条指令转入下一条指令的时间关系都是一样的。但由于是顺序执行的,上一步操作未完成,下一步操作就不能开始。因此,带来的主要缺点是速度慢,机器各部件的利用率很低。例如,在取指令和取操作数期间,主存储器是忙碌的,但是运算器处于空闲状态。在对操作数执行运算期间,运算器是忙碌的,而主存却是空闲的。

指令的另一种解释方式是重叠解释方式,在解释第k条指令的操作完成之前,就可开始解释第k+1条指令。显然,重叠解释并不能加快一条指令的实现,但能加快相邻两条以至一段程序的解释。图4.3给出了指令的重叠解释的方式。至于中央处理机、存储器和输入输出设备之间的重叠操作,也是一种重叠方式,是实现I/O指令与其它指令的重叠。在一般的机器上,操作数和指令是混合存贮于同一主存内的,而且主存同时只能访问一个存贮单元。从图4.3可以看出,重叠解释方式需要“取指k+1”与“分析k”在时间上重叠,显然,对于一般机器,取指需要访问主存,分析中取操作数也可能访问主存。如果不在硬件上花费一定的代价解决好访主存的冲突,就无法实现“取指k+1”与“分析k”的重叠。

为实现“取指k+1”与“分析k”的重叠对计算机组成有如下要求:

(1)让操作数和指令分别存放于两个独立编址且可同时访问的存储器中;这还有利于实现指令的保护,但这增加了主存总线控制的复杂性及软件设计的麻烦。

(2)仍然维持指令和操作数混存,但采用多体交叉主存结构;只要第k条指令的操作数与第k+1条指令不在同一个存储体内,仍可在一个主存周期(或稍许多一些时间)内取得这两者,从而实现“分析k”与“取指k+1”重叠。当然,若这两者正好共存于一个体时就无法重叠。(3)增设指令缓冲寄存器。设置指令缓冲寄存器就可以乘主存有空时,预先把下一条或下几条指令取出来存放在指令缓冲寄存器中。最多可预取多少条指令取决于指令缓冲寄存器的容量。这样,“分析k”就能与“取指k+1”重叠,因为只是前者需访主存取操作数,而后者是从指缓取第k+1条指令。只要每次取指都可从指缓中得到,则“取指k+1”的时间很短,完全可以把这个微操作合并到“分析k+1”内,从而由原来的取指、分析、执行重叠演变成只需“执行k”与“分析k+1”的一次重叠,如图4.4所示。4.1.2一次重叠工作方式从图4.4可以看出,为了实现“执行k”与“分析k+1”重叠还必须在硬件上保证有独立的指令分析部件和指令执行部件。在实际应用中,“分析”和“执行”所需的时间常常不完全一样,在设计时,应解决好控制上的同步,保证任何时候都只是“执行k”与“分析k+1”一次重叠。即任何时候,指令分析部件和指令执行部件都只有相邻两条指令的解释。“一次重叠”解释方式的优点为省硬件,机器内只需要一套指令分析部件和指令执行部件,也有助于简化控制。但缺点是,在实际情况中,“分析”和“执行”所需的时间常常不完全一样,设计时应适当安排好每条指令的微操作,使“分析”和“执行”所需的时间尽可能等长,才能使重叠方式有较高的效率。如果采用多次重叠,不仅要设置多套指令分析和指令执行部件,控制还相当复杂。所以,重叠方式的机器大多数都采用一次重叠,若仍达不到速度要求时,宁可采用后面要介绍的流水方式。

在实际设计中,为了实现“分析k+1”和“执行k”的一次重叠,还需要在硬件控制上解决许多问题。先看转移指令的处理问题。例如:第k条指令是按其执行结果进行转移的条件转移指令,当条件转移不成功时,重叠操作是有效的;但当遇到条件转移,并且成功转移到第m条指令时,这时与“执行k”重叠的“分析k+1”的操作是无效的,重叠方式实际上变成了顺序方式,因为在“执行k”的末尾才形成下一条要执行指令的地址,显然,下一条指令应该执行第m条指令,

即当第m条指令在指缓内时,应该执行的是“分析m”,若不在,应该执行的是“取指m”,并且应该是在“执行k”结果出来之后。而“分析k+1”(包含了取指k+1)取的是第k+1条指令的内容,这就会出错。图4.5给出了执行条件转移时指令重叠的情况。

为了避免出错,第k条和第k+1条指令就不能同时解释,因此采用重叠方式的机器中应尽量减少程序中条件转移指令的使用,否则将会使重叠效率显著下降。如果出现条件转移指令,可以采用其它技术,如延迟转移技术,使重叠效率不下降。

控制上还要解决好邻近指令之间有可能出现的某种关联。当一段程序的邻近指令之间出现某种关联后,为了避免出错而使它们不能同时被解释的现象称之为“相关”。相关可以是指令相关,也可以是操作数相关。指令相关是指第k条指令执行的结果会影响第k+1条指令内容而产生的关联,造成第k条指令和第k+1条指令不能同时解释。例如,在采用VonNeumann型机器上,可通过执行第k条指令的办法来形成第k+1条指令:

k:存,通用寄存器号,k+1功能:(通用寄存器)k+1k+1:……

由于在“执行k”的末尾才形成第k+1条指令,按照一次重叠的时间关系,“分析k+1”所分析的是早已取进指缓的第k+1条指令的旧内容,这就会出错,这种情况就是我们所说的指令相关。特别是当指令缓冲器可缓冲存放n条指令情况下,执行到第k条指令时,与已预取进指缓的第k+1到第k+n条指令都有可能发生指令相关。指令缓冲寄存器的容量愈大,或者说指令预处理能力愈强的机器发生指令相关的概率就愈高。

操作数相关是指在第k条指令和第k+1条指令的数据地址之间发生关联,而造成第k条指令和第k+1条指令不能同时解释的现象。例如:第k+1条指令的源操作数地址i正好是第k条指令存放运算结果的地址。在顺序解释时,由于先由第k条指令把运算结果存入主存i单元,而后再由第k+1条指令从i单元取出,当然不会出错。但在“分析k+1”与“执行k”重叠解释时,“分析k+1”从i单元取出的源操作数内容成了“执行k”存入运算结果前的原始内容,而不是第k条指令的运算结果,这必然会出错。操作数相关不只是会发生在主存空间,还会发生在通用寄存器空间。4.1.3相关处理

1.指令相关的处理对于有指令缓冲器的机器,由于指令是提前由主存取进指缓的,为了判定是否发生了指令相关,需要进行相当复杂的对多条指令地址与多条指令的运算结果地址比较,看是否有相同的。如果发现有指令相关,还要让已预取进指缓中的相关指令作废,并重取、更换指缓中的内容,这样做不仅操作控制复杂,而且增加了辅助操作时间,特别是要花一个主存周期去访存重新取指,必然会带来时间损失。

因为可能被修改的指令是以“执行”指令的操作数形式出现,并存于第k+1条指令的物理地址,而下一条指令又是从该地址取出来的,而指令代码本身就是数据,因此指令相关实际上就转化成了操作数相关,统一用处理操作数相关的方法来解决,从而在程序中就不会发生指令相关了。

实际上操作数可能存放于主存,也可能存放于通用寄存器中,因此就有主存空间数相关和通用寄存器组数相关。一般的机器中,通用寄存器还可以存放变址值,而变址值是在“分析”的前半时间为形成操作数地址时所要用到的,它必须在分析时间段的一开始就要访问变址寄存器。这样,若在第k条指令“执行”的末尾形成的结果正好是第k+1条指令“分析”时所要用的变址值时,还会发生通用寄存器组的变址值相关。2.主存空间数相关的处理主存空间数相关是指相邻两条指令之间出现要求对主存同一单元先写入而后再读出的关联。如果让“执行k”与“分析k+1”在时间上重叠,就会使“分析k+1”读出的操作数不是程序要求的第k条指令执行完后应当写入的结果,而造成错误。如图4.6所示。主存空间数相关的处理方法通常采用推后第k+1条指令的读操作数。

具体方法是由存控通过给读数、写数申请安排不同的访存优先级来解决。通常很多机器都将访存优先级依次定为通道申请、写数、读数、取指令。这样,当第k条和k+1条指令出现主存空间数相关时,“执行k”与“分析k+1”同时对主存同一个单元发出访存申请,但因“写数”级别高于“读数”,存控先处理“执行k”的写数,“分析k+1”的读数申请必然只能推迟到下一个主存周期才有可能被处理,从而就自动实现了推后“分析k+1”的读,不用处理机另外采取措施。如图4.7所示。3.通用寄存器组相关的处理通用寄存器既可存放操作数、运算结果,也可以存放变址值,但是在指令解释过程中,使用通用寄存器作为不同用途所需的有关微操作时间要求是不相同的。存放于通用寄存器中的基址或变址值一般总是在“分析”周期的前半段就要取出来用;而操作数则是在“分析”周期的后半段取出,到“执行”周期的前半段才用得上;运算结果却是在“执行”周期的末尾才形成,并送入通用寄存器中。

图4.8给出了它们之间的时间关系。正是因为它们的时间要求不同,所以通用寄存器数相关和通用寄存器变址值相关的情况及其处理方法不相同。设机器的基本指令格式如图4.9所示。L1、L3分别指示存放第一操作数和运算结果的通用寄存器号,B2为形成第二操作数地址的基址值所在通用寄存器号,d2为相对位移量。

设机器的基本指令格式如图4.9所示。L1、L3分别指示存放第一操作数和运算结果的通用寄存器号,B2为形成第二操作数地址的基址值所在通用寄存器号,d2为相对位移量。(1)通用寄存器组数相关的情况和处理办法假设某台机器正常情况下,“分析”和“执行”的周期与主存周期一样都是4拍。有些指令需要从通用寄存器组中取两个操作数(L1)和(L2),若通用寄存器组做在一个片子上,每次只能读出一个数,则在“分析k+1”期间,操作数(L1)和(L2)就需要在不同拍时取得,分别送入运算器的B和C寄存器,以便在“执行k+1”时供运算用。这样“执行k”与“分析k+1”间通用寄存器组的时间关系如图4.10所示。当程序执行过程中出现L1(k+1)=L3(k)时就发生了L1相关;而当L2(k+1)=L3(k)时就发生了L2相关。

当程序执行过程中出现要解决通用寄存器组数相关的情况,主要有以下两种方法:①与前述处理主存空间数相关的一样,推后“分析k+1”的读(寄存器的内容)。具体有两种不同的方法:可以把“分析k+1”推后到“执行k”结束时开始,也可以只要推后到“执行k”把结果送入L3,然后再由“分析k+1”在取(L1)或(L2)时能取到就可以了。采用前一种推后的办法,只要发生数相关就使一次重叠变成了完全的顺序串行,速度明显下降;后一种推后的方法则是发生数相关时,相邻两条指令的解释仍有部分重叠,可以减少速度损失,但控制要稍微复杂一些。

这两种方法都是靠推后读,牺牲速度来避免相关时出错。那么能否在不降低速度的情况下仍然能保证数相关时的正确处理呢?②在运算器的输出到B、C输入之间增设一条“相关专用通路”,如图4.11所示,则在发生L1或L2相关时,让相关专用通路接通,就可以在“执行k”时将运算结果送入通用寄存器以在完成其应有的功能的同时,直接将运算结果回送到B或C寄存器,从而大大缩短了其间的传送时间,并能保证当“执行k+1”需要用此操作数时,它已在B或C寄存器中准备好了。

也就是说,尽管原先将通用寄存器的旧内容经数据总线分别在“分析k+1”的第3拍或第4拍末送入了操作数寄存器B或C中,但之后经相关专用通路在“执行k+1”真正用它之前,操作数寄存器B或C重新获得第k条指令送来的新结果。这样,既保证了相关时不用推后“分析k+1”,重叠效率不下降,又可以保证指令重叠解释时数据不出错。

推后“分析k+1”和设置“相关专用通路”是解决重叠方式相关处理的两种基本方法。两者的主要区别为前者是以降低速度为代价,使设备基本上不增加,后者是以增加设备为代价,使重叠效率不下降。“相关专用通路”法照样可用于解决前述的主存空间数相关,但由于主存空间数相关的出现概率比通用寄存器组数相关的出现概率低得多,所以,主存数相关不采用“相关专用通路”法,而只采用推后读来解决。(2)通用寄存器组基址值或变址值相关的情况及其处理办法在采用基址寻址时,操作数的有效地址为:(Xd)+(B2)·(B2≠0000)+d2,由分析器内的地址加法器形成。由于通常情况下,“分析”周期等于主存周期,所以,从时间关系上要求在“分析”周期的前半段,就能由通用寄存器输出总线取得(B2),送入地址加法器。

由于运算结果是在“分析”周期的末尾才送入通用寄存器组的,它当然不能立即出现在通用寄存器输出总线上。也就是说,在“执行k”得到的、送入通用寄存器的运算结果来不及作为“分析k+2”的基址值用,更不用说作为“执行k+1”的基址值用。因此,虽然是一次重叠,但基址值相关(B相关)就不止会出现一次相关,还会出现二次相关。即当出现B(k+1)=L3(k)

时,称为发生了B一次相关;而当出现B(k+2)=L3(k)时,称为发生了B二次相关。这里所谓的一次和二次指的是相关指令相隔的指令条数。

对于基址值相关,其解决办法同数相关的一样,也可有推后分析(读基址寄存器的内容)和设置相关专用通路两种。变址值相关与基址值相关类似,处理方法也一样。①推后分析的方法。由图4.12可看出,对于B二次相关,只需推后“分析k+2”的始点,使“执行k”送入通用寄存器的运算结果,在“分析k+2”开始时已出现于通用寄存器的输出总线上,如图4.13(a)所示。而对B一次相关,则除此之外,还需要推后一个“执行”周期,如图4.13(b)所示。②设置相关专用通路的方法。由于B一次、二次相关的概率并不很低,增设B相关专用通路还是值得的,其办法如图4.14所示。这样,在B二次相关时,就可把“执行k”得到的运算结果,在送入通用寄存器组的同时,经“B相关专用通路”直接送到“访存操作数地址”形成机构,由于缩短了其间的传送延迟,使得不必推后“分析k+2”,就能保证使用正确的基址值。同理,在B一次相关时,只需使“分析k+1”推后到接着“执行k”进行就可以了。

综上所述,实现在时间上的重叠,(1)需要付出空间代价;如增设数据总线和控制总线、指令缓冲器、地址加法器、相关专用通路等,需将指令分析部件和指令执行部件分开、单独设置,需将主存采用多体交叉存取等等。(2)要处理好这二条指令之间可能存在的关联。如转移的处理以及指令相关、主存空间数相关、通用寄存器组的数相关和在址/变址值相关等的处理。相关处理的办法无非是“推后读”和设置相关专用通路两种,应当根据Huffman概念在成本和效率上加以权衡选用。(3)还应合理安排调配好机器每条指令的微操作,使“分析”和“执行”所需的时间尽可能匹配,以提高重叠的效率。4.2流水线的工作原理

如果CPU用一次重叠方式解释指令仍达不到所要求的速度性能时,可以考虑同时解释多条指令。其中最常用的是流水方式,它是通过并行硬件来改善性能的最普通的手段。在60年代,硬件的价格相对较高,流水线计算机都是巨型机。IBM的STRETCH和CDC的6600就是60年代早期大量应用流水线的两种机器,它们对后来巨型机的结构产生了深刻的影响。

到了80年代,技术的进步使硬件价格大幅度下降,使流水线技术能在各种类型的计算机上得到应用。例如,Intel8086微处理机虽然价格十分低廉,也能在芯片执行运算的同时应用流水线技术访问存储器。而发展到Pentium系列CPU产品的时候,更是一个高级的超标量处理器。可以说,计算机发展到现在,流水技术已经成为各类机器普遍采用的、用来改善性能的基本手段。

计算机的流水技术是如何工作的呢?流水技术的基本思想在冯·诺依曼的第一台存储程序计算机中已经提出。流水技术早已应用于社会生产与活动的各个方面,并不是计算机所特有的。其主要特点是在一个任务完成以前就可以开始一个新的任务。先看一次重叠的情况,“执行k”与“分析k+1”的一次重叠是把一条指令的解释过程分解成“分析”与“执行”两个子过程,分别在独立的分析部件和执行部件上进行。因此,不必等一条指令的“分析”、“执行”子过程都完成才送入下条指令,而是分析部件在完成一条指令的“分析”子过程时,就可开始下一条指令的“分析”子过程。

若“分析”与“执行”子过程都需要Δt的时间,如图4.15所示,就一条指令的解释来看,需要2Δt才能完成,但从机器的输出来看,每隔Δt就能完成一条指令的解释。也就意味着,一次重叠解释比起指令的串行解释,可使机器的最大吞吐率提高一倍。这里的最大吞吐率是指当流水线正常满负荷工作时,单位时间内机器所能处理的最多指令条数或机器能输出的最多结果数。若将指令的分析和执行部分进一步细分成一些子过程,并改进相应硬件的结构,使得子过程分别由独立的子部件实现,形成流水处理的方式,其最大吞吐率可进一步提高,如图4.16的流水处理过程和相应的时-空图。

如图4.16(a)所示,把“分析”子过程再细分成“取指令”、“指令译码”和“取操作数”3个子过程,并改进运算器的结构以加快其“执行”子过程,这4个子过程分别由独立的子部件实现,让经过各子部件的时间都相同,用Δt1表示,则指令解释的时间-空间关系如图4.16(b)所示。一条指令从进入流水线到结果流出需经历“取指令”、“指令译码”、“取操作数”和“执行”4个子过程,每个子过程需要Δt1的时间,一条指令的解释需要4Δt1的时间完成。

当第1条指令完成“取指令”子过程时,就可以开始第2条指令的“取指令”子过程;当第1条指令完成“指令译码”子过程而进入“取操作数”子过程时,可以开始第2条指令的“指令译码”子过程,同时,第2条指令的“取指令”子过程结束,可以开始第3条指令的“取指令”子过程;依此类推,当第1条指令进入“执行”子过程时,第2条指令可进入“取操作数”子过程,第3条指令可进入“指令译码”子过程,第4条指令可进入“取指令”子过程。显然,图4.16(b)中的流水线可同时解释4条指令。

如果完成一条指令的时间为T,则对于分解为“分析”和“执行”两个子过程的,其T=2Δt,而对于分解为“取指令”、“指令译码”、“取操作数”和“执行”4个子过程的,其T=4Δt1。这样,虽然完成一条指令所需时间仍是T,对于顺序解释方式,每隔T由处理机“流出”一个结果;但对图4.15的重叠方式是每隔T/2(即每隔Δt)就可由处理机“流出”一个结果,吞吐率提高了一倍;而对图4.16的流水方式是每隔T/4(即每隔Δt1)“流出”一个结果,即吞吐率比顺序方式提高了三倍。

流水处理带来的好处是显而易见的,以图4.16为例,若进入流水线的指令数为6,则其从第1条指令流入流水线,到最后一条指令的结果流出,使用的时间是9Δt1,即9T/4的时间;如果是顺序执行,则需要6T的时间,从一组指令序列的执行速度来看,采用流水解释方式的机器的速度要比顺序解释方式的机器快得多。“流水”在概念上与“重叠”没有什么差别,可以看成是“重叠”的进一步引伸。两者的差别只在于“一次重叠”只是把一条指令的解释分解为两个子过程,而“流水”则是分解成更多个子过程。前者同时解释两条指令,后者可同时解释多条指令。例如图4.16的流水处理过程可同时解释4条指令。如果能把一条指令的解释分解成时间相等的N个子过程,则每隔Δt=T/N就可以处理一条指令。如图4.17所示,这意味着,流水线的最大吞吐率是取决于子过程所经过的时间Δt,Δt越小,流水线的最大吞吐率就越高。

如果流入流水线的指令数为6,则从第1条指令流入,到第6条指令的结果流出,所需要的时间为(NΔt+5Δt)。如果流入流水线的指令数是X,则从第1个指令流入,到第X条指令的结果流出,所需要的时间为(NΔt+(X-1)Δt)。设流水线对一条指令的解释可以细分为n个子过程,每个子过程处理的时间均为Δt,若有m条指令进入该流水线,则从第1条指令流入,到第m条指令的结果流出所需要的时间定义为Tm,则有:

从第1条指令流入流水线开始,到最后一个结果流出的这一段时间内,每隔Δt流出一个结果。应该注意的是,只有当流水线正常满负荷流动时,才会每隔Δt流出一个结果。流水线从开始启动工作到流出第一个结果,需要经过一段流水线的建立时间,在这段时间里流水线并没流出任何结果。

在计算机实际的流水线中,各子部件经过的时间会有差异。为解决这些子部件处理速度的差异,一般在子部件之间需设置高速接口锁存器。所有锁存器都受同一时钟信号控制来实现各子部件信息流的同步推进。时钟信号周期不得低于速度最慢子部件的经过时间与锁存器的存取时间之和,还要考虑时钟信号到各锁存器可能存在时延差。所以,子过程的细分,会因锁存器数增多而增大指令或指令流过流水线的时间,这在一定程度上会抵消子过程细分而使流水线吞吐率得到提高的好处。4.3流水线的特点

在流水技术中,一般有如下特点:一条流水线通常由多个流水段组成;各个流水段分别承担不同的工作,也可以把这些流水段看作功能部件。如在图4.16(a)中,流水段由四部分组成,依次是“取指令”、“指令译码”、“取操作数”和“执行”4个功能段。在实际机器中,一条流水线的功能部件按完成的任务及采用的设计思想不同,其数目也各不相同。

例如,80486、Pentium的流水线设计为5段,PentiumIII的流水线设计为10段,AMDAthlon的流水线有11段,PentiumIV的流水线达到了20段,MIPS的R4000有8个流水段,DEC的Alpha21064处理机共有三条指令流水线,整数操作流水线和访问存储器流水线分为7个流水段,而浮点操作流水线分为10个流水段。每个流水段有专门的功能部件对指令进行某种加工;例如,80486的流水线分为5段,分别为“取指令”、“译码段1”、“译码段2”、“执行”和“写回”。在译码段1完成所有的操作码和寻址方式的译码工作。而在译码段2则将每个操作码扩展成对ALU的控制信号。在执行段则要完成ALU运算、Cache访问和寄存器修改。

各流水段所需的时间是一样的;在设计流水线的控制线路及计算流水线的性能时会带来方便,简化了设计。但在实际机器中,各流水段所需的时间很难保证一致。流水线工作阶段可分为建立、满载和排空三个阶段。从第一个任务进入流水线到流水线所有的部件都处于工作状态的这一个时期,称为流水线的建立阶段。当所有部件都处于工作状态时,称为流水线的满载阶段。从最后一条指令流入流水线到结果流出,称为流水线的排空阶段。在理想情况下,当流水线充满后,每隔Δt时间将会有一个结果流出流水线。4.4流水线的分类

从不同的角度,可对流水线进行不同的分类。

4.4.1根据向下扩展和向上扩展的思想分类依据向下扩展和向上扩展的思想,可分类出在计算机系统不同等级上使用的流水线。向下扩展是指把子过程进一步向下细分,让每个子过程经过的时间都同等程度地减少,吞吐率就会进一步提高。如把图4.15中的“分析”子过程细分为“取指令”、“指令译码”和“取操作数”3个子过程。

在机器中“执行”子过程会因指令不同,执行时间不同,而使细分的情形不同。如浮点加法可进一步细分成为“求阶差”、“对阶”、“尾数相加”和“规格化”4个子过程,如图4.18所示。

子过程的进一步细分是以增加设备为代价的。例如,“求阶差”和“尾数相加”都要用到加法器,为此需要分别设置阶码加法器和尾数加法器。“对阶”和“规格化”都要用到移位也就需要分别设置两套移位器。设备的增加不仅会使成本增加,也使控制变得复杂。但它比起完全靠重复设置多套分析部件和执行部件来提高指令并行性,其设备量的增加毕竟要少得多。子过程细分并不是无止境的,因为级间缓冲器数的增多,使成本提高,辅助延时增大,控制复杂,电路设计和实现困难等,抵消了子过程细分带来的好处。PentiumIII的流水线设计为10段,AMDAthlon的流水线有11段,PentiumIV的流水线达到了20段,PentiumIV的Willamette版本在运行一些测试程序时,其性能比相同时钟频率PentiumIII及AMDAthlon要低10%~20%。但是子过程的细分可以在相同设计条件和生产工艺下提高芯片的时钟频率,PentiumIII处理器拥有10级的流水线设计,其频率很难超过1GHz;而PentiumIV处理器采用了20级的流水线,其频率已经突破3GHz。

流水的向上扩展可理解为在多个处理机之间进行流水。如图4.19所示。多个处理机串行地对数据集进行处理,某个处理机专门完成其中的一个任务。因为各个处理机都在同时工作,所以能对多个不同的数据集流水地处理,使计算机系统处理能力有较大的提高。

综上所述,按流水处理的级别不同,可以把流水线分为部件级、处理机级和系统级的流水。部件级流水是指构成部件内的各个子部件之间的流水,如运算器内浮点加法流水线及Cache和多体交叉主存的流水。处理机级流水是指构成处理机的各个部件的流水,如“取指”、“分析”、“执行”间的流水。系统级流水是指构成计算机系统的多个处理机之间的流水,也称为宏流水。4.4.2按流水线功能的多少分类按流水线具有功能的多少来划分,可以分为单功能流水线和多功能流水线。单功能流水线是指只能完成一种固定功能的流水线。Cray-1计算机中有12条单功能流水线,分别为:地址加、地址乘、标量加、标量移位、标量逻辑运算、标量加1计数、向量加、向量移位、向量逻辑运算、浮点加、浮点乘、浮点迭代求倒数;Pentium有一条5段的定点和一条8段的浮点流水线;PentiumⅢ有三条指令流水线,其中两条定点指令流水线,一条浮点指令流水线,其流水线的功能段为10个。

多功能流水线是指同一流水线的各个段之间可以有多种不同的联接方式以实现多种不同的运算或功能。例如美国Texas公司的ASC计算机运算器的流水线就是多功能的,它有8个可并行工作的独立功能段,能够实现:定点加减法、定点乘法、浮点加减法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。

如图4.20所示,TI-ASC机器要进行浮点加、减法时,其流水线功能段的联接如图4.20(b)所示;而要进行定点乘法运算时,其流水线功能段的联接如图4.20(c)所示。除此之外,它还可以根据运算的要求来实现多种不同的联接。4.4.3按流水线的工作方式分类按多功能流水线的各段能否允许同时用于多种不同功能联接流水,可把流水线分为静态流水线和动态流水线。静态流水线是指在同一时间内,多功能流水线中的各个功能段只能按一种功能的联接方式工作。就指令级流水而言,仅当流入的是一串相同运算的指令时,才能发挥出静态流水线的效能。若进入的是浮加、定乘、浮加、定乘……这样一串不同指令相间时,静态流水线的效能会降低到比顺序方式的还要差。

因此,在静态流水线机器中,要求程序员编制出(或是编译程序生成)的程序应尽可能调整成有更多相同运算的指令串,以提高其流水的效能。以TI-ASC机器的流水线为例,如果先执行n条浮点加法指令,再执行m条定点乘法指令,其时-空图如图4.21所示。

而动态流水线是指在同一时间内,多功能流水线中的各个功能段可按不同运算或功能的联接方式工作。如图4.22所示,在同一时间段内,某些段按浮点加法联接,而另一些段按定点乘法联接。这样做的好处在于,不要求流入流水线的指令串有相同的功能也能提高流水的吞吐率和设备的利用率。

从图4.21和图4.22比较,静态流水线与动态流水线的差别在于:对于相同的一串运算功能不同的指令而言,动态流水线的吞吐率和设备利用率比静态流水线的高;由于在同一时间内,可以通过不同的联接实现不同的运算,故动态流水线的控制比静态流水线要复杂,需增加相应硬件,故成本比静态流水线的高;从软、硬件功能分配的观点上看,静态流水线把功能负担较多地加到软件上,以简化硬件控制,而动态流水线则把功能负担较多地加在硬件控制上,以提高流水的效能。4.4.4按流水线的连接方式分类根据流水线中各功能段之间是否有反馈回路,可把流水线分为线性流水线和非线性流水线。若流水线各段串行联接,没有反馈回路,各个段只经过一次的,称为线性流水线。而如果流水线中除有串行联接的通路外,有某种反馈回路,使一个任务流经流水线时,需多次经过某个段或越过某些段,则称之为非线性流水线。在非线性流水线中,一个重要的问题是确定什么时候向流水线送入新的任务,使此任务流经流水线各段时不会与先进入的任务争用流水段。这个问题将在本章4.7节中讨论。4.5线性流水线性能分析

衡量流水线处理机性能的指标主要是吞吐率和效率,本节将以线性流水线为例讨论流水线处理机的性能。

4.5.1吞吐率和加速比

1.吞吐率(throughputrate)

吞吐率指单位时间内流水线能处理的指令条数或能输出的数据量。吞吐率越高,计算机系统的处理能力就越强。对流水线而言,吞吐率就是单位时间内能流出的任务数或能流出的结果数。(1)最大吞吐率最大吞吐率是指在流水线正常满负荷工作时,单位时间内机器所能处理的最多指令条数或机器能输出的最多结果数。由于指令的取指和执行过程中的各个子过程所需的时间不同,为了避免各段之间经过时间不匹配,也为了保证各段之间数据通路宽度上能匹配,通常都要在各子过程之间插入一个锁存器,这些锁存器都受同一个时钟脉冲的控制,从而达到同步。如果指令的解释细分为n个子过程,且各个子过程所需的时间分别为Δt1、Δt2、Δt3、…、Δtn,时钟周期应当为max{Δt1、Δt2、Δt3、…、Δtn},对应于流水线的最大吞吐率为:

由此可以看出,流水线的最大吞吐率取决于最慢子过程所需要的时间,我们把流水线中经过时间最长的子过程称为“瓶颈”子过程。(4.1)

如图4.23(a)所示,有一个4段的指令流水线,其中A、C、D段经过的时间均为Δt,而B段的处理时间需要3Δt,则B段就是该指令流水线的瓶颈。根据流水线的最大吞吐率公式,其最大吞吐率TPmax=1/(3Δt),即流水线满负荷工作时,只能每隔3Δt才解释完一条指令,每隔3Δt才能流出一个结果。其时-空图如图4.23(b)所示。

显然,流水线的最大吞吐率受限于瓶颈子过程,要提高流水线的最大吞吐率,应当设法消除此瓶颈子过程。消除瓶颈的一种办法是将瓶颈子过程再细分。如对图4.23(a)的B段进一步进行细分,将其再细分为三个段B1、B2和B3,并且每个段的处理时间都是Δt,这样,该指令流水线的最大吞吐率就变成1/Δt。如图4.24所示。并不是所有子过程都可以进一步细分,如对图4.23(a)中的B段如果不能进一步细分,可以采用消除瓶颈的另一种办法,即重复设置多套瓶颈段并联,让它们交叉进行。

对于图4.23(a)所示的问题,则可以采用三套B段并联,分别以BS1、BS2、BS3命名,每隔Δt轮流给一个瓶颈段分配任务,使它们仍可每隔Δt解释完一条指令。如图4.25所示,其流水线的最大吞吐率也是1/Δt。这种办法需要解决好在各并行子过程之间的任务分配和同步控制,比起瓶颈子过程再细分控制要复杂、设备量要多些。(2)实际吞吐率流水线的实际吞吐率用TP表示,是指从启动流水线处理机开始到流水线操作结束,单位时间内能流出的任务数或能流出的结果数。前面的分析都是在流水线连续流动时能达到的最大吞吐率。实际上,流水开始时总要有一段建立时间,此外还常常会由于各种原因,如功能部件冲突等使流水线无法连续流动,不得不流一段时间,停一段时间,因此实际吞吐率TP总是小于最大吞吐率TPmax。

设指令流水线由m段组成,如图4.26所示,且各段经过的时间均为Δt,则一条指令的解释需要mΔt的时间,之后每隔Δt完成一条指令的解释,则完成n条指令的解释所需要的时间为:

该流水线的实际吞吐率为:(4.2)

从式4.2可以看出,实际吞吐率总是小于最大吞吐率,只有当进入流水线的任务数远大于流水线功能段的数目时,即时,才能使实际吞吐率趋近于最大吞吐率,或者可以近似认为TP=TPmax。对于图4.26,如果流入流水线的任务数不是n,而是周期性的任务,即每流入n条指令之后,延迟ΔT的时间,再流入n条指令,延迟ΔT之后,再流入n条指令,周而复始,则这时的流水线的实际吞吐率TP就应为:(4.3)

综上所述,流水线的实际吞吐率除了与该流水线的功能段数目有关外,还与流入该流水线的指令流或任务流有关。指令流不同,其实际吞吐率也不同。在实际应用中,除了在硬件上对子过程细分外,还应当从软件上采取措施,如选择合适的算法、程序设计方法、编译器等,从软、硬两方面入手,保证在流水线中连续流动的任务数n能远远大于子过程数m,才能充分发挥流水线的效率。否则,在极端情况下,即n=1的时候,由于m的增大,锁存器数也增多,这样实际上增大了任务从流入到流出的流水线通过时间,以至于使其速度反而比顺序串行的还要低。

如果各段经过的时间Δti不相等,其中“瓶颈”段时间为Δtj,完成n条指令的解释,流水线的实际吞吐率为:(4.4)2.加速比(speedupratio)

所谓加速比是指流水线工作相对于等效的非流水线顺序串行工作方式,速度提高的比值。设指令流水线由m段组成,各段经过的时间均为Δt,共完成n条指令的解释,则此流水线方式工作的加速比为:(4.5)

由式4.5可以看出,当n>>m时,流水线的加速比Sp才接近于流水线的段数m,也就是说,当流水线各段时间都一样时,其最大加速比等于流水线的段数m。因此,在n>>m的前提下,增大流水线的段数m,可以提高流水线的加速比Sp。如果考虑各段经过的时间Δti不相等,其中“瓶颈”段时间为Δtj,完成n条指令的解释,则此流水线方式工作的加速比为:(4.6)4.5.2效率(efficiency)

流水线的效率是指流水线的设备利用率。即在整个运行时间里,流水线的设备有百分之多少的时间是真正用于工作的。由于流水线存在有建立时间和排空时间,在连续完成n个任务的时间里,各段并不是满负荷工作的,因此流水线的效率一定小于1。设指令流水线由m段组成,各段经过的时间均为Δt,完成n条指令的解释,流水线的效率为:η1+η2+…+ηmm·η1m·nΔtm·nΔtη===η1==(4.7)mmm·(mΔt+(n-1)Δt)m·T

对于式4.7,从时-空图上来看,所谓效率实际就是n个任务占用的时-空区和m个段总的时-空区面积之比。如果考虑各段经过的时间Δti不相等,其中“瓶颈”段时间为Δtj,完成n条指令的解释。由于流水线的效率实际上就是n个任务占用的时-空区和m个段总的时-空区面积之比,因此,整个流水线的效率为:η1+η2+…+ηmn·∑Δti

η==(4.8)mm·(∑Δti+(n-1)Δtj)

mmi=1i=1

比较各种公式,可以得出如下结论:

(1)Sp=TP·ΣΔti(2)η=Sp/m

mi=14.6线性流水线性能分析举例

对于单功能线性流水线,输入连续任务的情况,通过上一节给出的公式很容易计算出流水线的吞吐率、加速比和效率。

例4.1

用一条4段浮点加法器流水线求8个浮点数的和:Z=A+B+C+D+E+F+G+H。已知流水线的各段经过时间都是Δt,流水线的输出结果可以直接返回到流水线的输入或暂存于相应的缓冲寄存器中,其延迟时间忽略不计。流水线为双输入端,如图4.27(a)所示。

实现8个浮点数的相加,先完成A+B、C+D、E+F、G+H,然后(A+B)和(C+D)、(E+F)和(G+H)又作为新的输入进入流水线,分别实现A+B+C+D及E+F+G+H,最后完成所要求的加法,如图4.27所示。这样,流入流水线的任务数为7个,从时-空图上可以看出,从任务开始到结束,共需15Δt,而顺序完成7个任务需要的时间为7×4Δt=28Δt。因此,该流水线的实际吞吐率为:TP=7/(15Δt)

加速比为:Sp=28Δt/(15Δt)≈1.87

效率为:η=28Δt/(4×15Δt)≈46.7%

例4.2

设有二个向量A、B,各有4个元素,要在如图4.28所示的静态双功能流水线上,计算向量点积A·B=Σai×bi。在该双功能流水线中,S1→S2→S3→S5组成加法流水线,S1→S4→S5组成乘法流水线。设每个流水段所经过的时间为Δt,而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中,其延迟时间和功能切换时间忽略不计。使用合理的算法,能使完成向量点积A·B运算所用的时间最短,并求出流水线在此期间的实际吞吐率TP和效率η。

选择适合于静态流水线工作的算法:⑴连续计算a1×b1、a2×b2、a3×b3、a4×b44个乘法;⑵等执行乘法工作的流水线排空后,进行功能部件的切换,按加法的方式联接流水线功能部件,连续计算(a1×b1+a2×b2)、(a3×b3+a4×b4);⑶产生了上述两个结果后,再最后计算:(a1×b1+a2×b2)+(a3×b3+a4×b4)。显然,最后总共流入多功能流水线的任务数为7个,完成任务所需的时间为15Δt,而顺序完成7个任务需要的时间为4×3Δt+3×4Δt=24Δt。

因此,该流水线的实际吞吐率为:TP=7/(15Δt)

效率为:η=24Δt/(5×15Δt)=32%

前面讨论的是静态流水线,如果把静态流水线改为动态流水线,其它条件不变,那么,在计算向量点积A·B=Σai×bi时,流水线在此期间的吞吐率TP和效率η又该是多少呢?动态流水线的时-空图如图4.29所示。

从图4.29中可以看出,进入流水线的任务数还是7个,但所需要的时间比静态流水线少Δt,只需要14Δt就可完成。在此期间,动态流水线的实际吞吐率为:TP=7/(14Δt)=1/(2Δt)

效率为:η=(4×3Δt+3×4Δt)/(5×14Δt)≈34.3%

从以上两个例子可以看出,动态流水线与静态流水线相比,具有较高的实际吞吐率和效率。4.7非线性流水线的基本概念

前面讨论都是以线性流水线为基础的,由于线性流水线在执行每个任务(指令、操作)的过程中,各段均只通过一次,因此每拍都可以将一个新的任务送入流水线,这些任务不会争用同一个流水段。在非线性流水线中,由于存在有反馈回路,当一个任务在流水线中流过时,在同一个功能段可能要经过多次。因此,就不能每一个时钟周期向流水线输入一个新任务,否则会发生在同一个时刻有几个任务争用同一个功能段的情况。这种情况称为功能部件冲突,或流水线冲突。

为了避免流水线发生冲突,一般采用延迟输入新任务的方法。那么,在非线性流水线的输入端,究竟每间隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个功能段都不发生冲突,这就是非线性流水线的调度问题。在许多非线性流水线中,间隔的周期数往往不是一个常数,而是一串周期变化的数字。因此,非线性流水线调度的任务是要找出一个最小的循环周期,按照这周期向流水线输入新任务,流水线的各个功能段都不会发生冲突,而且流水线的吞吐率和效率最高。

在非线性流水线的表示中,它与线性流水线有2个明显不同的地方:

(1)有反馈线和前馈线;

(2)其输出端经常不在最后一个功能段,而可能从中间任意一个功能段输出。典型的非线性流水线的连接图如图4.30所示。

为了能对流水线的任务进行优化调度和控制,1971年E.S.Davidson提出使用一个二维的预约表(reservationtable)来描述一个任务在非线性流水线中对各功能段的使用情况。预约表用于非线性流水线,是一张二维的表格,其横坐标表示流水线工作的时钟周期,纵坐标表示流水线的功能段,中间画“√”表示该功能段在这一时钟周期处于工作状态,空白的地方表示该功能段在这个时钟周期不工作。

在预约表中,一行有多个“√”表示一个任务在不同时钟周期重复使用了同一个功能段;而一列有多个“√”则表示在同一个时钟周期同时使用了多个功能段。预约表的总行数表示流水线功能段的个数,总列数表示一个任务从流入到流出所经过的时钟周期数。对于图4.30的流水线,由5个功能段组成,段号k分别为1到5,任务经过流水线总共需N=9拍,假设其预约表如图4.31所示。

值得说明的是:(1)一张非线性流水线的预约表可能与多个非线性流水线连接图相对应;(2)一个非线性流水线的连接图也可能对应多张预约表。因此,一条非线性流水线一般需要一个各功能段之间的连接图和一张预约表来共同表示。

根据预约表可以很快得出一个任务使用图4.30的流水线各段所需间隔的拍数。将流水线中所有各段对一个任务流过时,产生争用同一段的节拍间隔数汇集在一起,构成一个延迟禁止表F(forbiddenlist)。从图4.31所给出的预约表,l段相隔8拍,那么两个任务相隔8拍流入流水线必将会争用1段;2段相隔1、5、6拍,则相隔1、5或6拍流入流水线必将会争用2段;5段相隔1拍,两个任务相隔1拍流入流水线必将会争用4段;4段相隔1拍,两个任务相隔1拍流入流水线必将会争用5段。由图4.31的预约表可以得到相应非线性流水线的延迟禁止表F为(1,5,6,8)。即要想不出现争用流水线功能段的现象,相邻两个任务送入流水线的间隔拍数就不能为1、5、6、8拍,这些间隔拍数应当禁止使用。

可以用一个有N-1位的位向量来表示后继新任务间隔各种不同拍数送入流水线时,是否会发生功能段使用的冲突,称此位向量为冲突向量C(collisionvector)。冲突向量(cN-1…ci…c2c1)中第i位的状态用以表示与当时相隔i拍给流水线送入后继任务是否会发生功能段的使用冲突。如果不会发生冲突,令该位为“0”,表示允许送入;否则,让该位为“1”,表示禁止送入。冲突向量取N-1位,是因为经N拍后,任务己流出流水线,不会与后续的任务争用流水线功能段了。

不难看出,输入后续任务还需等待的拍数与前一个任务在流水线中已进行了几拍有关。当第一个任务第1拍送入流水线时,根据禁止表F=(1,5,6,8),可以形成此时的冲突向量C为(10110001),称此为刚流入流水线时的初始冲突向量。由于初始冲突向量的c2、c3、c4、c7为0,所以第二个任务可以距第一个任务2、3、4或7拍流入流水线。当第二个任务流入流水线后,应当产生新的冲突向量,以便决定第三个任务可以相隔多少拍流入流水线,才不会与已进入流水线的前面第一、第二个任务争用功能段,…,依此顺序类推。

显然,随着流水线中第一个任务每拍向前推进一段,原先禁止第二个任务流入流水线的各种间隔拍数均相应减去l拍。这意味着可以将初始冲突向量放在一个移位器中,每拍逻辑右移1位,让左面移空的位补以“0”,以表示如果间隔8拍流入后续任务的话,前一个任务必定已流出流水线而不会发生功能部件使用冲突。因此,随着任务在流水线中的推进,会不断动态地形成当时的冲突向量。

如果选择第二个任务在间隔2拍时流入流水线,对第一个任务而言,冲突向量右移2位成了(00101100)。这样,要想使第三个任务流入流水线后,既不会与第一个任务发生功能段冲突,也不会与第二个任务发生功能段冲突,新的冲突向量就应当是第一个任务当前的冲突向量(00101100)与第二个任务的初始冲突向量(10110001)按位"或",其结果为(10111101)。即第三个任务只能在第二个任务流入流水线后,隔2拍或7拍流入,才不会发生与先前流入流水线的那些任务争用功能段。

按照这样的思路,选择各种可能的间隔拍数流入新的任务,从而又可以产生新的冲突向量,一直进行到不再产生不同的冲突向量为止。由此可以画出用冲突向量表示的流水线状态转移图。图中两个冲突向量之间用有向弧上的数字表示引入后续任务产生新的冲突向量所用的间隔拍数。本例的流水线状态转移图如图4.32所示。

从上面的分析中可以看出,从第二个任务开始,流入流水线的任务间隔拍数就有不同的选择;而实际应用的时候,只能选择一种间隔拍数进入流水线,那么应该选择哪一个间隔拍数进入流水线才不会产生冲突,而且效率最高?只要按流水线状态图中由初始状态出发,能构成一种间隔拍数呈周期性重复的方案来进行流水线的调度,都不会发生功能段使用冲突。然而,我们还希望能寻找一种最佳的调度方案,以便使流水线的吞吐率最高。显然,只需要分别计算出每种调度方案的平均间隔拍数,然后,找出其中之最小者,就是流水线各后续任务流入流水线所用间隔的最佳调度。表4.1各种调度方案的平均间隔拍数调度方案(2,2,7)(2,7)(3,4)(4,3)(3,4,7)(3,7)(4,3,7)(4,7)(7)平均间隔拍数3.674.53.53.54.6754.675.57

由表4.1中可见,采用先隔3拍后隔4拍轮流给流水线送入任务的调度方案是最佳的,平均每隔3.5拍即可流入一个任务,吞吐率最高。尽管(4,3)调度方案平均间隔拍数也是3.5拍,但若实际流入任务数不是循环所需任务数的整数倍时,其实际吞吐率相对会低些,所以不作为最佳调度方案。如图4.33所示,如果有4个任务流入流水线,采用(3,4)的调度方案流入时,所需要的拍数为9+3+4+3=19拍,而采用(4,3)调度方案时,所需要的拍数就变成9+4+3+4=20拍。

同样是4个任务,采用不同调度方案,完成任务的拍数相差1拍。但若流入的任务数为5个的话,采用(3,4)调度方案或(4,3)调度方案,所需的拍数是一样的,都是23拍。这是一种不等间隔的调度策略,比起相等间隔的调度策略在控制上要复杂一些。

为了简化控制,也可以采用相等间隔调度,不过常常会因此而使吞吐率和效率下降。在本例只有一种相等间隔调度方案,即每隔7拍输入一个任务,吞吐率比(3,4)调度方案降低了1/2。如果能有几种不同的相等间隔调度方案,显然应取其中间隔最小的,这样会使吞吐率的下降最少。4.8相关处理和控制机构

流水线只有连续不断地流动,即不出现“断流”,才能获得高效率。造成流水线“断流”的原因很多,有编译程序形成的目标程序不能发挥流水结构的作用,存储系统供不上为连续流动所需的指令和操作数,转移(无条件转移、条件转移)指令的使用,相关(指令相关、主存操作数相关和通用/变址寄存器组操作数相关)和中断的出现等。

前面讨论了重叠方式中出现的指令相关、主存操作数相关、通用寄存器组的操作数相关及基址值变址值相关。这些相关在流水机器中同样也会出现。而且,由于流水是同时解释更多条指令,所以相关状况要比重叠机器的更复杂、更严重,如果处理不当,就会使流水效率显著下降。指令相关、主存操作数相关和通用/变址寄存器组操作数相关由于只影响相关的二条或几条指令,而至多影响流水线某些段的推后工作,并不会改动指令缓冲器中预取到的指令内容,影响是局部的,所以被称之为局部性相关。

同样,流水机器在遇到转移指令,尤其是条件转移指令时,效率也会显著下降。如果流水机器的转移条件码是由条件转移指令本身或是由它的前一条指令形成时,则只有该指令流出流水线才能建立转移条件,并依此决定下一条指令的地址。那么从条件转移指令进入流水线,译码出它是条件转移指令直至它流出的整个期间,流水线都不能继续往前处理。若转移成功,且转向的目标指令又不在指令缓冲器内时,还得要重新访存取指令。

转移指令和其后的指令之间存在关联,使之不能同时解释,其造成的对流水机器的吞吐率和效率下降的影响要比指令相关、主存操作数相关和通用/变址寄存器操作数相关严重得多,它可能会造成流水线中很多已被解释的指令作废,重新预取指令进入指令缓冲寄存器,它将影响整个程序的执行顺序,所以称之为全局性相关。4.8.1局部性相关的处理局部性相关包括指令相关、访存操作数相关和通用/变址寄存器组操作数相关等,都是由于在机器同时解释的多条指令之间出现了对同一个单元(包括主存单元和通用寄存器)的“先写后读”要求。重叠机器在处理这些局部性相关时有两种办法:一种办法是推后对相关单元的读,直至写入完成;另一种办法是设置相关专用通路,使得不必先把运算结果写入相关存储单元,再由它读出后才能使用,而是经相关专用通路直接使用运算结果,这样,就可省去“写入”和“读出”两个访问周期。

由于流水技术是重叠技术的延伸,因此上述两种方法的思路也适用于流水机器处理局部性相关,但由于流水机器是同时解释更多条指令,所以其相关专用通路的设计当然要比重叠的复杂。流水线有多个子过程,多条指令同时处在不同子过程上解释。在控制机构上需要解决好如下问题:如何判定流入流水线的多条指令之间是否相关,如何控制推后对相关单元的读,如何设置相关专用通路并控制相关专用通路的连通和断开。对流水的流动顺序的安排和控制可以有两种方式:顺序流动方式和异步流动方式。

顺序流动方式是指流水线输出端的任务(指令)流出顺序和输入端的流入顺序一样。如图4.34所示,有一个8段的流水线,其中第2段为读段,第7段为写段。有一串指令h、i、j、k、l、m、……依次流入,当指令j的源操作数地址与指令h的目的操作数地址相同时,h和j就发生了先写后读的操作数相关。顺序流动方式时,就要求j流到读段时必须停下来等待,直到h到达写段并完成写入后,才能继续向前流动,否则j将会因读出的不是h写入后的内容而造成错误。

这是一种推后对相关单元读的办法,由于j停下来,j之后的指令也被迫停下来。顺序流动方式的优点是控制比较简单。例如TI-ASC机就采用了这种方式。其缺点是一旦相关后,在空间和时间上都会有损失,使得流水线的吞吐率和功能部件的利用率降低。空间上会有功能段空闲出来,使部件利用率(效率)降低,时间上推后流出,会使流水线吞吐率降低。

异步流动方式是指流水线输出端的任务(指令)流出顺序和输入端的流入顺序可以不一样。异步流动方式的优点是流水线的吞吐率和功能部件的利用率都不会下降。如图4.34的“可以不顺序流动的”那行所示的指令在流水线内的流动顺序,如果让j之后的那些指令,如k、l、m、n等,只要与j没有相关,就越过j继续向前流动。但采用异步流动方式带来了新的问题,采用异步流动的控制复杂,而且会发生在顺序流动中不会出现的其它相关。由于异步流动要改变指令的执行顺序,同时流水线的异步流动还会使相关情况复杂化,出现除“先写后读”相关外的“写-写”相关、“先读后写”相关等。

例如,若指令i、k都有写操作,而且是写入同一单元,那该单元的最后内容本应是指令k的写入结果。但是,由于指令i执行时间很长或有“先写后读”相关,就会出现指令k先于指令i到达“写段”,从而使得该单元的最后内容错为指令i的写入结果。我们称这种对同一单元,要求在先的指令先写入,在后的指令后写入的关联为“写-写”相关。采用异步流动时,应在控制机构上保证当发生“写-写”相关后写入的先后顺序不变。另外,若指令i的读操作和指令k的写操作是对应于同一单元,指令i读出的本应是该单元的原存内容。但若指令k越过指令i向前流,且其写操作在指令i的读操作开始前完成,那指令i就会错误地读出了指令k的写入结果。我们称这种对同一单元,要求在先的指令先读出,在后的指令才写入的关联为“先读后写”相关。显然,“写-写”相关和“先读后写”相关都只有在异步流动时才有可能发生,顺序流动时是不可能发生的。所以,在设计采用异步流动方式工作时,控制机构应能处理好这3种关系。

在前面异步流动方式的例子中,“写段”和“读段”之间设置了相关专用通路。然而,流水机器是同时解释多条指令,还经常采用多个可并行工作的功能部件,不应当在各个功能部件之间为每种局部性相关都设置单独的相关专用通路,否则会使硬件耗费大,控制复杂。一般的流水线机器都是采用分布式管理和控制以及设置公共数据总线来简化各种相关的判别和实现相关专用通路的连接。4.8.2全局性相关的处理全局性相关指的是已进入流水线的转移指令(尤其是条件转移指令)和其后面的指令之间的相关。下面介绍一些常用的处理方法。

1.分支预测技术若指令i是条件转移指令,它有两个分支,如图4.35所示。一个分支是i+1、i+2、i+3、…,按原来的顺序继续执行下去,称转移不成功分支,另一个分支是转向p,然后继续执行p+1、p+2、…,称为转移成功分支。

流水方式是同时解释多条指令,因此,当指令i进入流水线,后面进i+1还是进p,只有等条件码建立才能知道,而这一般要等该条件转移指令快流出流水线时才行。如果在此期间让i之后的指令等着,流水线就会“断流”,性能将会急剧下降。为了在遇到条件转移指令后,流水线仍能继续向前流动,不使吞吐率和效率下降,绝大多数机器都采用所谓的“猜测法”,即分支预测技术。猜取第i+1条指令和第p条指令所在分支中的一个继续向前流动。

分支预测技术可以分为静态分支预测和动态分支预测,这里我们讨论静态分支预测技术,可以有两种实现方法。一种是分析程序结构本身的特点或使用该程序以前运行时收集的模拟信息。不少条件转移两个分支的出现概率是能够预估的,只要程序设计者或编译程序把出现概率高的分支安排为猜选分支,就能显著减少由于处理条件转移所带来的流水线吞吐率和效率的损失。另一种是按照分支的方向来预测分支是否转移成功,当两者概率差不多时,一般选取不成功转移分支。

因为这些指令一般已预取进指令缓冲器,可以很快从指令缓冲器取出,进入流入线而不必等待。如果猜选成功转移分支,指令p很可能不在指令缓冲器中,需花较长时间去访存取得,使流水线实际上断流。例如IBM360/91就采用转移不成功分支。但这两种方法猜错的概率都不会低于30%。要提高预测的准确度,可以采用动态预测的方法,在硬件上建立分支预测缓冲站及分支目标缓冲站,根据执行过程中转移的历史记录来动态的预测转移选择,其预测准确度可以提高到90%左右。这种方法在POWERPC620的分支预测中得到了采用。

显然,采用猜测法的控制机构应能保证在猜错时可返回到分支点之前,并能把沿猜测分支流水时的指令的已有解释全部作废,并恢复分支点处的原有现场。恢复已经开始解释的那些指令的原有现场有如下三种方法:一是对猜测指令的解释只完成译码和准备好操作数,在转移条件码出现前不执行运算;二是对猜测指令的解释可完成到运算完毕,但不送回运算结果;然而早期所用的这两种办法不方便,因为若猜对后还要让这些指令继续完成余留的操作。随着器件技术的发展,已经可以让它们和正常情况一样,不加区别地全部解释完。三是对在流水线中的猜测指令不加区别地全部解释完,但需把可能被破坏的原始状态都用后援寄存器保存起来,一旦猜错就取出后援寄存器的内容来恢复分支点的现场。一般猜对的概率要高,猜对后既不用恢复,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论