第4章 指令级并行 曲冠南 qugnStu@live.com http://cc.jlu.edu.cn/ComputerArchitecture.html.

Presentation on theme: "第4章 指令级并行 曲冠南 qugnStu@live.com http://cc.jlu.edu.cn/ComputerArchitecture.html."— Presentation transcript:

1 第4章 指令级并行 曲冠南 qugnStu@live.com

2 小节 章节名 主要内容 4.1 指令级并行的概念 4.2 指令的动态调度 4.3 动态分支预测技术 4.4 多指令流出技术 4.5
4.1  指令级并行的概念 指令级并行  4.2  指令的动态调度 动态调度思想，Tomasulo算法  4.3  动态分支预测技术 什么是动态分支预测，分支历史表，分支目标缓冲器，基于硬件的前瞻技术  4.4  多指令流出技术 自学  4.5 循环展开和指令调度

3 4.1 指令级并行 4.1.1 指令级并行的概念 几乎所有的处理机都利用流水线来使指令重叠并行执行，以达到提高性能的目的。这种指令之间存在的潜在并行性称为指令级并行。 （ILP：Instruction-Level Parallelism） 开发指令级并行的方法： 静态方法—软件 动态方法—硬件

4 理想流水线的CPI加上各类停顿的时钟周期数：
4.1 指令级并行 目标 – 降低流水线处理机的实际CPI 理想流水线的CPI加上各类停顿的时钟周期数： CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 理想CPI是衡量流水线最高性能的一个指标。 概念 -- 基本程序块 基本程序块：一段除了入口和出口以外不包含其他分支的线性代码段。 程序平均每5～7条指令就会有一个分支。 跨基本块开发指令级并行

5 方法1 — 从循环入手：使一个循环中的不同循环体并行执行。 开发循环体中存在的并行性 是指令级并行研究的重点之一 例如，考虑下述语句：
4.1 指令级并行 方法1 — 从循环入手：使一个循环中的不同循环体并行执行。 开发循环体中存在的并行性 是指令级并行研究的重点之一 例如，考虑下述语句： for （i=1； i<=500； i=i＋1） a[i]=a[i]＋s； 每一次循环都可以与其他的循环重叠并行执行； 在每一次循环的内部，却没有任何的并行性。 最基本的开发循环级并行的技术 循环展开（loop unrolling）技术 采用向量指令和向量数据表示

6 尽可能开发并行性，在影响程序正确性的情况下保持程序顺序。
4.1 指令级并行 方法2 – 从相关与流水线冲突入手 相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系；具体的一次相关是否会导致实际冲突的发生，以及该冲突会带来多长的停顿，则是流水线的属性。 可以从两个方面来解决相关问题： 保持相关，但避免发生冲突 ，如 指令调度 通过代码变换，消除相关 ，如 换名技术 尽可能开发并行性，在影响程序正确性的情况下保持程序顺序。 程序顺序：由源程序确定的在完全串行方式下指令的执行顺序。

7 对于控制相关 -- 并不是一个必须严格保持的关键属性。
4.1 指令级并行 对于控制相关 -- 并不是一个必须严格保持的关键属性。 -- 主要在于执行不该执行的指令会不会对 程序正确性产生影响。 重点：对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为。 保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。 即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。 上述条件经常被弱化为：指令执行顺序的改变不能导致程序中发生新的异常。 如果我们能做到保持程序的数据相关和控制相关，就能保持程序的数据流和异常行为。

8 如果把DADDU调度到BEQZ之后，程序结果就会改变。
4.1 指令级并行 例1： DADDU R2，R3，R4 BEQZ R2，L1 //R2==0， 跳到L1. LW R1，0（R2） L1 ：。。。 如果把DADDU调度到BEQZ之后，程序结果就会改变。 如果LW调度到BEQZ之前，可能会导致访存保护异常。

9 数据流：指数据值从其产生者指令到其消费者指令的实际流动。
4.1 指令级并行 数据流：指数据值从其产生者指令到其消费者指令的实际流动。 分支指令使得数据流具有动态性，因为它使得给定指令的数据可以有多个来源。 仅仅保持数据相关性是不够的，只有再加上保持控制顺序，才能够保持程序顺序。 数据相关+实际控制顺序 = 数据流

10 4.1 指令级并行 例2： DADDU R1，R2，R3 BEQZ R4，L1 DSUBU R1，R5，R6 L1 ：… OR R7，R1，R8

11 有时，不遵守控制相关既不影响异常行为，也不改变数据流。可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。
4.1 指令级并行 有时，不遵守控制相关既不影响异常行为，也不改变数据流。可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。 举例： DADDU R1，R2，R3 BEQZ R12，Skipnext DSUBU R4，R5，R6 DADDU R5，R4，R9 Skipnext：OR R7，R8，R9

12 4.2 指令的动态调度 静态调度 动态调度 依靠编译器对代码进行静态调度，以减少相关和冲突。
它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。 通过把相关的指令拉开距离来减少可能产生的停顿。 动态调度 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。

13 4.2 指令的动态调度 优点： 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器； 能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。 以硬件复杂性的显著增加为代价

14 4.2.1 动态调度的基本思想 到目前为止我们所使用流水线的最大的局限性: 指令必须按序流出和执行 考虑下面一段代码：
4.2 指令的动态调度 4.2.1 动态调度的基本思想 到目前为止我们所使用流水线的最大的局限性: 指令必须按序流出和执行 考虑下面一段代码： DIV.D F4，F0，F2 SUB.D F10，F4，F6 ADD.D F12，F6，F14 SUB.D指令与DIV.D指令关于F4相关，导致 流水线停顿。 ADD.D指令与流水线中的任何指令都没有关 系，但也因此受阻。

15 ID 不采用动态调度： 检测结构冲突 检测数据冲突 一旦一条指令受阻，其后的指令都将停顿。 解决办法：允许无冲突的指令先执行
4.2 指令的动态调度 不采用动态调度： ID 检测结构冲突 检测数据冲突 一旦一条指令受阻，其后的指令都将停顿。 解决办法：允许无冲突的指令先执行

16 RO IS 为了允许乱序执行，我们将5段流水线的译码阶段再分为两个阶段：
4.2 指令的动态调度 为了允许乱序执行，我们将5段流水线的译码阶段再分为两个阶段： 流出（Issue，IS）：指令译码，检查是否存在结构冲突。如果不存在结构冲突，则流出。 读操作数（Read Operands，RO）：等待数据冲突消失，然后读操作数。 IS RO 检测结构冲突 检测数据冲突 顺序流出, 乱序执行

17 在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。 例如，考虑下面的代码
4.2 指令的动态调度 在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。 例如，考虑下面的代码 DIV.D F10, F0, F2 SUB.D F10, F4, F6 ADD.D F6, F8, F14 存在输出相关 存在反相关 Tomasulo算法可以通过使用寄存器重命名来消除。

18 动态调度的流水线支持多条指令同时处于执行当中。 要求：具有多个功能部件、或者流水功能部件、或者兼而有之。
4.2 指令的动态调度 动态调度的流水线支持多条指令同时处于执行当中。 要求：具有多个功能部件、或者流水功能部件、或者兼而有之。 我们假设具有多个功能部件。 指令乱序完成带来的最大问题 - 异常处理比较复杂 动态调度要保持正确的异常行为，即只有那些在程序严格按程序顺序执行时会发生的异常，才能真正发生。 如何保持正确的异常行为？对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行后，才允许它产生异常。 即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。

