第章指令级并行

1、2022-5-2614.1 指令级并行 指令级并行的概念指令级并行的概念几乎所有的处理机都利用流水线来使几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能指令重叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并的目的。这种指令之间存在的潜在并行性称为行性称为指令级并行。指令级并行。 （ILPILP：Instruction-Instruction-Level ParallelismLevel Parallelism）2022-5-262本章研究：本章研究：如何通过各种可能的技术，如何通过各种可能的技术，获得更多的指令级并行性。获得更多的指令级并行性。 硬件软件技术硬件软件技

2、术 必须要硬件技术和软件技术互相必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程配合，才能够最大限度地挖掘出程序中存在的指令级并行。序中存在的指令级并行。2022-5-2631.1.流水线处理机的实际流水线处理机的实际CPICPI理想流水线的理想流水线的CPICPI加上各类停顿的时钟周加上各类停顿的时钟周期数：期数： CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 理想理想CPICPI是衡量流水线最高性能的一个指标。是衡量流水线最高性能的一个指标。IPCIPC：Instructions Per CycleInstructions Per Cycle

3、 （每个时钟周期完成的指令条数）（每个时钟周期完成的指令条数）2022-5-2642.基本程序块基本程序块 基本程序块基本程序块：一段除了入口和出口以外一段除了入口和出口以外不包含其他分支的线性代码段。不包含其他分支的线性代码段。程序平均每程序平均每5 57 7条指令就会有一个分支。条指令就会有一个分支。 循环级并行：循环级并行：使一个循环中的不同循环体使一个循环中的不同循环体并行执行。并行执行。 开发循环体中存在的并行性开发循环体中存在的并行性 最常见、最基本最常见、最基本 是指令级并行研究的重点之一是指令级并行研究的重点之一2022-5-265例如，例如，考虑下述语句：考虑下述语句： fo

4、r for （i=1i=1； i=500i=500； i=ii=i1 1） ai=aiai=ai s s；p每一次循环都可以与其他的循环重每一次循环都可以与其他的循环重叠并行执行；叠并行执行；p在每一次循环的内部，却没有任何在每一次循环的内部，却没有任何的并行性。的并行性。 2022-5-266 3.最基本的开发循环级并行的技术最基本的开发循环级并行的技术循环展开（循环展开（loop unrollingloop unrolling）技术）技术采用向量指令和向量数据表示采用向量指令和向量数据表示 4. 相关与流水线冲突相关与流水线冲突相关有三种类型：相关有三种类型：数据相关、名相关、控制相关数据

5、相关、名相关、控制相关2022-5-267 流水线冲突流水线冲突是指对于具体的流水线来说，是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。指令不能在指定的时钟周期执行。流水线冲突有三种类型：结构冲突、数流水线冲突有三种类型：结构冲突、数据冲突、控制冲突据冲突、控制冲突 相关是程序固有的一种属性，它反映了程相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。序中指令之间的相互依赖关系。 具体的一次相关是否会导致实际冲突的发具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流生以及该冲突

6、会带来多长的停顿，则是流水线的属性。水线的属性。2022-5-2685. 可以从两个方面来解决相关问题：可以从两个方面来解决相关问题：保持相关，但避免发生冲突。保持相关，但避免发生冲突。 指令调度指令调度 通过代码变换，消除相关。通过代码变换，消除相关。6.程序顺序程序顺序：由源程序确定的在完全串行：由源程序确定的在完全串行方式下指令的执行顺序。方式下指令的执行顺序。必须保持程序顺序必须保持程序顺序 7. 控制相关并不是一个必须严格保持的控制相关并不是一个必须严格保持的关键属性。关键属性。2022-5-2698. 对于正确地执行程序来说，必须保持的最关键对于正确地执行程序来说，必须保持的最关键

7、的两个属性是：的两个属性是：数据流数据流和和异常行为。异常行为。 保持异常行为保持异常行为是指：无论怎么改变指令的执是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。行顺序，都不能改变程序中异常的发生情况。 即原来程序中是怎么发生的，改变执行顺即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。序后还是怎么发生。 弱化为：指令执行顺序的改变不能导致程弱化为：指令执行顺序的改变不能导致程序中发生新的异常。序中发生新的异常。 如果我们能做到保持程序的数据相关和控制如果我们能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。相关，就能保持程序的数据流和异常行为。 2

8、022-5-26104.2 4.2 流水线的动态调度流水线的动态调度方法方法( (简述简述) ) 流水线的静态调度流水线的静态调度 主要借助软件对指令执行顺序进行调度，主要借助软件对指令执行顺序进行调度，减少流水线中因相关冲突而引起的停顿减少流水线中因相关冲突而引起的停顿时间。时间。 流水线的动态调度流水线的动态调度 主要通过硬件重新安排指令的执行顺序，主要通过硬件重新安排指令的执行顺序，减少流水的停顿。减少流水的停顿。2022-5-2611 (1)(1)能处理某些在编译时无法知道的相能处理某些在编译时无法知道的相关情况。关情况。 (2)(2)能简化编译程序设计。能简化编译程序设计。 (3)(

9、3)使代码有可移植性。使代码有可移植性。 动态调度方法的主要缺点是硬件较为复动态调度方法的主要缺点是硬件较为复杂。杂。流水线动态调度的优点流水线动态调度的优点2022-5-2612 集中式动态调度集中式动态调度 利用状态记录控制器利用状态记录控制器( (或记分牌或记分牌 ScoreBoardScoreBoard) )在程在程序执行过程中，对流水线中的各个功能部件的工序执行过程中，对流水线中的各个功能部件的工作状态、进入流水线中的各条指令的工作状态、作状态、进入流水线中的各条指令的工作状态、指令所使用的寄存器情况等进行集中的统一记录指令所使用的寄存器情况等进行集中的统一记录和调度。和调度。 集中

