控制相关的动态解决技术

*,28,4.3 控制相关的动态解决技术,处理器一个时钟周期流出多条指令受到以下两 个因素的限制：,流出,n,条,指令的处理器中，遇到分支指令的 速度也快了,n,倍；,根据,Amdahl,定律可知，随着机器,CPI,的降低，控制相关对性能的影响越来越大。,第四章 指令级并行,本节着重于：,通过硬件技术，动态地进行分支处理，对程序运行时的分支行为进行预测，提前对分支操作做出反应，加快分支处理的速度。,分支的最终延迟,取决于流水线的结构、预测的方法和预测错误后恢复所采取的策略。,4.3 控制相关的动态解决技术,4.3.1 分支预测缓冲,动态分支预测必须解决,两个问题,：,如何记录一个分支操作的历史。,决定预测的走向。,记录分支历史的方法有以下几种：,（1）仅仅记录最近一次或最近几次的分支历史；,（2）记录分支成功的目标地址；,（3）记录分支历史和分支目标地址，相当于前,面两种方式的结合；,（4）记录分支目标地址的一条或若干条指令。,4.3 控制相关的动态解决技术,分支预测缓冲技术,（,Branch-Prediction Buffer或者Branch History Table,，简写为,BTB或者BHT,）：目前广泛使用的最简单的动态分支预测技术。使用一片存储区域，记录最近一次或几次分支特征的历史。,1.,只有,1个预测位,的分支预测缓冲,索引,：分支指令地址的低位。,存储区,：,1位,的分支历史记录位，又称为,预测位，记录该指令最近一次,分支是否成功。,4.3 控制相关的动态解决技术,状态转换图,“0”,记录分支不成功,“1”,记录分支成功,图4.9 只有1个预测位的分支预测缓冲状态转换图,4.3 控制相关的动态解决技术,2.分支预测缓冲技术包括两个步骤,分支预测 如果当前缓冲记录的预测位为,“1”,，则预,测分为成功；如果预测位为,“0”,，则预测分支为不成功。,预测位修改 如果当前分支成功，则预测位置为,“1”,；如果当前分支不成功，预测位置为,“0”,。,3.分支预测错误时，预测位就被修改，并且需 要恢复现场，程序从分支指令处重新执行,。,4.3 控制相关的动态解决技术,图4.10 分支预测执行不成功和重新执行过程,4.3 控制相关的动态解决技术,例4.6,一个循环共循环,10,次，它将分支成功,9,次，,1,次不成功。假设此分支的预测位始终在缓冲区中。那么分支预测的准确性是多少？,解,这种固定的预测将会在第一次和最后一次 循环中出现预测错误。,第一次预测错误是源于上次程序的执行，因为上一次程序最后一次分支是不成功的。,最后一次预测错误是不可避免的，因为前 面的分支总是成功，共,九,次。,因此，尽管分支成功的比例率是,90%,，但分支预测的准确性为,80%,（,两,次不正确，,8,次确）。,4.3 控制相关的动态解决技术,4.,1位预测机制的,缺点,只要预测出错，往往是连续两次而不是一次。,5.解决方法,采用,两个预测位的预测机制,。,在两个预测位的分支预测中，更改对分支的预测必须有两次连续预测错误。,两位分支预测的状态转换图,4.3 控制相关的动态解决技术,图4.11 具有两个分支预测位的分支预测缓冲状态转换机制,4.3 控制相关的动态解决技术,6.,n位,分支预测缓冲,采用,n,位,计数器，则计数器的值在,0到2,n,-1,之间：,当计数器的值大于或等于最大值的一半（,2,n-1,）,时，则预测下一次分支成功；,否则预测下一次分支不成功。,预测位的修改和两位预测时相同：,当分支成功时计数器的值,加1,，不成功时,减1,。,研究表明：,n,位,分支预测的性能和两位分支预测差不多，因而大多数处理器都只采用两位分支预测。,4.3 控制相关的动态解决技术,7.对于真实的应用程序，两位的分支预测的准确率可达到多少呢？,SPEC89,标准程序的测试：,在使用,4096,个记录项的缓冲区时，分支 预测准确率可达到,99%到82%,。,使用无穷多历史记录项的分支预测缓冲，只有少量程序的分支预测准确率仅仅比,4096,个记录项提高,1%,，多数程序的预测精度是相 同的。,因此，对于,SPEC89,应用环境而言，,4K,的 缓冲区是恰当的。,8.上述分支预测机制对于改进后的,DLX,流水线没有帮助。,4.3 控制相关的动态解决技术,4.3.2 分支目标缓冲,目标：,将分支的开销降为零。,方法：,分支目标缓冲,将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标示；取指令阶段，所有指令地址都与保存的标示作比较，一旦相同，我们就认为本指令是分支指令，且认为它转移成功，并且它的分支目标（下一条指令）地址就是保存在缓冲区中的分支目标地址。,这个缓冲区就是,分支目标缓冲区,（,Branch-Target Buffer，简记为BTB，或者Branch-Target Cache,）。,4.3 控制相关的动态解决技术,1.分支目标缓冲结构和工作过程,图4.12 分支目标缓冲的结构和工作过程,2.在流水线的各个阶段中，具有分支目标缓冲的工作 分配如图4.13。,问题：,解决预测错误或不命中的延迟。,3.采用,BTB,技术时指令在各种情况下的延迟,指令在,BTB,中？,是,是,不是,不是,预测结果,成功,成功,实际的动作,成功,不成功,成功,不成功,延迟周期,0,2,2,0,表4.3 采用BTB技术时指令在各种情况下的延迟,4.3 控制相关的动态解决技术,例4.7,按,表4.3,计算分支转移总的延迟，根据下面的假 设，计算分支目标缓冲的性能。（1）对于,BTB,中的指令，预测准确率,90%,（2）缓冲区命中率,90%,（3）不在,BTB,中分支转移成功的比例为,60%,解,根据,表4.3,的分类，性能计算包括,4个,部分：,（1）在,BTB,中，预测成功，实际成功，此时的 延迟为,0,。,（2）在,BTB,中，预测成功，实际不成功，此时,的延迟为：,4.3 控制相关的动态解决技术,BTB命中率,预测错误率,2,=90%,10%,2,=0.18（时钟周期）,（3）不在,BTB,中，实际成功，此时的延迟为：,（1-BTB命中率）,不在BTB中分支转移成功率,2,=10%,60%,2,=0.12（时钟周期）,（4）不在,BTB,中，实际不成功，此时的延迟为,0,。,4.3 控制相关的动态解决技术,4.对分支预测机制的一种改进,在缓冲区中不仅存入目的地址，而且还存入一 个或多个目标指令。有两种潜在的,好处,：,在连续取指令之前，可以较长时间的访问缓冲区，这时的分支目的缓冲区较大。,对目的指令进行缓冲，构成称为,分支目标指令缓冲,（,branch folding,）,的结构，它可使无条件分支的延迟达到零，甚至有的条件分支也可达到零延迟。,4.3 控制相关的动态解决技术,4.3.3 基于硬件的前瞻执行,前瞻,（,Speculation,）的技术方法,：,它允许在处理器还未判断指令是否能执行之前就提前执行,，以克服控制相关。,在大多数指令前瞻正确的前提下，前瞻就可以有效地加快分支处理的速度。,1.基于硬件的前瞻执行结合了,三种思想,：,（1）采用动态的分支预测技术来选择后续执 行语句；,4.3 控制相关的动态解决技术,（2）在控制相关消除之前指令前瞻执行；,（3）对基本块采用动态调度。,2.基于硬件的前瞻是动态地根据数据相关性来选择指令和指令的执行时间。,实质：,数据流驱动运行,（,data-flow execution,）只要操作数有效，指令就可以执行。,3.指令的确认,前瞻执行的指令产生的结果要一直到指令处于非前瞻执行状态时，才能确定为最终结果，才允许最终写到寄存器或存储器中去。,4.3 控制相关的动态解决技术,4.实现前瞻的,关键思想,：,允许指令乱序执行，但必须顺序确认。,5.再定序缓冲（,reorder buffer，简记为ROB,）保存那些执行完毕但未经确认的指令及其结果。在指令执行完毕和确认之间这段时间里，由,再定序缓冲提供所有其他指令需要的作为操作数的数据。再定序缓冲区还可以取代取（,load,）缓,冲区。,4.3 控制相关的动态解决技术,再定序缓冲的每个项包含,三个域,：,（1）指令的类型,指令类型包括是否是分支（尚无结果）、存操作（目的地址为存储器）或寄存器操作,（,ALU,操作或目的地址是寄存器的取操作）。,（2）目的地址,目的地址域给出结果应写入的目的寄存,器号（对于取操作和,ALU,指令）或存储器的地,址（存操作）。,（3）值域,值域用来保存指令前瞻执行的结果，直 到指令得到确认。,4.3 控制相关的动态解决技术,使用再定序缓冲的处理部件的硬件结构,图4.14 采用Tomasulo算法并支持前瞻执行的DLX浮点部件的结构,例4.8,假设浮点功能单元的延迟为加法是,2个,时钟周 期，乘法是,10个,时钟周期，除法,40个,时钟周,期。给出下面的代码段当指令,MULTD,要确认,时的状态。,LDF6,34(R2),LDF2,45(R3),MULTDF0,F2,F4,SUBDF8,F6,F2,DIVDF10,F0,F6,ADDDF6,F8,F2,4.3 控制相关的动态解决技术,解,状态如图4.15所示。,名称,保留站,Add1,Add2,Add3,Mult1,Mult2,忙,no,no,no,no,yes,操作,MULTD,DIVD,Vj,Mem45+RegsR2,Vk,Regs4,Mem34+RegsR2,Qj,#3,Qk,目的,#3,#5,4.3 控制相关的动态解决技术,项号,ROB,1,2,3,4,5,6,忙,no,no,yes,yes,yes,yes,LD,LD,MULTD,SUBD,DIVD,ADDD,指令,F6,34(R2),F2,45(R3),F0,F2,F4,F8,F6,F2,F10,F0,F6,F6,F8,F2,状态,确认,确认,写结果,写结果,执行,写结果,目的,F6,F2,F0,F8,F10,F6,值,Mem34+RegsR2,Mem45+RegsR3,#2,RegsF4,#1-#2,#4+#2,浮点寄存器状态表,F0 F2 F4 F6 F8 F10 F30,ROB,号,3 6 4 5,忙 yes no no yes yes yes,no,域,通过再定序缓冲，可以在进行精确异常处理的同时进行动态指令调度。,前瞻执行的技术策略很容易的推广到整数寄存器和整数功能单元上。前瞻技术存在的一个,主要缺点,：支持前瞻的硬件太复杂，需要大量的硬件资源。,4.3 控制相关的动态解决技术,