19 不精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。
4.2 指令的动态调度 不精确异常：当执行指令i导致发生异常时，处理机的现场（状态）与严格按程序顺序执行时指令i的现场不同。 发生不精确异常的原因： 因为当发生异常（设为指令i）时： 流水线可能已经执行完按程序顺序是位于指令i之后的指令； 流水线可能还没完成按程序顺序是指令i之前的指令。 不精确异常使得在异常处理后难以接着继续执行程序。 精确异常：如果发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场相同。

20 4.2.2 Tomasulo算法 Tomasulo算法基本思想 1. 核心思想
4.2 指令的动态调度 4.2.2 Tomasulo算法 Tomasulo算法基本思想 1. 核心思想 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减少到最小； 通过寄存器换名来消除WAR冲突和WAW冲突。

21 2. 寄存器换名可以消除WAR冲突和WAW冲突。 考虑以下代码：
4.2 指令的动态调度 2. 寄存器换名可以消除WAR冲突和WAW冲突。 考虑以下代码： DIV.D F0，F2，F4 ADD.D F6，F0，F8 S.D F6，0（R1） SUB.D F8，F10，F14 MUL.D F6， F10，F8 输出相关（F6） 导致WAW冲突 反相关（F8） 导致WAR冲突

22 3. 基于Tomasulo算法的MIPS处理器浮点部件的基本结构
4.2 指令的动态调度 消除名相关 引入两个临时寄存器S和T 把这段代码改写为： DIV.D F0，F2，F4 ADD.D S，F0，F8 S.D S，0（R1） SUB.D T，F10，F14 MUL.D F6，F10，T 两个F6都换名为S 两个F8都换名为T 3. 基于Tomasulo算法的MIPS处理器浮点部件的基本结构

23 思考： 1. Tomasulo算法如何通过寄存器换名技术消除名相关？ 2. 对目标寄存器多次预约的结果是？

24 4.2 指令的动态调度

25 保留站（reservation station）
4.2 指令的动态调度 保留站（reservation station） 每个保留站中保存一条已经流出并等待到本功能部件执行 的指令（相关信息）。 包括：操作码、操作数以及用于检测和解决冲突的信息。 在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则将之取到该保留站中。 如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识。 浮点加法器有3个保留站：ADD1，ADD2，ADD3 浮点乘法器有两个保留站：MULT1，MULT2 每个保留站都有一个标识字段，唯一地标识了该保留站。

26 公共数据总线CDB load缓冲器和store缓冲器 4.2 指令的动态调度 （一条重要的数据通路）
存放读/写存储器的数据或地址 load缓冲器的作用有3个： 存放用于计算有效地址的分量； 记录正在进行的load访存，等待存储器的响应； 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。

27 浮点寄存器FP 指令队列 4.2 指令的动态调度 store缓冲器的作用有3个： 存放用于计算有效地址的分量；
保存正在进行的store访存的目标地址，该store正在等待存储数据的到达； 保存该store的地址和数据，直到存储部件接收。 浮点寄存器FP 共有16个浮点寄存器：F0，F2，F4，…，F30。 它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。 指令队列 指令部件送来的指令放入指令队列 指令队列中的指令按先进先出的顺序流出

28 4. 在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。
4.2 指令的动态调度 运算部件 浮点加法器完成加法和减法操作 浮点乘法器完成乘法和除法操作 4. 在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。 当指令流出时，如果该数据已经就绪，则将指令中的相应的寄存器号换成数据本身。 当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存器号换名为将产生这个操作数的保留站的标识。 由此，消除名相关。

29 5. 指令执行的步骤 使用Tomasulo算法的流水线需3段： 流出：从指令队列的头部取一条指令。 4.2 指令的动态调度
如果没有空闲的保留站，指令就不能流出。 （发生了结构冲突） 如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为r）。 （寄存器换名和对操作数进行缓冲，消除WAR冲突） 完成对目标寄存器的预约工作 （消除了WAW冲突） 参考新教材中的图4.2例子

30 执行 写结果 4.2 指令的动态调度 当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。
load和store指令的执行需要两个步骤： 计算有效地址（要等到基地址寄存器就绪） 把有效地址放入load或store缓冲器 写结果 功能部件计算完毕后，就将计算结果放到CDB上，所有等待该计算结果的寄存器和保留站（包括store缓冲器）都同时从CDB上获得所需要的数据。

31 Busy：为“yes”表示本保留站或缓冲单元“忙”。
4.2 指令的动态调度 6. 每个保留站有以下6个字段： Op：要对源操作数进行的操作。 Qj，Qk：将产生源操作数的保留站号。 等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。 Vj，Vk：源操作数的值。 对于每一个操作数来说，V或Q字段只有一个有效。 对于load来说，Vk字段用于保存偏移量。 Busy：为“yes”表示本保留站或缓冲单元“忙”。 A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段，地址计算后存放有效地址。

32 Qi：寄存器状态表。 4.2 指令的动态调度 每个寄存器在该表中有对应的一项，用于存放将把结果写入该寄存器的保留站的站号。
为0表示当前没有正在执行的指令要写入该寄存器，也即该寄存器中的内容就绪。

33 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。
4.2 指令的动态调度 7. Tomasulo算法具有如下特点： 冲突检测逻辑是分布的 （通过保留站和CDB实现） 如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个结果一产生，就可以通过CDB同时播送给所有这些指令，使它们可以同时执行。 消除了WAW冲突和WAR冲突导致的停顿 使用保留站进行寄存器换名，并且操作数一旦就 绪就将之放入保留站。 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。

34 r：分配给当前指令的保留站或者缓冲器单元编号； rd：目标寄存器编号； rs、rt：操作数寄存器编号； imm：符号扩展后的立即数；
4.2 指令的动态调度 Tomasulo具体算法 各符号的意义 r：分配给当前指令的保留站或者缓冲器单元编号； rd：目标寄存器编号； rs、rt：操作数寄存器编号； imm：符号扩展后的立即数； RS：保留站； result：浮点部件或load缓冲器返回的结果； Qi：寄存器状态表； Regs[ ]：寄存器组；

35 Qi、Qj、Qk的内容或者为0，或者是一个大于0的整数。
4.2 指令的动态调度 与rs对应的保留站字段：Vj，Qj 与rt对应的保留站字段：Vk，Qk Qi、Qj、Qk的内容或者为0，或者是一个大于0的整数。 Qi为0表示相应寄存器中的数据就绪。 Qj、Qk为0表示保留站或缓冲器单元中的Vj或Vk字 段中的数据就绪。 当它们为正整数时，表示相应的寄存器、保留站或 缓冲器单元正在等待结果。

36 rs rd rt j k i rs rt j k rs rt j k 符号说明： （举例） MUL.D F4，F0，F2
4.2 指令的动态调度 符号说明： （举例） MUL.D F4，F0，F2 rs rd rt j k i L.D F2，45（R3） rs rt imm j k S.D F3, 40（R4） rs rt imm j k

37 rs rd rt j k MUL.D F4，F0，F2 指令流出 浮点运算指令 进入条件：有空闲保留站（设为r） 操作和状态表内容修改：
if （Qi[rs] = 0） // 检测第一操作数是否就绪  RS[r].Vj  Regs[rs]； // 第一操作数就绪。把寄存器rs // 中的操作数取到当前保留站的Vj。 RS[r].Qj  0 ； // 置Qj为0，表示当前保留站的Vj // 中的操作数就绪。 else // 第一操作数没有就绪  RS[r].Qj  Qi[rs]  // 进行寄存器换名，即把将产生该 // 操作数的保留站的编号放入当前保留站的Qj。 注意检测 寄存器 状态表