10、式动态调度集中式动态调度依靠硬件在程序运行过程中对可依靠硬件在程序运行过程中对可能出现的相关情况加以检测，从而保证流水线中能出现的相关情况加以检测，从而保证流水线中的各个功能部件能最大限度地重叠工作的各个功能部件能最大限度地重叠工作。 集中式动态调度常用于解决乱序方式流水线中的集中式动态调度常用于解决乱序方式流水线中的相关冲突相关冲突。4.2.1 4.2.1 流水的集中式动态调度流水的集中式动态调度2022-5-2613IF ID整数部分整数部分浮点加浮点加浮点乘浮点乘浮点除浮点除RF记录控制器记录控制器EX MEMWB 指令指令控制控制/状态状态控制控制/状态状态集中式动态调度集中式动态调度

11、寄存器堆寄存器堆2022-5-2614记分牌目的记分牌目的 记分牌技术的目标：记分牌技术的目标： 尽可能早地执行无关指令，在没有数据相关的情尽可能早地执行无关指令，在没有数据相关的情况下，达到每个时钟周期执行一条指令。况下，达到每个时钟周期执行一条指令。 记分牌电路全盘负责指令的流出、执行以及相关记分牌电路全盘负责指令的流出、执行以及相关检测。检测。 要发挥指令乱序执行的好处，必须有多条指令同要发挥指令乱序执行的好处，必须有多条指令同时处于执行阶段，这就要求有多个功能部件或功时处于执行阶段，这就要求有多个功能部件或功能部件流水化或两者兼有。能部件流水化或两者兼有。 一般，采用多个功能部件。一般

12、，采用多个功能部件。2022-5-2615 如：如：CDC6600具有具有16个功能部件：个功能部件： 4个浮点部件、个浮点部件、5个存储器访问部件、个存储器访问部件、7个整数操个整数操作部件。作部件。 对于对于DLX，记分牌技术主要用于浮点部件，因为记分牌技术主要用于浮点部件，因为其他部件的操作延迟很小，可以不计。其他部件的操作延迟很小，可以不计。 DLX的部件是：的部件是：1个浮点乘法器、个浮点乘法器、1个浮点加法器、个浮点加法器、1个浮点除法部件和个浮点除法部件和1个整数部件，其中整数部件个整数部件，其中整数部件用于处理所有的存储器访问、分支处理和整数操用于处理所有的存储器访问、分支处理

13、和整数操作。作。 RISC的超标量机的超标量机也可以采用类似的方法。也可以采用类似的方法。2022-5-2616记分牌的三个主要组成部分记分牌的三个主要组成部分 指令状态：指令状态：指明指令所处的阶段指明指令所处的阶段 功能部件状态：功能部件状态：指出功能部件的工作状指出功能部件的工作状态态 寄存器结果状态：寄存器结果状态：指出功能部件将要回指出功能部件将要回写结果到寄存器。如果不回写，则为空写结果到寄存器。如果不回写，则为空状态。状态。2022-5-2617DLX记分牌的四级操作记分牌的四级操作 将每条指令的执行按将每条指令的执行按4步处理（主要考虑浮点等功步处理（主要考虑浮点等功能的操作，

14、忽略能的操作，忽略MEM）：）： 1.指令流出（指令流出（Issue, 记为记为IS）：如果指令所需的功：如果指令所需的功能部件空闲，并且其他正在执行的指令使用的目能部件空闲，并且其他正在执行的指令使用的目的寄存器与该指令的不同，记分牌就向相应的功的寄存器与该指令的不同，记分牌就向相应的功能部件发射该指令，并改变记分牌内部的数据结能部件发射该指令，并改变记分牌内部的数据结构。这一步代替了构。这一步代替了ID的一部分。的一部分。 解决了结构相关和解决了结构相关和WAW相关。相关。2022-5-2618 2.读操作数（读操作数（Read Operand, 记记RO）：如果前面：如果前面已流出的正在

15、运行的指令不对本指令的源操作数已流出的正在运行的指令不对本指令的源操作数寄存器进行写操作，或者一个正在工作的功能部寄存器进行写操作，或者一个正在工作的功能部件已经完成了对这个寄存器的写操作，那么此操件已经完成了对这个寄存器的写操作，那么此操作数有效。整个检测工作由记分牌完成。当操作作数有效。整个检测工作由记分牌完成。当操作数有效后，记分牌告诉功能部件读操作数并开始数有效后，记分牌告诉功能部件读操作数并开始执行。执行。 解决解决RAW相关，代替相关，代替ID的一部分工作。（与的一部分工作。（与1.合合成，就是成，就是ID的工作）的工作）2022-5-2619 3. 执行（执行（Execution