38 if （Qi[rt] = 0） // 检测第二操作数是否就绪
 RS[r].Vk  Regs[rt]； // 第二操作数就绪。把寄存器rt中的 // 操作数取到当前保留站的Vk。 RS[r].Qk  0  // 置Qk为0，表示当前保留站的Vk中的 // 操作数就绪。 else //第二操作数没有就绪  RS[r].Qk  Qi[rt]  //进行寄存器换名，即把将产生该操作 // 数的保留站的编号放入当前保留站的Qk。 RS[r].Busy  yes； //置当前保留站为“忙” RS[r].Op  Op； //设置操作码 Qi[rd]  r； // 把当前保留站的编号r放入rd所对应 // 的寄存器状态表项，以便rd将来接收结果。 注意 寄存器 预约

39 rs rt j k L.D F2，45（R3） imm load和store指令 进入条件：缓冲器有空闲单元（设为r）
操作和状态表内容修改： if （Qi[rs] = 0） // 检测第一操作数是否就绪 RS[r].Vj  Regs[rs]； // 第一操作数就绪，把寄存器rs中的 // 操作数取到当前缓冲器单元的Vj RS[r].Qj  0 ； // 置Qj为0，表示当前缓冲器单元的Vj // 中的操作数就绪。 else // 第一操作数没有就绪 RS[r].Qj  Qi[rs]  // 进行寄存器换名，即把将产生该 // 操作数的保留站的编号存入当前缓冲器单元的Qj。

40 rs rt j k L.D F2，45（R3） imm RS[r].Busy  yes； // 置当前缓冲器单元为“忙”
RS[r].A  Imm； // 把符号位扩展后的偏移量放入 // 当前缓冲器单元的A 对于load指令： Qi[rt]  r； // 把当前缓冲器单元的编号r放入 // load指令的目标寄存器rt所对应的寄存器 // 状态表项，以便rt将来接收所取的数据。 寄存器 预约

41 RS[r].Vk  Regs[rt]； // 该数据就绪，把它从寄存器rt取到
S.D F3, 40（R4） rs rt imm j k 对于store指令： if （Qi[rt] = 0） // 检测要存储的数据是否就绪 RS[r].Vk  Regs[rt]； // 该数据就绪，把它从寄存器rt取到 // store缓冲器单元的Vk RS[r].Qk  0 ； // 置Qk为0，表示当前缓冲器单元的Vk // 中的数据就绪。 else // 该数据没有就绪 RS[r].Qk  Qi[rt]  // 进行寄存器换名，即把将产生该数 据的保留站的编号放入当前缓冲器单元的Qk。

42 执行 浮点操作指令 进入条件：（RS[r].Qj = 0）且（RS[r].Qk= 0）； // 两个源操作数就绪 操作和状态表内容修改：进行计算，产生结果 。 load/store指令 进入条件：（RS[r].Qj = 0）且r成为load/store 缓冲队列的头部 操作和状态表内容修改： RS[r].A  RS[r].Vj + RS[r].A； //计算有效地址 对于load指令，在完成有效地址计算后，还要进行： 从Mem[RS[r].A]读取数据； //从存储器中读取数据

43 进入条件：保留站r执行结束，且CDB就绪。 操作和状态表内容修改： x （if（Qi[x] = r） // 对于任何一个正在等该结果
写结果 浮点运算指令和load指令 进入条件：保留站r执行结束，且CDB就绪。 操作和状态表内容修改： x （if（Qi[x] = r） // 对于任何一个正在等该结果 // 的浮点寄存器x  Regs[x]  result； // 向该寄存器写入结果 Qi[x]  0 ； // 把该寄存器的状态置为数据就绪 x （if（RS[x].Qj = r） // 对于任何一个正在等该结果 // 作为第一操作数的保留站x RS[x].Vj  result； // 向该保留站的Vj写入结果 RS[x].Qj  0 ； // 置Qj为0，表示该保留站的 // Vj中的操作数就绪

44 x （if（RS[x].Qk = r） // 对于任何一个正在等该结果作为
RS[x].Vk  result； // 向该保留站的Vk写入结果 RS[x].Qk  0 ； // 置Qk为0，表示该保留站的Vk中的 // 操作数就绪。 RS[r].Busy  no； // 释放当前保留站，将之置为空闲状态。 store指令 进入条件：保留站r执行结束，且RS[r].Qk = 0 // 要存储的数据已经就绪 操作和状态表内容修改： Mem[RS[r].A]  RS[r].Vk // 数据写入存储器，地址由store // 缓冲器单元的A字段给出。 RS[r].Busy  no； //释放当前缓冲器单元，将之置为空闲状态。 注意store的 进入条件。 也就是store执行 时不需要存储的 数据就绪

45 例4.1 对于下述指令序列，给出当第一条指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容。
4.2 指令的动态调度 例4.1 对于下述指令序列，给出当第一条指令完成并写入结果时，Tomasulo算法所用的各信息表中的内容。 L.D F6,34（R2） L.D F2,45（R3） MUL.D F0,F2,F4 SUB.D F8,F2,F6 DIV.D F10,F0,F6 ADD.D F6,F8,F2

46 流出 执行 写结果 指 令 L.D F6 , 34(R2) √ √ √ L.D F2 , 45(R3) √ √
4.2 指令的动态调度 当采用Tomasulo算法时，在上述给定的时刻， 保留站、load缓冲器以及寄存器状态表中的内容。 指 令 指令状态表 流出 执行 写结果 L.D F6 , 34(R2) √ √ √ L.D F2 , 45(R3) √ √ MUL.D F0 , F2 , F √ SUB.D F8 , F2 , F √ DIV.D F10 , F0 , F √ ADD.D F6 , F8 , F √

47 Qi Mult1 Load2 Add2 Add1 Mult2 …
保留站 名称 Vj Busy no yes Op LD SUB ADD MUL DIV Vk Mem[34+Regs[R2]] Reg[F4] Qj Load2 Add1 Mult1 Qk Load2 A 45+Regs[R3] Load1 Load2 Add1 Add2 Add3 Mult1 Mult2 寄存器状态表 F0 F2 F4 F6 F8 F10 … F30 Qi Mult1 Load Add2 Add1 Mult2 …

48 4.2 指令的动态调度 例4.2 对于例4.1中的代码，假设各种操作的延迟为： load：1个时钟周期 加法：2个时钟周期 乘法：10个时钟周期 除法：40个时钟周期 给出MUL.D指令准备写结果时各状态表的内容。 解 MUL.D指令准备写结果时各状态表的内容如下图所示。

49 流出 执行 写结果 指 令 L.D F6 , 34(R2) √ √ √ L.D F2 , 45(R3) √ √ √
4.2 指令的动态调度 指令状态表 流出 执行 写结果 指 令 L.D F6 , 34(R2) √ √ √ L.D F2 , 45(R3) √ √ √ MUL.D F0 , F2 , F √ √ SUB.D F8 , F6 , F √ √ √ DIV.D F10, F0, F √ ADD.D F6 , F8 , F √ √ √

50 名称 F0 F2 F4 F6 F8 F10 … F30 Qi Mult1 Mult2 … Vj Mem[45+Regs[R3]] Busy
保留站 名称 Vj Mem[45+Regs[R3]] Busy no yes Op Mul DIV Vk Reg[F4] Mem[34+Regs[R2]] Qj Mult1 Qk A Load1 Load2 Add1 Add2 Add3 Mult1 Mult2 寄存器状态表 F0 F2 F4 F6 F8 F10 … F30 Qi Mult Mult2 …

51 注意事项 1. 所有类型指令的进入条件和每阶段结束时状态，特别是load和store指令； 2
注意事项 1. 所有类型指令的进入条件和每阶段结束时状态，特别是load和store指令； 2. load指令在执行阶段访存，而store指令在写结果阶段访存； 3. 算法对指令的执行有限制：如果流水线中还有分支指令没有执行，当前指令就不能进入“执行”阶段，为了保证正确的异常行为。

52 4.3 动态分支预测技术 1. 分支预测的重要性 所开发的ILP越多，控制相关的制约就越大，分支预测就要有更高的准确度。
例如：本节中介绍的方法对于每个时钟周期流出多条指令（若为n条，就称为n流出）的处理机来说非常重要。 因为： 在n-流出的处理机中，遇到分支指令的可能性增加了n倍。要给处理器连续提供指令，就需要预测分支的结果； Amdahl定律告诉我们，机器的CPI越小，控制停顿的相对影响就更大。

53 动态分支预测：在程序运行时，根据分支指令过去的表现来预测其将来的行为。
4.3 动态分支预测技术 2. 什么是动态分支预测？为什么动态分支预测 静态分支预测？ 动态分支预测：在程序运行时，根据分支指令过去的表现来预测其将来的行为。 如果分支行为发生了变化，预测结果也跟着改变。 有更好的预测准确度和适应性。

54 尽快找到分支目标地址（或指令） -- 减少开销
4.3 动态分支预测技术 3. 分支预测的有效性取决于： 预测的准确性 预测正确和不正确两种情况下的分支开销 决定分支开销的因素： 流水线的结构 预测的方法 预测错误时的恢复策略等 4. 目标 预测分支是否成功 -- 提高准确性 尽快找到分支目标地址（或指令） -- 减少开销 （避免控制相关造成流水线停顿） 有效的恢复现场

55 如何根据这些信息来预测分支的去向（甚至取到 指令）； 如何保护分支前现场；
4.3 动态分支预测技术 5. 需要解决的关键问题 如何记录分支的历史信息； 如何根据这些信息来预测分支的去向（甚至取到 指令）； 如何保护分支前现场； 在预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

56 如何根据这些信息来预测分支的去向 – 分支目标缓冲器缓冲器
4.3 动态分支预测技术 介绍三种方法解决如上三个问题： 如何记录分支的历史信息 -- 分支历史表 如何根据这些信息来预测分支的去向 – 分支目标缓冲器缓冲器 如何保护分支前现场 – 基于前瞻的执行

57 4.3 动态分支预测技术 4.3.1 采用分支历史表 BHT 分支历史表BHT（Branch History Table）或分支预测缓冲器（Branch Prediciton Buffer） 最简单的动态分支预测方法。 用BHT来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此进行预测。 只有1个预测位的分支预测缓冲 　　记录分支指令最近一次的历史，BHT中只需要 1位二进制位。 　（最简单）

58 采用两位二进制位来记录历史 两位分支预测的状态转换如下所示： 4.3 动态分支预测技术 提高预测的准确度
研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。 两位分支预测的状态转换如下所示：

59 两位分支预测中的操作有两个步骤： 4.3 动态分支预测技术 分支预测。
当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测 。 若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。 状态修改。

60 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。
4.3 动态分支预测技术 BHT方法只在以下情况下才有用： 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。 前述5段经典流水线：由于判定分支是否成功和计算 分支目标地址都是在ID段完成，所以BHT方法不会给 该流水线带来好处。 研究结果表明：对于SPEC89测试程序来说，具有大小为4K的BHT的预测准确率为82%～99%。 一般来说，采用4K的BHT就可以了。 BHT可以跟分支指令一起存放在指令Cache中，也可以用一个专门的硬件来实现。

61 4.3.2 采用分支目标缓冲器BTB 目标：将分支的开销降为 0 方法：分支目标缓冲
4.3 动态分支预测技术 4.3.2 采用分支目标缓冲器BTB 目标：将分支的开销降为 0 方法：分支目标缓冲 将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。 这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB，或者Branch-Target Cache）。

62 4.3 动态分支预测技术 BTB的结构

63 采用BTB后，在流水线各个阶段所进行的相关操作：

64 指令在BTB中？ 预测 实际情况 延迟周期 是 成功 不成功 2 不是
4.3 动态分支预测技术 采用BTB后，各种可能情况下的延迟 ： 指令在BTB中？ 预测 实际情况 延迟周期 是 成功 不成功 2 不是 更新时停止 取指令

65 BTB的另一种形式 在分支目标缓冲器中存放一条或者多条分支 目标处的指令。 有三个潜在的好处： 4.3 动态分支预测技术
更快地获得分支目标处的指令； 可以一次提供分支目标处的多条指令，这对于多流出处理器是很有必要的； 使我们可以进行称为分支折叠（branch folding）的优化。 实现零延迟无条件分支，甚至有时还可以做到 零延迟条件分支。 分支折叠： 没有找到更多的资料。一些资料表明，缓存目标地址，就是branch folding

66 4.3.3 基于硬件的前瞻执行 前瞻执行（speculation）的基本思想： 对分支指令的结果进行猜测，并假设这个猜测
4.3 动态分支预测技术 4.3.3 基于硬件的前瞻执行 前瞻执行（speculation）的基本思想： 对分支指令的结果进行猜测，并假设这个猜测 总是对的，然后按这个猜测结果继续取、流出和执 行后续的指令。只是执行指令的结果不是写回到寄 存器或存储器，而是放到一个称为ROB（ReOrder Buffer）的缓冲器中。等到相应的指令得到“确认” （commit）（即确实是应该执行的）之后，才将结 果写入寄存器或存储器。

67 在控制相关的结果尚未出来之前，前瞻地执行后续指令。
4.3 动态分支预测技术 基于硬件的前瞻执行结合了三种思想： 动态分支预测。用来选择后续执行的指令。 在控制相关的结果尚未出来之前，前瞻地执行后续指令。 用动态调度对基本块的各种组合进行跨基本块的调度。 对Tomasulo算法加以扩充，就可以支持前瞻执行。 把Tomasulo算法的写结果和指令完成加以区分，分成两个不同的段： 写结果，指令确认

68 写结果段 指令确认段 4.3 动态分支预测技术 把前瞻执行的结果写到ROB中； 通过CDB在指令之间传送结果，供需要用到这些结果的指令使用。
在分支指令的结果出来后，对相应指令的前瞻执行 给予确认。 如果前面所做的猜测是对的，把在ROB中的结果写到寄存器或存储器。 如果发现前面对分支结果的猜测是错误的，那就不予以确认（清空ROB），并从那条分支指令的另一条路径开始重新执行。

69 4.3 动态分支预测技术 实现前瞻的关键思想： 允许指令乱序执行，但必须顺序确认。 支持前瞻执行的浮点部件的结构

70 指令类型 目标地址 数据值 就绪状态

71 Tomasulo算法中保留站的换名功能是由ROB来完成的。
4.3 动态分支预测技术 ROB中的每一项由以下4个字段组成： 指令类型 指出该指令是分支指令、store指令或寄存器操作指令。 目标地址 给出指令执行结果应写入的目标寄存器号（如果是 load和ALU指令）或存储器单元的地址（如果是store指 令）。 数据值字段 用来保存指令前瞻执行的结果，直到指令得到确认。 就绪字段 指出指令是否已经完成执行并且数据已就绪。 Tomasulo算法中保留站的换名功能是由ROB来完成的。