16、,记记EX）：取到操作数后就开始：取到操作数后就开始执行指令。执行指令。 这一步相当于这一步相当于DLX流水线的流水线的EXE阶段，并且在流阶段，并且在流水线中要占用多个时钟周期。水线中要占用多个时钟周期。 4. 写结果（写结果（Write Result，记，记WR）：）：记分牌知道记分牌知道指令执行完毕后，如果目标寄存器空闲，就将结指令执行完毕后，如果目标寄存器空闲，就将结果写到该目标寄存器中，然后释放本指令使用的果写到该目标寄存器中，然后释放本指令使用的所有资源。所有资源。 此步可解决此步可解决WAR相关。这一步代替了流水线的相关。这一步代替了流水线的WB工作。工作。2022-5-2620

17、4.2.2 4.2.2 流水的分布式动态调度流水的分布式动态调度 分布式动态调度法也称动态指令调度法、分布式动态调度法也称动态指令调度法、公共数据总线法、令牌法。公共数据总线法、令牌法。由由R.M.Tomasulo于于1967年首先提出，年首先提出，并最早在大型计算机并最早在大型计算机IBM 360/91处处理机的浮点处理部件中被采用。理机的浮点处理部件中被采用。分布式动态调度分布式动态调度 利用乱序流动方式来提高流水线的性能，利用乱序流动方式来提高流水线的性能，并通过分散控制的方法处理数据相关。并通过分散控制的方法处理数据相关。2022-5-2621 例：在流水机例：在流水机IBM 360/

18、91中，采用公共数据总线中，采用公共数据总线CDB来实现某些相关专用通路连接，并通过给每来实现某些相关专用通路连接，并通过给每个浮点数寄存器个浮点数寄存器FLR设置一个设置一个“忙忙”标志来判别标志来判别指令间所用的数据是否发生数据相关，只要某些指令间所用的数据是否发生数据相关，只要某些FLR正在使用，就将正在使用，就将“忙忙”位置位置“1”表示存在数表示存在数据相关，一旦使用完成，就将据相关，一旦使用完成，就将“忙忙”位置成位置成“0”。 以下面的一段程序为例说明以下面的一段程序为例说明TomasuloTomasulo算法。算法。k： LOAD F1, Ak+1： FADD F1, F2k+

19、2： FMUL F1, F3k+3： STORE F1, B2022-5-2622 存存 储储 器器 总总 线线 指指 令令 分分 析析 部部 件件 C C D D B B 6 6 先先 行行 读读 数数 站站 控控 制制 先先 行行 操操 作作 站站 F F 7 7 忙忙 位位 站站 号号 通通 用用 寄寄 存存 器器 5 5 ( ( F F L L B B ) ) ( ( F F L L O O S S ) ) F F 6 6 ( ( F F L L R R ) ) 4 4 F F 5 5 3 3 F F 4 4 2 2 F F 3 3 F F L L B B 1 1 F F 2 2 F

20、F 1 1 1 1 1 1 0 0 / / 8 8 控控 制制 站站 号号 后后 行行 写写 数数 站站 F F 0 0 译译 码码 器器 A A 3 3 1 1 2 2 站站 号号 源源1 1 站站 号号 源源2 2 控控 制制 M M 2 2 9 9 站站 号号 源源1 1 站站 号号 源源2 2 控控 制制 A A 2 2 1 1 1 1 M M 1 1 8 8 1 1 0 0 ( ( F F 3 3 ) ) A A 1 1 1 1 0 0 ( ( F F L L B B 1 1 ) ) ( ( F F 2 2 ) ) 乘乘 / / 除除 法法 器器 加加 法法 器器 （ 6 6 级级

21、流流 水水 线线 ） ( ( 2 2 级级 流流 水水 线线 ) ) C D B I I B B M M 3 3 6 6 0 0 / / 9 9 1 1 处处 理理 机机 的的 浮浮 点点 执执 行行 部部 件件 控控 制制 总总 线线 F F L L B B 总总 线线 F F L L R R 总总 线线 C C D D B B 2022-5-2623特点：特点： （1）加法器和乘法器分别设置了）加法器和乘法器分别设置了3个和个和2个保存站，个保存站，减小了资源使用冲突的机会。减小了资源使用冲突的机会。 （2）调度算法使用保存站，通过对寄存器重新命）调度算法使用保存站，通过对寄存器重新命名（

22、改写站号）自然地消除了名（改写站号）自然地消除了WAR和和WAW相关的相关的可能性。可能性。 （3）通过对）通过对FLR寄存器忙位状态的判别，来检测寄存器忙位状态的判别，来检测是否存在是否存在RAW相关。相关。 （4）借助）借助CDB公共数据总线作为专用相关通路，公共数据总线作为专用相关通路，将有关数据直接送到所有需要它的功能部件。将有关数据直接送到所有需要它的功能部件。2022-5-2624* *基于基于TomasuloTomasulo算法的算法的MIPSMIPS基本结构基本结构 从指令部件来从指令部件来 浮点寄存器浮点寄存器 FP store 缓冲器缓冲器 load 缓冲器缓冲器 地址部件