72 采用前瞻执行机制后，指令的执行步骤： 4.3 动态分支预测技术 （在Tomasulo算法的基础上改造的 ） 流出
从浮点指令队列的头部取一条指令。 如果有空闲的保留站（设为r）且有空闲的ROB项（设为b），就流出该指令。 如果该指令需要的操作数在寄存器或者ROB中就绪，就将其值取到保留站r中；否则，将产生其值的ROB编号写入。 ROB的编号写入r。 用对应的ROB编号对目标寄存器进行预约。 流出（Tomasulo算法） 从指令队列的头部取一条指令。 如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站r。 如果该指令需要的操作数在寄存器中就绪，就将值取到保留站r中；如果没就绪，将产生该操作数的保留站的标识送到保留站r。 完成对目标寄存器的预约工作。

73 4.3 动态分支预测技术 执行 如果有操作数尚未就绪，就等待，并不断地监测CDB。
当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。 Load指令做有效地址运算和读取数据；store指令只做有效地址运算。 执行（Tomasulo算法） 如果有操作数尚未就绪，就等待，并不断地监测CDB。 当两个操作数都已在保留站中就绪后，就可以执行该指令的操作。 Load指令做有效地址运算和读取数据；store指令只做有效地址运算。

74 4.3 动态分支预测技术 写结果 当结果产生后，将该结果连同本指令在流出段所分配到的ROB项的编号放到CDB上，经CDB写到ROB以及所有等待该结果的保留站。 释放产生该结果的保留站。 store指令在本阶段完成，其操作为: 如果要写入存储器的数据已经就绪，就把该数据写入分配给该store指令的ROB项。 否则，就监测CDB，直到那个数据在CDB上播送出来，这时才将之写入分配给该store指令的ROB项。 写结果（tomasulo算法） 当结果产生后，将该结果放到CDB上，经CDB写到所有等待该结果的寄存器和保留站中。 当写入地址和数据齐备时，Store指令完成存储器的写入。 释放产生该结果的保留站。

75 4.3 动态分支预测技术 确认 （Tomasulo算法无该阶段） 对分支指令、store指令以及其他指令的处理不同：
当该指令到达ROB队列的头部而且其结果已经就绪时，就把该结果写入该指令的目标寄存器，并从ROB中删除该指令。 store指令 处理与上面类似，只是它把结果写入存储器。 分支指令 当预测错误的分支指令到达ROB队列的头部时，清空ROB，并从分支指令的另一个分支重新开始执行。（错误的前瞻执行） 当预测正确的分支指令到达ROB队列的头部时，该指令执行完毕。 异常指令（实现精确异常） 当产生异常的指令到达ROB队列的头部时，对异常进行处理， 同时清空ROB。

76 4.3 动态分支预测技术 例4.3 假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出当指令MUL.D即将确认时的状态表内容。 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,F8,F2

77 执行中状态变化的时钟周期如下 4.3 动态分支预测技术 上表可以看出：指令乱序执行，顺序确认
流出 执行 写结果 确认 执行延迟 LD F6 , 34(R2) 1 2 3 4 1个周期 LD F2 , 45(R3) 5 MULTD F0 , F2 , F4 5-14 15 16 10个周期 SUBD F8 , F2 , F6 5-6 7 17 2个周期 DIVD F10 , F0 , F6 16-55 56 57 40个周期 ADDD F6 , F8 , F2 6 8-9 10 58 上表可以看出：指令乱序执行，顺序确认 Mul即将确认，第16周开始，此时表中红色部分均为空。下面根据此表直接分析各个信息表的状态

78 前瞻执行中MUL.D确认前，保留站和ROB的状态 名称 保留站
4.3 动态分支预测技术 前瞻执行中MUL.D确认前，保留站和ROB的状态 名称 保留站 Busy Op Vj Vk Qj Qk Dest A Add1 no Add2 Add3 Mult1 MUL Mem[45+ Regs[R2]] Regs[F4] #3 Mult2 yes DIV #2*Reg[R3] Mem[34+Regs[R2]] #5

79 项号 ROB Busy 指令 状态 目的 Value 1 no L.D F6, 34（R2） 确认 F6 Mem[34+Regs[R2]] 2 L.D F2, 45（R3） F2 Mem[45+Regs[R3]] 3 yes MUL.D F0, F2, F4 写结果 F0 #2Regs[F4] 4 SUB.D F8, F6, F2 F8 #1－#2 5 DIV.D F10, F0, F6 执行 F10 6 ADD.D F6,F8,F2 #4＋#2 字段 浮点寄存器状态 F0 F2 F4 F6 F8 F10 … F30 ROB项编号 3 6 4 5 Busy yes no

80 很容易地推广到整数寄存器和整数功能单元上。 主要缺点：所需的硬件太复杂。
4.3 动态分支预测技术 前瞻执行 通过ROB实现了指令的顺序完成。 能够实现精确异常。 很容易地推广到整数寄存器和整数功能单元上。 主要缺点：所需的硬件太复杂。

81 4.4 多指令流出技术 一个时钟周期内流出多条指令， CPI＜1。 单流出和多流出处理机执行指令的时空图对比

82 4.4 多指令流出技术 单流出和多流出处理机执行指令的时空图

83 超长指令字VLIW（Very Long Instruction Word）
4.4 多指令流出技术 多流出处理机有两种基本风格： 超标量（Superscalar） 在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有上限） 设这个上限为n，就称该处理机为n流出。 可以通过编译器进行静态调度（顺序），也可以基于Tomasulo算法进行动态调度（乱序）。 超长指令字VLIW（Very Long Instruction Word） 在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。 指令包中，指令之间的并行性是通过指令显式地表示出来的。 指令调度是由编译器静态完成的。

84 超标量处理机与VLIW处理机相比有两个优点：
4.4 多指令流出技术 超标量处理机与VLIW处理机相比有两个优点： 超标量结构对程序员是透明的，因为处理机能自己检测下一条指令能否流出，从而不需要重新排列指令来满足指令的流出。 即使是没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，当然运行的效果不会很好。 要想达到很好的效果，方法之一： 使用动态超标量调度技术。 下表列出了一些基本的多流出技术、这些技术的特点以及采用这些技术的处理机例子。

85 技 术 流出 结构 冲突 检测 调 度 主要特点 处理机实例 超标量 （静态） 动态 硬件 静态 顺序执行 Sun UltraSPARCⅡ/Ⅲ （动态） 部分乱序执行 IBM Power2 （猜测） 带有猜 测的动 态执行 带有猜测的 乱序执行 Pentium Ⅲ/4， MIPS R10K， Alpha 21264， HP PA 8500， IBM RS64Ⅲ VLIW /LIW 软件 流出包之间 没有冲突 Trimedia，i860 EPIC 主要是 相关性被编译 器显式地标记出来 Itanium

86 4.4.1 基于静态调度的多流出技术 在典型的超标量处理器中，每个时钟周期可流出1到8条指令。 指令按序流出，在流出时进行冲突检测。
4.4 多指令流出技术 4.4.1 基于静态调度的多流出技术 在典型的超标量处理器中，每个时钟周期可流出1到8条指令。 指令按序流出，在流出时进行冲突检测。 在当前流出的指令序列中，不存在数据冲突或者相 关冲突。 举例：一个4流出的静态调度超标量处理机 在取指令阶段，流水线将从取指令部件收到1～4条指令（称为流出包）。 在一个时钟周期内，这些指令有可能是全部都能流出，也可能是只有一部分能流出。