23、地址部件 load/store 操作操作 浮点操作浮点操作 操作数总线操作数总线 操作总线操作总线 数据数据 1 1 存储部件存储部件 浮点加法器浮点加法器 浮点乘法器浮点乘法器 指令队列指令队列 地址地址 2 3 2 3 4 5 6 公共数据总线（公共数据总线（CDB） 1 2 保留站保留站 标识标识 标识标识 2022-5-2625保留站（保留站（reservation stationreservation station） 每个保留站中保存一条已经流出并等待到本功能部每个保留站中保存一条已经流出并等待到本功能部件执行的指令（相关信息）。件执行的指令（相关信息）。包括：包括：操作码、操操作

24、码、操作数以及用于检测和解决冲突的信息。作数以及用于检测和解决冲突的信息。在一条指令流出到保留站的时候，如果该指令在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到的源操作数已经在寄存器中就绪，则将之取到该保留站中。该保留站中。如果操作数还没有计算出来，则在该保留站中如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。记录将产生这个操作数的保留站的标识。浮点加法器有浮点加法器有3 3个保留站：个保留站：ADD1ADD1，ADD2ADD2，ADD3ADD3浮点乘法器有浮点乘法器有两两个保留站：个保留站：MULT1MULT1，MULT2MULT

25、2 每个保留站都有一个标识字段，唯一地标识了该每个保留站都有一个标识字段，唯一地标识了该保留站。保留站。 2022-5-2626公共数据总线公共数据总线CDBCDB （一条重要的数据通路）（一条重要的数据通路）所有功能部件的计算结果都是送到所有功能部件的计算结果都是送到CDBCDB上，由上，由它把这些结果直接送到（播送到）各个需要它把这些结果直接送到（播送到）各个需要该结果的地方。该结果的地方。在具有多个执行部件且采用多流出（即每个在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要时钟周期流出多条指令）的流水线中，需要采用多条采用多条CDBCDB。2022-5-262

26、7loadload缓冲器和缓冲器和storestore缓冲器缓冲器 存放读存放读/写存储器的数据或地址写存储器的数据或地址 loadload缓冲器的缓冲器的作用有作用有3 3个：个：存放用于计算有效地址的分量；存放用于计算有效地址的分量；记录正在进行的记录正在进行的loadload访存，等待存储器的访存，等待存储器的响应；响应；保存已经完成了的保存已经完成了的loadload的结果（即从存储的结果（即从存储器取来的数据），等待器取来的数据），等待CDBCDB传输。传输。2022-5-2628storestore缓冲器的缓冲器的作用有作用有3 3个：个：存放用于计算有效地址的分量；存放用于计算有

27、效地址的分量；保存正在进行的保存正在进行的storestore访存的目标地址，访存的目标地址，该该storestore正在等待存储数据的到达；正在等待存储数据的到达；保存该保存该storstore e的地址和数据，直到存储部的地址和数据，直到存储部件接收。件接收。2022-5-2629浮点寄存器浮点寄存器FPFP 共有共有1616个浮点寄存器：个浮点寄存器：F0F0，F2F2，F4F4，F30F30。 它们通过一对总线连接到功能部件，并通过它们通过一对总线连接到功能部件，并通过CDBCDB连接连接到到storestore缓冲器缓冲器。 指令队列指令队列 指令部件送来的指令放入指令队列指令部件送

28、来的指令放入指令队列 指令队列中的指令按先进先出的顺序流出指令队列中的指令按先进先出的顺序流出 运算部件运算部件 浮点加法器完成加法和减法操作浮点加法器完成加法和减法操作 浮点乘法器完成乘法和除法操作浮点乘法器完成乘法和除法操作 2022-5-2630在在TomasuloTomasulo算法中，寄存器换名是通过保留站和流算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。出逻辑来共同完成的。 当指令流出时，如果其操作数还没有计算出来，当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号则将该指令中相应的寄存器号换名为将产生这换名为将产生这个操作数的保留站的标识。个操作数的保留

29、站的标识。 指令流出到保留站后，其操作数寄存器号或者指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数据已经就绪），或换成了数据本身（如果该数据已经就绪），或者换成了保留站的标识，者换成了保留站的标识，不再与寄存器有关系不再与寄存器有关系。 2022-5-2631TomasuloTomasulo算法具有以下算法具有以下两个特点：两个特点： 冲突检测和指令执行控制是分布的。冲突检测和指令执行控制是分布的。 每个功能部件的保留站中的信息决定了什每个功能部件的保留站中的信息决定了什么时候么时候指令可以在该功能部件开始执行。指令可以在该功能部件开始执行。 计算结果通过计算结果通过CDBC

30、DB直接从产生它的保留站传送直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。到所有需要它的功能部件，而不用经过寄存器。2022-5-2632* Tomasulo指令执行的步骤指令执行的步骤使用使用TomasuloTomasulo算法的流水线需算法的流水线需3 3段段： 流出：从指令队列的头部取一条指令。流出：从指令队列的头部取一条指令。如果该指令的操作所要求的保留站有空闲的，如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为就把该指令送到该保留站（设为r r）。）。如果其操作数在寄存器中已经就绪，就将如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站这