87 流出部件检测结构冲突或者数据冲突。 MIPS处理机是怎样实现超标量的呢？ 假设：每个时钟周期流出两条指令： 4.4 多指令流出技术
一般分两阶段实现： 第一阶段：进行流出包内的冲突检测，选出初步判定可以流出的指令。 第二阶段：检测所选出的指令与正在执行的指令是否有冲突。 MIPS处理机是怎样实现超标量的呢？ 假设：每个时钟周期流出两条指令： 1条整数型指令＋1条浮点操作指令 其中，把load指令、store指令、分支指令归类为整数型指令。 简单，能消除大部分的包内冲突

88 同时取两条指令（64位），译码两条指令（64位）。 对指令的处理包括以下步骤： 从Cache中取两条指令。
4.4 多指令流出技术 要求： 同时取两条指令（64位），译码两条指令（64位）。 对指令的处理包括以下步骤： 从Cache中取两条指令。 确定那几条指令可以流出（0～2条指令）。 把它们发送到相应的功能部件。 双流出超标量流水线中指令的执行过程 假设：所有的浮点指令都是加法指令，其执行时间为两个时钟周期。 为简单起见，下图中总是把整数指令放在浮点指令的前面。

89 4.4 多指令流出技术 指令类型 流水线工作情况 整数指令 IF ID EX MEM WB 浮点指令

90 采用“1条整数型指令＋1条浮点指令”并行流出的方式，需要增加的硬件很少。
4.4 多指令流出技术 采用“1条整数型指令＋1条浮点指令”并行流出的方式，需要增加的硬件很少。 浮点load或浮点store指令将使用整数部件，会增加对浮点寄存器的访问冲突。 增设一个浮点寄存器的读/写端口。 由于流水线中的指令多了一倍，定向路径也要增加。

91 限制超标量流水线的性能发挥的障碍。 load指令 分支延迟 4.4 多指令流出技术 load后续3条指令都不能使用其结果，否则就会引起停顿。
如果分支指令是流出包中的第一条指令，则其延迟是3个时钟周期； 否则就是流出包中的第二条指令，其延迟就是两个时钟周期。 分支指令，造成的3个延迟为包中的第二条指令，和下一个包的两条指令；（我认为应该是2个周期延迟） 造成的2个延迟是下一个周期的两条指令。（我认为应该是1个周期的延迟）

92 4.4.2 基于动态调度的多流出技术 扩展Tomasulo算法：支持两路超标量 采用一种比较简单的方法：
4.4 多指令流出技术 4.4.2 基于动态调度的多流出技术 扩展Tomasulo算法：支持两路超标量 每个时钟周期流出两条指令； 一条是整数指令，另一条是浮点指令。 采用一种比较简单的方法： 指令按顺序流向保留站，否则会破坏程序语义。 将整数所用的表结构与浮点用的表结构分离开，分别进行处理，这样就可以同时地流出一条浮点指令和一条整数指令到各自的保留站。

93 在半个时钟周期里完成流出步骤，这样一个时钟周期就能处理两条指令。
4.4 多指令流出技术 有两种不同的方法可以实现多流出。 关键在于：对保留站的分配和对流水线控制表格的修改。 在半个时钟周期里完成流出步骤，这样一个时钟周期就能处理两条指令。 设置一次能同时处理两条指令的逻辑电路。 现代的流出4条或4条以上指令的超标量处理机 经常是两种方法都采用。

94 Loop: L.D F0, 0（R1） // 取一个数组元素放入F0 ADD.D F4, F0, F2 // 加上在F2中的标量
4.4 多指令流出技术 例4.4 对于采用了Tomasulo算法和多流出技术的MIPS流水线，考虑以下简单循环的执行。该程序把F2中的标量加到一个向量的每个元素上。 Loop: L.D F0, 0（R1） // 取一个数组元素放入F0 ADD.D F4, F0, F // 加上在F2中的标量 S.D F4, 0（R1） // 存结果 DADDIU R1,R1，#-8 // 将指针减少8（每个数据占8个字节） BNE R1,R2,Loop // 若R1不等于R2，表示尚未结束，转移到Loop继续

95 现做以下假设： 4.4 多指令流出技术 每个时钟周期能流出一条整数指令和一条浮点指令，即使它们相关也是如此。
有一个整数部件，用于整数ALU运算和地址计算；并且对于每一种浮点操作类型都有一个独立的流水化了的浮点功能部件。 指令流出和写结果各占用一个时钟周期。 具有动态分支预测部件和一个独立的计算分支条件的功能部件。 分支指令单独流出，没有采用延迟分支，但分支预测是完美的。分支指令完成前，其后续指令只能被取出和流出，但不能执行。

96 列出该程序前面3遍循环中各条指令的流出、开始执行和将结果写到CDB上的时间。
4.4 多指令流出技术 因为写结果占用一个时钟周期，所以产生结果的延迟为：整数运算一个周期，load两个周期，浮点加法运算3个周期。 列出该程序前面3遍循环中各条指令的流出、开始执行和将结果写到CDB上的时间。 解 执行时，该循环将动态展开，并且只要可能就流出两条指令。 为了便于分析，表中列出了访存发生的时刻。运行结果如下图所示。

97 遍数 指 令 流出 执行 访存 写CDB 说明 1 L.D F0,0（R1） 2 3 4 流出第一条指令 ADD.D F4,F0,F2 5 8 等待L.D的结果 S.D F4,0（R1） 9 等待ADD.D的结果 DADDIU R1,R1,#-8 等待ALU BNE R1,R2,Loop 6 等待DADDIU的结果 7 等待BNE完成 10 13 14 11 12 15 18 19 16

98 虽然指令的流出率比较高，但是执行效率并不是很高。
4.4 多指令流出技术 从图中可以看出： 程序基本可以达到3拍流出5条指令 IPC＝5/3＝1.67 条/拍 虽然指令的流出率比较高，但是执行效率并不是很高。 16拍共执行15条指令， 平均指令执行速度为15/16＝0.94 条/拍。 原因是浮点运算少，ALU部件成了瓶颈。 解决方法：增加一个加法器，把ALU功能和地址运算功能分开。

99 上述双流出动态调度流水线的性能受限于以下3个因素： 整数部件和浮点部件的工作负载不平衡，没有充分发挥出浮点部件的作用。
4.4 多指令流出技术 上述双流出动态调度流水线的性能受限于以下3个因素： 整数部件和浮点部件的工作负载不平衡，没有充分发挥出浮点部件的作用。 应该设法减少循环中整数型指令的数量。 每个循环迭代中的控制开销太大。 5条指令中有两条指令是辅助指令。 应该设法减少或消除这些指令。 控制相关使得处理机必须等到分支指令的结果出来后才能开始下一条L.D指令的执行。

100 4.4.3 超长指令字技术（VLIW） 把能并行执行的多条指令组装成一条很长的指令。 设置多个功能部件。
4.4 多指令流出技术 4.4.3 超长指令字技术（VLIW） 把能并行执行的多条指令组装成一条很长的指令。 （100多位到几百位） 设置多个功能部件。 指令字被分割成一些字段，每个字段称为一个操作槽，直接独立地控制一个功能部件。 在VLIW处理机中，所有的处理和指令安排都是由编译器完成的。