31、些操作数送入保留站r r。2022-5-2633如果其操作数还没有就绪，就把将产生该如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站操作数的保留站的标识送入保留站r r。一旦被记录的保留站完成计算，它将直接一旦被记录的保留站完成计算，它将直接把数据送给保留站把数据送给保留站r r。（寄存器换名和对操作数进行缓冲，消除（寄存器换名和对操作数进行缓冲，消除WARWAR冲突）冲突） 完成对目标寄存器的预约工作完成对目标寄存器的预约工作 （消除了（消除了WAWWAW冲突）冲突） 如果没有空闲的保留站，指令就不能流出。如果没有空闲的保留站，指令就不能流出。 （发生了结构冲突）（发生了结

32、构冲突） 2022-5-2634 执行执行 当两个操作数都就绪后，本保留站就用相应的功当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。能部件开始执行指令规定的操作。 loadload和和storestore指令的执行需要两个步骤：指令的执行需要两个步骤：计算有效地址（要等到基地址寄存器就绪）计算有效地址（要等到基地址寄存器就绪）把有效地址放入把有效地址放入loadload或或storestore缓冲器缓冲器 写结果写结果 功能部件计算完毕后，就将计算结果放到功能部件计算完毕后，就将计算结果放到CDBCDB上，上，所有等待该计算结果的寄存器和保留站（包括所有等待该计算结果

33、的寄存器和保留站（包括storestore缓冲器）都同时从缓冲器）都同时从CDBCDB上获得所需要的数据。上获得所需要的数据。 2022-5-2635保留站保留站6 6个字段：个字段：OpOp：要对源操作数进行的操作。要对源操作数进行的操作。QjQj，QkQk：将产生源操作数的保留站号。将产生源操作数的保留站号。等于等于0 0表示操作数已经就绪且在表示操作数已经就绪且在VjVj或或VkVk中，或中，或者不需要操作数。者不需要操作数。VjVj，VkVk：源操作数的值。源操作数的值。对于每一个操作数来说，对于每一个操作数来说，V V或或Q Q字段只有一个字段只有一个有效。有效。对于对于loadlo

34、ad来说，来说，VkVk字段用于保存偏移量。字段用于保存偏移量。2022-5-2636BusyBusy：为为“yesyes”表示本保留站或缓冲单元表示本保留站或缓冲单元“忙忙”。A A：仅仅loadload和和storestore缓冲器有该字段。开始是存缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效放指令中的立即数字段，地址计算后存放有效地址。地址。 QiQi：寄存器状态表。寄存器状态表。 每个寄存器在该表中有对应的一项，用于存每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。放将把结果写入该寄存器的保留站的站号。 为为0 0表示当前没有正在执行的指

35、令要写入该寄表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。存器，也即该寄存器中的内容就绪。2022-5-2637*Tomasulo算法举例例4.1 对于下述指令序列，给出当第一条指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容。 L.DF6,34（R2） L.DF2,45（R3） MUL.DF0,F2,F4 SUB.DF8,F2,F6 DIV.DF10,F0,F6 ADD.DF6,F8,F2 2022-5-2638 当采用当采用Tomasulo算法时，在上述给定的时刻，算法时，在上述给定的时刻， 保留站、保留站、load缓冲器以及寄存器状态表中的内容缓冲器

36、以及寄存器状态表中的内容。 指指 令令 指令状态表指令状态表 流出流出 执行执行 写结果写结果 L.D F6 , 34(R2) L.D F2 , 45(R3) MUL.DF0 , F2 , F4 SUB.D F8 , F6 , F2 DIV.DF10 , F0 , F6 ADD.D F6 , F8 , F2 2022-5-2639名称名称 保留站保留站 Load1Load1Load2Load2Add1Add1Add2Add2Add3Add3Mult1Mult1Mult2Mult2BusyBusy no no yes yes yes yes yes yes no no yes yes yes y

37、esOpOp LD LD SUB SUB ADD ADD MUL MUL DIV DIVVjVj VkVk Mem34+RegsR2 Mem34+RegsR2 RegF4 RegF4 Mem34+RegsR2 Mem34+RegsR2QjQj Load2Load2 Add1 Add1 Load2 Load2 Mult1 Mult1QkQk Load2Load2A A 45+RegsR3 45+RegsR3 寄存器状态表寄存器状态表 F0 F2 F4 F6 F8 F10 F0 F2 F4 F6 F8 F10 F30 F30 Qi Qi Mult1Mult1 Load2 Add2 Load2 Ad

38、d2 Add1 Mult2Add1 Mult2 2022-5-2640例4.2 对于例4.1中的代码，假设各种操作的延迟为： load：1个时钟周期 加法：2个时钟周期 乘法：10个时钟周期 除法：40个时钟周期 给出MUL.D指令准备写结果时各状态表的内容。解 MUL.D指令准备写结果时各状态表的内容如下图所示。2022-5-2641指指 令令 指令状态表指令状态表 流出流出 执行执行 写结果写结果L.D F6 , 34(R2) L.D F2 , 45(R3) MUL.D F0 , F2 , F4 SUB.D F8 , F6 , F2 DIV.D F10, F0, F6 ADD.D F6 ,