101 4.4 多指令流出技术 例4.5 假设VLIW处理机每个时钟周期可同时流出5条指令：两条访存指令、两条浮点操作指令和一条整数指令或分支指令。对于例4.4中的循环展开后的代码，给出它在该VLIW中的代码序列。不考虑分支指令的延迟槽。

102 每遍循环平均1.6个时钟周期（展开了5次循环）。 8个时钟周期内流出了17条指令，每个时钟周期2.1条。
4.4 多指令流出技术 访存指令1 访存指令2 浮点指令1 浮点指令2 整数/转移指令 L.D F0,0(R1) L.D F6,-8(R1) L.D F10,-16(R1) L.D F14,-24(R1) L.D F18,-32(R1) ADD.D F4,F0,F2 ADD.DF8,F6,F2 ADD.DF12,F10,F2 ADD.DF16,F14,F2 ADD.DF20,F18,F2 S.D F4,0(R1) S.D F8,-8(R1) S.D F12,-16(R1) S.D F16,–24(R1) DADDIUR1,R1,#-40 S.D F20,8(R1) BNE R1,R2,Loop 解 代码序列如下图所示。 运行时间为8个时钟周期。 每遍循环平均1.6个时钟周期（展开了5次循环）。 8个时钟周期内流出了17条指令，每个时钟周期2.1条。 8个时钟周期共有操作槽85=40个，有效槽的比例为42.5%。

103 VLIW存在的一些问题 程序代码长度增加了 采用了锁步机制 机器代码的不兼容性 4.4 多指令流出技术 提高并行性而进行的大量的循环展开。
指令字中的操作槽并非总能填满。 解决：采用指令共享立即数字段的方法，或者采用指 令压缩存储、调入Cache或译码时展开的方法。 采用了锁步机制 任何一个操作部件出现停顿时，整个处理机都要停顿。 机器代码的不兼容性

104 4.4.4 多流出处理器受到的限制 指令多流出处理器受哪些因素的限制呢？ 主要受以下三个方面的影响： 4.4 多指令流出技术
程序所固有的指令级并行性。 硬件实现上的困难。 超标量和超长指令字处理器固有的技术限制。

105 4.4.5 超流水线处理机 将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。
4.4 多指令流出技术 4.4.5 超流水线处理机 将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。 对于一台每个时钟周期能流出n条指令的超流水线计算机来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令。 实际上该超流水线计算机的流水线周期为1/n个时钟周期。 一台每个时钟周期分时流出两条指令的超流水线计算机的时空图。

106 4.4 多指令流出技术

107 在有的资料上，把指令流水线级数为8或8以上的流水线处理机称为超流水线处理机。 典型的超流水线处理器：SGI公司的MIPS系列R4000
4.4 多指令流出技术 在有的资料上，把指令流水线级数为8或8以上的流水线处理机称为超流水线处理机。 典型的超流水线处理器：SGI公司的MIPS系列R4000 R4000微处理器芯片内有2个Cache： 指令Cache和数据Cache 容量都是8 KB 每个Cache的数据宽度为64 b R4000的核心处理部件：整数部件 一个32×32位的通用寄存器组 一个算术逻辑部件（ALU） 一个专用的乘法/除法部件

108 浮点部件 R4000的指令流水线有8级 4.4 多指令流出技术 一个执行部件 浮点乘法部件 浮点除法部件 浮点加法/转换/求平方根部件
（它们可以并行工作） 一个16×64位的浮点通用寄存器组。浮点通用寄存器组也可以设置成32个32位的浮点寄存器。 R4000的指令流水线有8级

109 4.4 多指令流出技术

110 各级的功能 4.4 多指令流出技术 IF：取指令的前半步，根据PC值去启动对指令Cache的访问。
IS：取指令的后半步，在这一级完成对指令Cache的访问。 RF：指令译码，访问寄存器组读取操作数，冲突检测，并判断指令Cache是否命中。 EX：指令执行。包括有效地址计算，ALU操作，分支目标地址计算，条件码测试。 DF：取数据的前半步，启动对数据Cache的访问。 DS：取数据的后半步，在这一级完成对数据Cache的访问。 TC：标识比较，判断对数据Cache的访问是否命中。 WB：load指令或运算型指令把结果写回寄存器组。

111 4.4 多指令流出技术 MIPS R4000指令流水线时空图

112 载入延迟为两个时钟周期

113 4.5 循环展开和指令调度 4.5.1 循环展开和指令调度的基本方法
充分开发指令之间存在的并行性，找出不相关的指令序列，让它们在流水线上重叠并行执行。 增加指令间并行性最简单和最常用的方法 开发循环级并行性——循环的不同迭代之间存在的并行性。 在把循环展开后，通过重命名和指令调度来开发更多的并行性。

114 编译器完成这种指令调度的能力受限于两个特性： 程序固有的指令级并行性； 流水线功能部件的执行延迟。 本节中，我们使用的浮点流水线延迟为：
4.5 循环展开和指令调度 编译器完成这种指令调度的能力受限于两个特性： 程序固有的指令级并行性； 流水线功能部件的执行延迟。 本节中，我们使用的浮点流水线延迟为： 产生结果的指令 使用结果的指令 延迟（时钟周期数） 浮点计算 另一个浮点计算 3 浮点store（S.D） 2 浮点load（L.D） 1

115 整数运算部件是全流水或者重复设置了足够的份数。
4.5 循环展开和指令调度 假设采用第3章的5段整数流水线： 分支的延迟：1个时钟周期。 整数load指令的延迟：1个时钟周期。 整数运算部件是全流水或者重复设置了足够的份数。

116 例4.6 对于下面的源代码，转换成MIPS汇编语言， 在不进行指令调度和进行指令调度两种情况下，分析其 代码一次循环所需的执行时间。
4.5 循环展开和指令调度 例4.6 对于下面的源代码，转换成MIPS汇编语言， 在不进行指令调度和进行指令调度两种情况下，分析其 代码一次循环所需的执行时间。 for (i=1； i<=1000； i++) x[i] = x[i] + s； 解 把该程序翻译成MIPS汇编语言代码： 假设R1的初值是指向第一个元素，8（R2）指向最后一个元素。

117 Loop：L.D F0,0（R1） ADD.D F4,F0,F2 S.D F4, 0（R1） DADDIU R1,R1，#-8
4.5 循环展开和指令调度 Loop：L.D F0,0（R1） ADD.D F4,F0,F2 S.D F4, 0（R1） DADDIU R1,R1，#-8 BNE R1,R2,Loop 其中： 整数寄存器R1：指向向量中的当前元素。 （初值为向量中最高端元素的地址） 浮点寄存器F2：用于保存常数s。

118 不进行指令调度的情况下，程序的实际执行情况：
4.5 循环展开和指令调度 不进行指令调度的情况下，程序的实际执行情况： 指令流出时钟 Loop: L.D F0,0（R1） 1 （空转） ADD.D F4,F0,F （空转） （空转） S.D F4, 0（R1） 6 DADDIU R1,R1，# （空转） BNE R1,R2,Loop （空转） 每个元素的操作需要10个时钟周期，其中5个是空转周期。

119 指令调度以后，程序的执行情况如下： 4.5 循环展开和指令调度 把DADDIU指令调度到了L.D指令和ADD.D指令之间的“空转”拍。
把S.D指令放到了分支指令的延迟槽中。 对存储器地址偏移量进行调整。