39、 F8 , F2 2022-5-2642 具体算法（略，具体算法（略，P123）名称名称 保留站保留站 Load1Load1Load2Load2Add1Add1Add2Add2Add3Add3Mult1Mult1Mult2Mult2BusyBusy no no yes yes yes yes yes yes no no yes yes yes yesOpOp MulMul DIV DIV VjVjMem45+RegsR3Mem45+RegsR3 VkVk RegF4 RegF4 Mem34+RegsR2Mem34+RegsR2QjQj Mult1Mult1QkQk A A 寄存器状态表寄存器状

40、态表 F0 F2 F4 F6 F8 F10 F0 F2 F4 F6 F8 F10 F30 F30 Qi Qi Mult1Mult1 Mult2Mult2 2022-5-26434.3 4.3 动态硬件预测转移方法动态硬件预测转移方法( (简略简略) ) 4.3.1 BHT (4.3.1 BHT (分支历史表，略分支历史表，略) ) 4.3.2 4.3.2 转移目标缓冲器转移目标缓冲器 动态硬件预测转移动态硬件预测转移 借助硬件在程序运行时动态地预测转移方向。借助硬件在程序运行时动态地预测转移方向。 方法：方法： 将过去发生过的转移指令地址以及它的转移目标将过去发生过的转移指令地址以及它的转移目

41、标地址存入一个转移目标缓冲器（地址存入一个转移目标缓冲器（BTB）中，利用）中，利用转移指令地址作为检测标志，以便尽早生成转移转移指令地址作为检测标志，以便尽早生成转移目标地址目标地址。2022-5-2644转移目标缓冲器的基本结构和工作原理转移目标缓冲器的基本结构和工作原理 预取指令的预取指令的PC =是是否否查找查找预测预测PC值值转移发生转移发生 预测预测PC值应值应送入送入PC中中预测转移发生或不发生预测转移发生或不发生转移不发生，按正常转移不发生，按正常顺序进行顺序进行（2位状态位）2022-5-2645记录转移历史信息的三种方法记录转移历史信息的三种方法 方法一：在指令方法一：在指

42、令Cache中记录转移历史信息中记录转移历史信息在指令在指令Cache中专门设置一个字段，称为中专门设置一个字段，称为“转转移历史表移历史表”。在执行转移指令时，把转移成功或。在执行转移指令时，把转移成功或不成功的信息记录在这个不成功的信息记录在这个“转移历史表转移历史表”中。可中。可以只用一个二进制位来记录最近一次转移是否成以只用一个二进制位来记录最近一次转移是否成功的信息，也可以用多个二进制位来记录最近几功的信息，也可以用多个二进制位来记录最近几次转移是否成功的信息。当下次再执行到这条指次转移是否成功的信息。当下次再执行到这条指令时，转移预测逻辑根据令时，转移预测逻辑根据“转移历史表转移历

43、史表”中记录中记录的信息预测转移成功或不成功。的信息预测转移成功或不成功。2022-5-2646 方法二，转移目标地址缓冲栈方法二，转移目标地址缓冲栈用一个小容量的高速缓冲栈保存最近执行的用一个小容量的高速缓冲栈保存最近执行的k条转移指令的条转移指令的“转移历史表转移历史表”和转移目标地址。和转移目标地址。“转移指令地址转移指令地址”字段采用全相联方式访问。当字段采用全相联方式访问。当程序中执行到一条转移指令时，把当前指令地址程序中执行到一条转移指令时，把当前指令地址与转移目标缓冲栈中的所有转移指令地址进行比与转移目标缓冲栈中的所有转移指令地址进行比较；如果发现有相等的，则根据同一行中的较；如

44、果发现有相等的，则根据同一行中的“转转移历史表移历史表”所记录的历史信息预测本次转移的方所记录的历史信息预测本次转移的方向，同时用转移目标地址预取指令。在实际转移向，同时用转移目标地址预取指令。在实际转移条件形成之后，可以根据某一种规则修改条件形成之后，可以根据某一种规则修改“转移转移历史表历史表”。2022-5-26472022-5-2648 方法三，转移目标指令缓冲栈方法三，转移目标指令缓冲栈当转移指令在指令分析部件中译码时，转移不当转移指令在指令分析部件中译码时，转移不成功方向上的指令已经被预取到先行指令缓冲栈成功方向上的指令已经被预取到先行指令缓冲栈中，或者已经存放在指令中，或者已经存

45、放在指令Cache中，为了能够在转中，为了能够在转移成功方向上也预取一部分指令，可以把转移目移成功方向上也预取一部分指令，可以把转移目标地址部分改为存放转移目标地址之后的标地址部分改为存放转移目标地址之后的n条指令。条指令。设置转移目标指令缓冲栈的转移预测方法的工作设置转移目标指令缓冲栈的转移预测方法的工作原理，预测转移方向的规则和修改原理，预测转移方向的规则和修改“转移历史表转移历史表”的方法与方法二相同。的方法与方法二相同。2022-5-26492022-5-26504.3.3 基于硬件的前瞻执行前瞻执行前瞻执行（speculationspeculation）的基本思想：的基本思想： 对分

46、支指令的结果进行猜测，并假设对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，行指令的结果不是写回到寄存器或存储器，而是放到一个称为而是放到一个称为ROBROB（ReOrderReOrder Buffer Buffer）的缓冲器中。等到相应的指令得到的缓冲器中。等到相应的指令得到“确认确认”（commitcommit）（即确实是应该执行的）之后，（即确实是应该执行的）之后，才将结果写入寄存器或存储器。才将结果写入寄存器或存储器。 2

47、022-5-2651 1. 基于硬件的前瞻执行结合了基于硬件的前瞻执行结合了三种思想：三种思想： 动态分支预测。用来选择后续执行的指令。动态分支预测。用来选择后续执行的指令。 在控制相关的结果尚未出来之前，前瞻地执行后续指令。在控制相关的结果尚未出来之前，前瞻地执行后续指令。 用动态调度对基本块的各种组合进行跨基本块的调度。用动态调度对基本块的各种组合进行跨基本块的调度。 2. 2. 对对TomasuloTomasulo算法加以扩充，就可以支持前瞻执算法加以扩充，就可以支持前瞻执行。行。 把把TomasuloTomasulo算法的写结果和指令完成加以区分，分成算法的写结果和指令完成加以区分，分

48、成两个不同的段：两个不同的段： 写结果写结果，指令确认指令确认 2022-5-2652 写结果段写结果段 把前瞻执行的结果写到把前瞻执行的结果写到ROBROB中；中； 通过通过CDBCDB在指令之间传送结果，供需要用到这些结果在指令之间传送结果，供需要用到这些结果的指令使用。的指令使用。 指令确认段指令确认段 在分支指令的结果出来后，对相应指令的前瞻执在分支指令的结果出来后，对相应指令的前瞻执行给予确认。行给予确认。 如果前面所做的猜测是对的，把在如果前面所做的猜测是对的，把在ROBROB中的结果写到中的结果写到寄存器或存储器。寄存器或存储器。 如果发现前面对分支结果的猜测是错误的，那就不予如

49、果发现前面对分支结果的猜测是错误的，那就不予以确认，并从那条分支指令的另一条路径开始重新执以确认，并从那条分支指令的另一条路径开始重新执行。行。 2022-5-2653 3. 实现前瞻的实现前瞻的关键思想：关键思想： 允许指令乱序执行，但必须顺序确认。允许指令乱序执行，但必须顺序确认。 4. 支持前瞻执行的浮点部件的结构支持前瞻执行的浮点部件的结构 2022-5-2654 从从指指令令部部件件来来 浮浮点点寄寄存存器器 FP 地地址址部部件件 load/store 操操作作 浮浮点点操操作作 操操作作数数总总线线 操操作作总总线线 store数数据据 1 1 存存储储部部件件 浮浮点点加加法法

50、器器 浮浮点点乘乘法法器器 指指令令队队列列 地地址址 2 3 2 3 4 5 6 公公共共数数据据总总线线（CDB） 1 2 保保留留站站 ROB 数数据据 寄寄存存器器号号 缓缓冲冲器器 load store地地址址 保保留留站站 load 数数据据 2022-5-2655ROBROB中的每一项由以下中的每一项由以下4 4个字段组成：个字段组成： 指令类型指令类型 指出该指令是分支指令、指出该指令是分支指令、storestore指令或寄存器操作指令。指令或寄存器操作指令。 目标地址目标地址 给出指令执行结果应写入的目标寄存器号（如果是给出指令执行结果应写入的目标寄存器号（如果是 loadl

51、oad和和ALUALU指令）或存储器单元的地址（如果是指令）或存储器单元的地址（如果是storestore指指 令）。令）。 数据值字段数据值字段 用来保存指令前瞻执行的结果，直到指令得到确认。用来保存指令前瞻执行的结果，直到指令得到确认。 就绪字段就绪字段 指出指令是否已经完成执行并且数据已就绪。指出指令是否已经完成执行并且数据已就绪。 TomasuloTomasulo算法中保留站的换名功能是由算法中保留站的换名功能是由ROBROB来完成来完成的。的。2022-5-26565. 采用前瞻执行机制后，指令的执行步骤：采用前瞻执行机制后，指令的执行步骤： 流出流出 从浮点指令队列的头部取一条指令

52、。从浮点指令队列的头部取一条指令。 如果有空闲的保留站（设为如果有空闲的保留站（设为r r）且有空闲的）且有空闲的ROBROB项（设项（设为为b b），就流出该指令，并把相应的信息放入保留站），就流出该指令，并把相应的信息放入保留站r r和和ROBROB项项b b。 如果保留站或如果保留站或ROBROB全满，便停止流出指令，直到它们全满，便停止流出指令，直到它们都有空闲的项。都有空闲的项。 执行执行 如果有操作数尚未就绪，就等待，并不断地监测如果有操作数尚未就绪，就等待，并不断地监测CDBCDB。 ( (检测检测RAWRAW冲突冲突) ) 当两个操作数都已在保留站中就绪后，就可以执行该当两个操