120 Loop: L.D F0, 0(R1) DADDIU R1,R1,#-8 ADD.D F4, F0, F2 （空转）
4.5 循环展开和指令调度 Loop: L.D F0, 0(R1) DADDIU R1,R1,#-8 ADD.D F4, F0, F2 （空转） BNE R1,R2,Loop S.D F4，8(R1) 　 Loop: L.D F0,0（R1） （空转） ADD.D F4,F0,F2 （空转） S.D F4, 0（R1） DADDIU R1,R1,#-8 BNE R1,R2,Loop

121 指令流出时钟 Loop: L.D F0, 0(R1) 1 DADDIU R1, R1, #-8 2 ADD.D F4, F0, F2 3
4.5 循环展开和指令调度 指令流出时钟 Loop: L.D F0, 0(R1) DADDIU R1, R1, # ADD.D F4, F0, F （空转） BNE R1, Loop S.D F4，8(R1) 一个元素的操作时间从10个时钟周期减少到6个,其中5个周期是有指令执行的，1个为空转周期。

122 例子中的问题及解决方案 4.5 循环展开和指令调度 只有L.D、ADD.D和S.D这3条指令是有效操作。 (取、加、存) 占用3个时钟周期。
而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。 循环展开技术 把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件。 这给编译器进行指令调度带来了更大的空间。

123 4.5 循环展开和指令调度 例4.7 （体现循环展开技术的特点） 将上述例子中的循环展开3次得到4个循环体，然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。假定R1的初值为32的倍数，即循环次数为4的倍数。消除冗余的指令，并且不要重复使用寄存器。 解 无需在循环体后面增加补偿代码

124 4.5 循环展开和指令调度 分配寄存器（不重复使用寄存器 ）： F0、F4：用于展开后的第1个循环体 F2：保存常数 F6、F8：展开后的第2个循环体 F10、F12：第3个循环体 F14、F16：第4个循环体

125 展开后没有调度的代码如下： 指令流出时钟 Loop: L.D F0,0(R1) 1 （空转） 2 ADD.D F4,F0,F2 3
（空转） 2 ADD.D F4,F0,F2 3 （空转） 4 （空转） 5 S.D F4, 0（R1） 6 L.D F6,-8(R1) 7 （空转） 8 ADD.D F8,F6,F2 9 （空转） 10 （空转） 11 S.D F8, -8（R1） 12 L.D F10,-16(R1) 13 （空转） 14 指令流出时钟 ADD.D F12,F10,F2 15 （空转） 16 （空转） 17 S.D F12,-16(R1) 18 L.D F14,-24(R1) 19 （空转） 20 ADD.D F16,F14,F2 21 （空转） 22 （空转） 23 S.D F16,-24(R1) 24 DADDIU R1,R1,#-32 25 （空转） 26 BNE R1,R2,Loop 27 （空转） 28

126 结果分析: 4.5 循环展开和指令调度 这个循环每遍共使用了28个时钟周期。 有4个循环体，完成4个元素的操作。
平均每个元素使用28/4=7个时钟周期 原始循环的每个元素需要10个时钟周期。 节省的时间：从减少循环控制的开销中获得的。 在整个展开后的循环中，实际指令只有14条，其他14个周期都是空转。 效率并不高

127 对指令序列进行优化调度，以减少空转周期：
指令流出时钟 Loop: L.D F0,0(R1) 1 L.D F6,-8(R1) 2 L.D F10,-16(R1) 3 L.D F14,-24(R1) 4 ADD.D F4,F0,F ADD.D F8,F6,F ADD.D F12,F10,F ADD.D F16,F14,F S.D F4,0(R1) 9 S.D F8,-8(R1) 10 DADDIU R1,R1,# S.D F12,16(R1) 11 BNE R1,R2,Loop 13 S.D F16,8(R1) 14

128 结果分析： 4.5 循环展开和指令调度 没有数据相关引起的空转等待。 整个循环仅仅使用了14个时钟周期。
平均每个元素的操作使用14/4=3.5个时钟周期。 通过循环展开、寄存器重命名和指令调度，可以有效地开发出指令级并行。

129 循环展开和指令调度时要注意以下几个方面： 保证正确性。
4.5 循环展开和指令调度 循环展开和指令调度时要注意以下几个方面： 保证正确性。 在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制，操作数偏移量的修改。 注意有效性。 只有能够找到不同循环体之间的无关性，才能有效地使用循环展开。 使用不同的寄存器。 （否则可能导致新的冲突） 删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。

130 注意对存储器数据的相关性分析 注意新的相关性 4.5 循环展开和指令调度
例如：对于load指令和store指令，如果它们在不同的循环迭代中访问的存储器地址是不同的，它们就是相互独立的，可以相互对调。 注意新的相关性 由于原循环不同次的迭代在展开后都到了同一次循环体中，因此可能带来新的相关性。

131 4.5 循环展开和指令调度 4.5.2 静态超标量处理机中的循环展开 根据表4.4给出的延迟条件，超标量处理器如何进行循环展开和指令调度？

132 4.5 循环展开和指令调度 例4.8 下面是前面使用的循环程序段，对其进行循环展开，并在超标量流水线上进行调度。 Loop: L.D F0,0（R1） // 取一个数组元素放入F0 ADD.D F4,F0,F2 // 加上在F2中的标量 S.D F4,0（R1） // 存结果 DADDIU R1,R1,#-8 // 将指针减少8（每个数据占8个字节） BNE R1,R2,Loop // 若R1不等于R2，表示尚未结束，转移到Loop继续

133 解 将循环展开5遍并调度，可得如下代码： Loop: L.D F0,0(R1) L.D F6,-8(R1) L.D F10,-16(R1) L.D F14,-24(R1) L.D F18,-32(R1) ADD.D F4,F0,F2 ADD.D F8,F6,F2 ADD.D F12,F10,F2 ADD.D F16,F14,F2 ADD.D F20,F18.F2 S.D F4,0(R1) S.D F8,-8(R1) S.D F12,-16(R1) S.D F16,-24(R1) DADDIU R1,R1,# -40 BNE R1,R2,Loop S.D F20,8(R1)

134 整数指令 浮点指令 时钟周期 Loop: L.D F0（R1） 1 L.D F6,-8（R1） 2 L.D F10,-16（R1）
进一步针对超标量进行调度后的指令序列如下所示 整数指令 浮点指令 时钟周期 Loop: L.D F0（R1） 1 L.D F6,-8（R1） 2 L.D F10,-16（R1） ADD.D F4,F0,F2 3 L.D F14,-24（R1） ADD.D F8,F6,F2 4 L.D F18,-32（R1） ADD.D F12,F10,F2 5 S.D F4,0（R1） ADD.D F16,F14,F2 6 S.D F8,-8（R1） ADD.D F20,F18,F2 7 S.D F12,-16（R1） 8 S.D F16,-24（R1） 9 DADDIU R1,R1,#-40 10 BNE R1,R2,Loop 11 S.D F20,8（R1） 12

135 4.5 循环展开和指令调度 每次循环需12个时钟周期，即计算每个结果需要2.4个时钟周期。 （每次循环计算5个结果） 在普通的MIPS流水线上，没有调度的代码迭代一次为9个时钟周期，调度后为6个时钟周期，展开4次并调度后每个迭代为3.5个时钟周期。 与之相比，超标量流水线的性能提高分别为： 3.75倍、2.5倍、1.4倍 在这个例子中可以看到，超标量MIPS流水线的性能主要受限于：整数计算和浮点计算之间的平衡问题。 本例中没有足够的浮点指令来使两路流水线都达到饱和。