53、作数都已在保留站中就绪后，就可以执行该指令的操作。指令的操作。2022-5-2657 写结果写结果 当结果产生后，将该结果连同本指令在流出段所分配当结果产生后，将该结果连同本指令在流出段所分配到的到的ROBROB项的编号放到项的编号放到CDBCDB上，经上，经CDBCDB写到写到ROBROB以及所有以及所有等待该结果的保留站。等待该结果的保留站。 释放产生该结果的保留站。释放产生该结果的保留站。 storestore指令指令在本阶段完成，其操作为在本阶段完成，其操作为: : 如果要写入存储器的数据已经就绪，就把该数据如果要写入存储器的数据已经就绪，就把该数据写入分配给该写入分配给该stores

54、tore指令的指令的ROBROB项。项。否则，就监测否则，就监测CDBCDB，直到那个数据在，直到那个数据在CDBCDB上播送出上播送出来，这时才将之写入分配给该来，这时才将之写入分配给该storestore指令的指令的ROBROB项项。2022-5-2658 确认确认 对对分支指令、分支指令、store指令指令以及以及其他指令其他指令的处理不同：的处理不同： 其他指令其他指令（除分支指令和除分支指令和storestore指令）指令） 当该指令到达当该指令到达ROBROB队列的头部而且其结果队列的头部而且其结果已经就绪时，就把该结果写入该指令的目标已经就绪时，就把该结果写入该指令的目标寄存器，

55、并从寄存器，并从ROBROB中删除该指令。中删除该指令。 2022-5-2659storestore指令指令 处理与上面类似，只是它把结果写入存储处理与上面类似，只是它把结果写入存储器。器。 分支指令分支指令 当预测错误的分支指令到达当预测错误的分支指令到达ROBROB队列的头队列的头部时，清空部时，清空ROBROB，并从分支指令的另一个，并从分支指令的另一个分支重新开始执行。分支重新开始执行。（错误的前瞻执行）（错误的前瞻执行）当预测正确的分支指令到达当预测正确的分支指令到达ROBROB队列的头队列的头部时，该指令执行完毕。部时，该指令执行完毕。 2022-5-2660例4.3 假设浮点功能

56、部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出当指令MUL.D即将确认时的状态表内容。 L.DF6,34（R2） L.DF2,45（R3） MUL.D F0,F2,F4 SUB.D F8,F6,F2 DIV.D F10,F0,F6 ADD.D F6,F8,F22022-5-2661前瞻执行中MUL.D确认前，保留站和ROB的状态名称 保留站 Busy Op Vj Vk Qj Qk Dest A Add1 no Add2 no Add3 no Mult1 no MUL Mem45+ RegsR2 RegsF4 #3 Mult2 yes DIV

57、Mem34+RegsR2 #3 #5 2022-5-2662项号 ROB Busy 指令 状态 目的 Value 1 no L.D F6, 34（R2） 确认 F6 Mem34+RegsR2 2no L.D F2, 45（R3） 确认 F2 Mem45+RegsR3 3yes MUL.D F0, F2, F4 写结果 F0 #2 RegsF4 4yes SUB.D F8, F6, F2 写结果 F8 #1#2 5yes DIV.D F10, F0, F6 执行 F10 6yes ADD.D F6,F8,F2 写结果 F6 #4#2 字段 浮点寄存器状态 F0 F2 F4 F6 F8 F10 F

58、30 ROB项编号项编号 3645Busy yes no no yes yes yes no2022-5-2663 6. 6. 前瞻执行前瞻执行通过通过ROBROB实现了指令的实现了指令的顺序完成。顺序完成。 能够能够实现精确异常。实现精确异常。 很容易地推广到整数寄存器和整数功能单很容易地推广到整数寄存器和整数功能单元上。元上。 主要缺点：主要缺点：所需的硬件太复杂。所需的硬件太复杂。 2022-5-26644.4 4.4 优化流水的软件技术优化流水的软件技术 4.4.1 循环体展开后调度循环体展开后调度 方法：方法： 通过优化编译技术，将欲执行的循环体展开多次。通过优化编译技术，将欲执行的

59、循环体展开多次。 例如：例如： for ( i=0;i1000;i+) Xi=Xi+S ; /X浮点向量，浮点向量，S浮点标量浮点标量 编译成：编译成：(RISC型机器指令型机器指令)2022-5-2665 loop: load f0, 0(r1); f0 Memr1+0 fadd f0, f0, f1; f0 f0+f1 ,S预先存入预先存入 f1 store f0, 0(r1); Memr1+0 f0 addi r1, r1, 4; r1 r1+4 , 单精度单精度 subicc r2, r2, 1; r2 r2-1 , r2初值初值=1000 bnez loop 下面以不同的处理技术讨论

60、该循环及展开的执行下面以不同的处理技术讨论该循环及展开的执行时间时间 。原始循环2022-5-26661. 仅考虑内部定向的运行情况仅考虑内部定向的运行情况load IF ID EX Mem WBfadd stall IF ID EX1 EX2 EX3 Mem WBstore stall IF ID EX Mem WBaddi IF ID EX Mem WBsubicc IF ID EX Mem WBbnez stall IF ID EX Memload stall IF ID 一次循环时间为10个周期时间槽 n=1冲突冲突2022-5-26672. 考虑重组和延迟转移等的运行情况考虑重组和延