第4章 指令级并行 授课教师：车喜龙 chexilong@jlu.edu.cn

4.1 指令级并行的概念 4.2 指令的动态调度 4.3 动态分支预测技术 4.4 多指令流出技术

4.1 指令级并行 4.1.1 指令级并行的概念 当指令之间不存在相关时，它们在流水线中是可以重叠起来并行执行的。这种指令序列中存在的潜在并行性称为指令级并行。 （ILP：Instruction-Level Parallelism） 本章研究：如何通过各种可能的技术，在流水线思想的基础上，获得更多的指令级并行性。 硬件技术(动态)＋软件技术（静态） 必须要两种技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行。

流水线的理想CPI加上各类相关导致的停顿周期数： 4.1 指令级并行 流水线处理机的实际CPI 流水线的理想CPI加上各类相关导致的停顿周期数： CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 理想CPI是衡量流水线最高性能的一个指标，减少任何一种停顿，都可以有效地减少实际CPI，从而提高流水线的性能。 相关是程序固有属性，它反映程序中指令之间的相互依赖关系。 一次相关是否会导致冲突发生以及该冲突会带来多长的停顿，则是流水线的属性。 可以从两个方面来解决相关问题： 通过动态/静态指令调度，保持相关，但避免发生冲突。 通过代码变换，消除相关。

2. 几种主要技术以及它们所克服的停顿 4.1 指令级并行 技术 克服的停顿 基本流水线调度 数据先写后读相关停顿 循环展开 控制相关停顿 寄存器换名 数据写后写相关和先读后写相关停顿 指令动态调度（Tomasulo算法） 各种数据相关停顿 动态分支预测 前瞻执行（Speculation） 数据/控制相关停顿 多指令流出（超标量和超长指令字） 提高理想CPI

定义：除了入口和出口以外不包含其他分支的线性代码段。 程序平均每6～7条指令就会有一个分支。 4.1 指令级并行 3. 基本程序块 定义：除了入口和出口以外不包含其他分支的线性代码段。 程序平均每6～7条指令就会有一个分支。 要开发指令的并行性，就不能局限于基本程序块内部，而要将跨越多个基本块作为各种优化技术的出发点。 4. 程序顺序 定义：由源程序确定的在完全串行方式下指令的执行顺序。 由于相关存在，要保持程序顺序，否则执行结果就会改变。 程序顺序不需要绝对保持，在不改变结果的情况下，可以适当的修改

5. 循环级并行性：循环体中指令之间的并行性。 不是循环体之内，而是循环体与循环体之间的并行 4.1 指令级并行 5. 循环级并行性：循环体中指令之间的并行性。 不是循环体之内，而是循环体与循环体之间的并行 最常见、最基本、最简单、最有效 是指令级并行研究的重点之一 例如，考虑下述语句： for （i=1； i<=500； i=i＋1） a[i]=a[i]＋s； 每一次循环都可以与其他的循环重叠并行执行； 在每一次循环的内部，没有任何的并行性。 循环级并行的基本开发技术 指令调度技术，循环展开技术，寄存器换名技术 采用向量指令和向量数据表示

必须保持的最关键的两个属性是：异常行为和数据流。 保持异常行为：是指无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。 4.1 指令级并行 6. 程序的正确执行 必须保持的最关键的两个属性是：异常行为和数据流。 保持异常行为：是指无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。 即原来程序中怎么发生，改变执行顺序后还是怎么发生。条件弱化为：指令执行顺序的改变不能导致程序中发生新的异常。 举例说明 DADDU R2，R3，R4 BEQZ R2，L1 LW R1，0（R2） L1 ： 如果LW指令移到分支之前，有可能产生“访存保护”异常，即访问R2 =0号地址，该地址只属于OS空间，而非用户空间。

数据流：指数据值从其生产者指令到其消费者指令的实际流动。 4.1 指令级并行 数据流：指数据值从其生产者指令到其消费者指令的实际流动。 分支指令使得数据流具有动态性，它使得给定消费者指令要使用的数据可以有多个来源，程序顺序决定了哪条指令才是真正的数据生产者。 仅仅保持数据相关性是不够的，因为消费者指令可能相关于多条生产者指令，只有再加上保持控制顺序，才能够保持程序正确性。 举例： DADDU R1，R2，R3 BEQZ R4，L1 DSUBU R1，R5，R6 L1 ：… OR R7，R1，R8 DSUBU指令不能移到分支指令之前，必须保持控制相关

只要能保证不影响异常行为和不改变数据流，控制相关并不是必须严格保持的关键属性。 4.1 指令级并行 只要能保证不影响异常行为和不改变数据流，控制相关并不是必须严格保持的关键属性。 这时，可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。 举例： DADDU R1，R2，R3 BEQZ R12，Skipnext DSUBU R4，R5，R6 DADDU R5，R4，R9 Skipnext：OR R7，R8，R9 假设R4在skipnext之后不再使用，且DSUBU也不会产生异常，那么DSUBU可以移到分支指令之前，不须遵守控制相关，也不影响程序结果的正确性。

4.2 指令的动态调度 静态调度：在出现数据相关时，为了消除或者减少流水线空转，编译器确定并分离出程序中存在相关的指令，然后进行指令调度，并对代码进行优化。 在编译期间静态完成，通过把相关的指令拉开距离来减少可能产生的停顿。优化通常是面向特定体系结构的。 动态调度：通过硬件重新调度相关的指令的执行顺序，减少冲突导致的处理器空转。 在程序的执行过程中动态完成，能够处理在编译时情况不明的相关（比如涉及到存储器访问的相关），以增加硬件复杂性为代价简轻编译器的负担（软件硬化）。

4.2.1 动态调度的基本思想 1. 前述流水线的局限性 指令必须按序流出和执行，一旦一条指令受阻，其后的指令都将停顿。 考虑下面一段代码： 4.2 指令的动态调度 4.2.1 动态调度的基本思想 1. 前述流水线的局限性 指令必须按序流出和执行，一旦一条指令受阻，其后的指令都将停顿。 考虑下面一段代码： 指令i DIV.D F4，F0，F2 指令i+1 SUB.D F10，F4，F6 指令i+2 ADD.D F12，F6，F14 指令i+1与指令i关于F4相关，导致流水线停顿。指令i+2与前两条指令都无关，但也因指令i+1而受阻。 解决办法：允许乱序执行与乱序完成

RO IS 2. 在前面的基本流水线中：ID段负责检测结构冲突与数据冲突。为了支持乱序执行，我们将5段流水线的ID段再分为两个阶段. 4.2 指令的动态调度 2. 在前面的基本流水线中：ID段负责检测结构冲突与数据冲突。为了支持乱序执行，我们将5段流水线的ID段再分为两个阶段. IS段：指令流出Issue。包括译码及检测结构冲突，如果无结构冲突，就允许指令流出。（顺序从IS进入RO） RO段：读操作数Read Operands。检测数据冲突，如果无数据冲突，就读操作数，并将指令送入EX段。（乱序从RO进入EX段） IS RO 检测结构冲突 检测数据冲突

3. 在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。 例如，考虑下面的代码 4.2 指令的动态调度 3. 在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执行就使得它们可能发生了。 例如，考虑下面的代码 DIV.D F10, F0, F2 SUB.D F10, F4, F6 ADD.D F6, F8, F14 DIV和SUB输出相关，SUB和ADD反相关，如果SUB早于DIV完成，就会使得后面使用F10的程序取到错误结果。 如果能消除这两种相关，乱序执行也不会导致WAR冲突和WAW冲突，这就需要用到寄存器换名技术。 乱序执行也会导致多条指令都处于执行状态，我们假设流水线具有多个功能部件，多条指令可同处EX段。

精确异常：当执行指令i导致发生异常时， 处理机的现场跟严格按程序顺序执行时指令i的现场相同。 4.2 指令的动态调度 4. 指令乱序完成增加了异常处理的复杂度 精确异常：当执行指令i导致发生异常时， 处理机的现场跟严格按程序顺序执行时指令i的现场相同。 不精确异常：当执行指令i导致发生异常时，处理机的现场跟严格按程序顺序执行时指令i的现场不同。 动态调度必须要保持正确的异常行为 动态调度情况下，对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行后，才允许它产生异常。 即使保持了正确的异常行为，动态调度处理机仍可能发生不精确异常。 不精确异常通常是乱序完成导致的，它使得在异常处理后难以接着继续执行程序。

4.2.2 Tomasulo算法 Robert Tomasulo发明，IBM 360/91首先采用。 4.2 指令的动态调度 4.2.2 Tomasulo算法 Robert Tomasulo发明，IBM 360/91首先采用。 核心思想：通过引入保留站（Reservation Station）和相关逻辑硬件来实现寄存器换名技术。完全消除名相关，并尽最大可能减少真数据相关引发的流水线阻塞。 每条指令根据不同的类型流出到不同的保留站中。保留站保存已流出并等待到对应的功能部件进行执行的指令及其相关信息。在一条指令流出到保留站时: 如果该指令的源操作数已经在寄存器中就绪，则将该操作数读出来保存到保留站中。 如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标识，指明将来谁会产生这个操作数。

基于Tomasulo算法的MIPS处理器浮点部件的基本结构 4.2 指令的动态调度 基于Tomasulo算法的MIPS处理器浮点部件的基本结构

浮点部件 保留站 4.2 指令的动态调度 浮点加法器：浮点加减法 浮点乘法器：浮点乘除法 浮点存储单元：浮点Load/Store 浮点加减法操作有3个保留站：ADD1，ADD2，ADD3 浮点乘除法操作有2个保留站：MULT1，MULT2 Load操作有6个Load缓冲器，每个都可看做保留站； Store操作有6个Store缓冲器，每个都可看做保留站； 每个保留站都有一个标识字段，唯一地标识了该保留站。

公共数据总线CDB（一条重要的数据通路） 4.2 指令的动态调度 公共数据总线CDB（一条重要的数据通路） 所有功能部件的计算/访存结果都是送到CDB上，由它把这些结果直接送到（广播到）各个需要该结果的地方。 CDB连到除了load缓冲器以外所有的部件入口。 在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线中，需要采用多条CDB。 浮点寄存器FP 共有16个浮点寄存器：F0，F2，F4，…，F30。 它们通过一对控制总线和数据总线连接到功能部件，并通过CDB连接到store缓冲器。 指令队列 指令部件送来的指令放入指令队列 指令队列中的指令按先进先出的顺序流出

地址部件 load缓冲器和store缓冲器 4.2 指令的动态调度 内部含有加法器，用于地址计算 存放读/写存储器的数据或地址 存放用于计算有效地址的分量Imm； 保存正在进行的load访存的目标地址，等待存储器的响应； 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。 store缓冲器的作用有3个： 保存正进行的store访存的目标地址，等待被存储数据的到达 保存要被存储的数据，直到存储部件接收。

指令执行控制是分布的。每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。 4.2 指令的动态调度 Tomasulo算法具有以下三个特点： 指令执行控制是分布的。每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。 冲突检测是分布的。计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器，使得等待这一运算结果的多个指令可以同时执行。 寄存器换名是通过保留站和流出逻辑来共同完成的。指令流出到保留站后，其操作数寄存器号要么换成了数据本身，要么换成了保留站的标识，不再与寄存器有关系，消除了名相关导致的冲突。

使用Tomasulo算法的流水线需3段，各段中指令执行步骤如下： 4.2 指令的动态调度 使用Tomasulo算法的流水线需3段，各段中指令执行步骤如下： 流出 流出条件：指令进入指令队列的头部，且有对应该指令的空闲保留站，则指令可从指令队列的头部流出到保留站(设为r)。 流出动作：缓冲操作数，完成换名，预约目标寄存器。 执行 （流水中没有待执行的分支指令） 浮点指令执行条件：两个操作数就绪，无论r是否成为保留站的头部，且计算部件就绪（乱序计算）。 LD/ST指令执行条件：地址操作数就绪，且r成为缓冲器队列的头部，且存储器部件就绪（按序访存，避免访存冲突）。 浮点指令执行动作：计算浮点操作，产生计算结果 LD/ST指令执行动作：计算有效地址，并将有效地址放入r，LD数据 写结果 浮点或LD指令写结果条件： r执行结束，且CDB就绪 浮点或LD指令写结果动作：将计算结果放到CDB上，送给所有等待该结果的寄存器和保留站（包括store缓冲器）, 释放产生结果的保留站。 ST指令写结果条件：r执行结束，且待存数据就绪 ST指令写结果动作：ST数据，释放产生结果的保留站。

指令执行状态表：每条2项={指令字段,状态字段} 寄存器状态表：每条2项={寄存器号,保留站预约字段} 4.2 指令的动态调度 Tomasulo算法需要的各信息表 指令执行状态表：每条2项={指令字段,状态字段} 寄存器状态表：每条2项={寄存器号,保留站预约字段} 保留站状态表：每条8项={L,B,O,Vj,Vk,Qj,Qk,A} L：label，保留站标识字段。 B：Busy，保留站或缓冲单元是否“忙”。 O：Operation，流出指令的操作码。 A：地址计算前存Imm，地址计算后存有效地址。 Qj，Qk：将要产生源操作数的保留站号。 Vj，Vk：源操作数的数值。 注：仅LD和ST缓冲器有A字段，ST缓冲器另有待存数字段V； Qj对应rs，为0表示Vj就绪；Qk对应rt，为0表示Vk就绪；Qi的预约字段为0表示该寄存器中的数据就绪。

符号说明： i,j,k rs rd rt j k i rs rt j k rs rt j k MUL.D F4，F0，F2 4.2 指令的动态调度 符号说明： i,j,k 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

完整的Tomasulo算法（1/5）：浮点指令的流出 4.2 指令的动态调度 完整的Tomasulo算法（1/5）：浮点指令的流出 if （Qi[rs] = 0） { RS[r].Vj = Regs[rs]； RS[r].Qj = 0 }； // 若第一操作数就绪，取到保留站r的Vj，置Qj为0，表示Vj操作数就绪 else { RS[r].Qj = Qi[rs] } // 若第一操作数没有就绪，把将产生该操作数的保留站编号放入r的Qj。 if （Qi[rt] = 0） { RS[r].Vk = Regs[rt]； RS[r].Qk = 0 } // 若第二操作数就绪，取到保留站r的Vk，置Qk为0，表示Vk操作数就绪 Else { RS[r].Qk = Qi[rt] } //若第二操作数没有就绪，把将产生该操作数的保留站编号放入r的Qk。 RS[r].Busy = yes；RS[r].Op = Op；//置当前保留站为“忙”并记录操作码 Qi[rd] = r； //把当前保留站的编号r放入rd对应寄存器状态表项，以便rd将来接收结果。

完整的Tomasulo算法（2/5）：LD/ST指令的流出 4.2 指令的动态调度 完整的Tomasulo算法（2/5）：LD/ST指令的流出 if （Qi[rs] = 0） {RS[r].Vj = Regs[rs]；RS[r].Qj = 0 }； //若第一操作数就绪，取到保留站r的Vj，置Qj为0，表示Vj操作数就绪 else {RS[r].Qj = Qi[rs] } //若第一操作数没有就绪，就把将产生该操作数的保留站编号放入r的Qj。 RS[r].Busy = yes； // 置当前缓冲器单元为“忙” RS[r].Op = Op； //设置操作码 RS[r].A = Imm； // 把符号位扩展后的偏移量放入当前保留站的A 对于load指令： Qi[rt] = r；// 把当前缓冲器的编号r放入rt对应寄存器状态表项，以便rt将来接收数据 对于store指令： if （Qi[rt] = 0） {RS[r].Vk = Regs[rt]；RS[r].Qk = 0 }； // 若待存数据就绪，从R[rt]取到r的Vk，置Qk为0，表示Vk操作数就绪 else {RS[r].Qk = Qi[rt] } // 若待存数据没有就绪，把将产生该数据的保留站编号放入r的Qk。

完整的Tomasulo算法（3/5）：指令的执行 4.2 指令的动态调度 完整的Tomasulo算法（3/5）：指令的执行 对于浮点指令： Result = RS[r].Vj op RS[r].Vk； //计算浮点操作 对于ST指令： RS[r].A = RS[r].Vj + RS[r].A； //计算有效地址 对于LD指令： Result = Mem[RS[r].A] ； //访存读数据

完整的Tomasulo算法（4/5）：浮点与LD指令的写结果 4.2 指令的动态调度 完整的Tomasulo算法（4/5）：浮点与LD指令的写结果 任意x （if（Qi[x] = r） { Regs[x] = result；Qi[x] = 0 }； // 对于任何正在等该结果的浮点寄存器x， 向x写入结果，把x的预约状态置为数据就绪 任意x （if（RS[x].Qj = r） {RS[x].Vj = result；RS[x].Qj = 0 }； // 对于任何正在等该结果作为第一操作数的保留站x， 向x的Vj写入结果，置Qj为0，表示x的Vj操作数就绪 任意x （if（RS[x].Qk = r） {RS[x].Vk = result；RS[x].Qk = 0 }； // 对于任何正在等该结果作为第二操作数的保留站x， 向x的Vk写入结果，置Qk为0，表示x的Vk操作数就绪 RS[r].Busy = no； // 释放当前保留站，将之置为空闲状态。

完整的Tomasulo算法（5/5）：ST指令的写结果 4.2 指令的动态调度 完整的Tomasulo算法（5/5）：ST指令的写结果 Mem[RS[r].A] = RS[r].Vk // 数据写入存储器，地址由store缓冲器单元的A字段给出。 RS[r].Busy = no； //释放当前缓冲器单元，将之置为空闲状态。 算法结束，下面讲2个例子

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 说明：在没有采用多指令流出技术的情况下，其实每个周期只能流出一条指令。不过本题做了个简单假设：假设第一条指令执行前，所有指令都已流出。

1. 所有指令都流出后的状态如下 4.2 指令的动态调度 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi Mul1 LD2 对应变量 状态 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 0：流出 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 1. 所有指令都流出后的状态如下 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi Mul1 LD2 LD1 Add2 Add1 Mul2 名称 保留站 B Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A LD1 Y LD (R2) 34 LD2 (R3) 45 Add1 SUBD Add2 ADDD Add3 Mul1 MULTD （F4） Mul2 DIVD

2. 执行中状态变化如下 4.2 指令的动态调度 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi Mul1 LD2 Add2 对应变量 流出 执行 写结果 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 1 2 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 3 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 2. 执行中状态变化如下 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi Mul1 LD2 Add2 Add1 Mul2 名称 保留站 B Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A LD1 N LD (R2) 34 34+(R2) LD2 Y (R3) 45 45+(R3) Add1 SUBD MEM[34+(R2)] LD1 0 Add2 ADDD Add3 Mul1 MULTD (F4) Mul2 DIVD LD10

4.2 指令的动态调度 例4.2 对于下述指令序列，考虑指令执行的延迟，给出MUL.D指令准备写结果时，Tomasulo算法所用的各信息表中的内容。 L.D F6,34（R2） 1个时钟周期 L.D F2,45（R3） 1个时钟周期 MUL.D F0,F2,F4 10个时钟周期 SUB.D F8,F2,F6 2个时钟周期 DIV.D F10,F0,F6 40个时钟周期 ADD.D F6,F8,F2 2个时钟周期 说明：在没有采用多指令流出技术的情况下，其实每个周期只能流出一条指令。不过本题做了个简单假设：假设第一条指令执行前，所有指令都已流出。实际上，Mul指令要执行10个时钟周期，即使不假设所有指令已流出，在Mul结束时所有指令已流出。

1. 由例4.1可知，所有指令都流出后的状态如下 4.2 指令的动态调度 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi 对应变量 状态 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 0：流出 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi Mul1 LD2 Add2 Add1 Mul2 名称 保留站 B Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A LD1 Y LD (R2) 34 LD2 (R3) 45 Add1 SUBD Add2 ADDD Add3 Mul1 MULTD （F4） Mul2 DIVD

2.执行中状态变化的时钟周期如下 4.2 指令的动态调度 从上表可以看出：指令是乱序执行的。 对应变量 流出 执行 写结果 延迟 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 1 2 1个周期 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 3 4 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 5 15 10个周期 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 7 2个周期 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 16 56 40个周期 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 8 10 从上表可以看出：指令是乱序执行的。 Mul准备写结果，就是第14周期尾，此时表中红色部分均为空。下页图解第1到14周期的指令动作。第5周期浮点加和浮点乘开始执行，第8周期ADD开始执行，在下页图中没有用彩色体现，也不需要体现。

4.2 指令的动态调度 名称 保留站 Busy Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A(Imm) Load1 对应变量 流出 执行 写结果 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 1 2 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 3 4 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 5 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 7 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 8 10 域 寄存器状态 F0 F2 F4 F6 F8 F10 … Qi Mul1 Load2 Add2 Add1 Mul2 名称 保留站 Busy Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A(Imm) Load1 Y->N LD (R2) 34->34+(R2) Load2 (R3) 45->45+(R3) Add1 SUBD Mem[45+(R3)] Mem[34+(R2)] Load2->0 Load1->0 Add2 ADDD SubResult Add1->0 Add3 Mul1 Y MULTD (F4) Mul2 DIVD

4.3 动态分支预测技术 CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突 由上述公式可知，如果每个时钟周期能够流出多条指令，则能够通过减小CPI理想达到减小CPI流水线的目的。然而，处理器一个时钟周期能够流出多条指令要受限于控制相关： 在n-流出的处理机中，遇到分支指令的可能性增加了n倍。要给处理器连续提供指令，就需要预测分支的结果。 根据Amdahl定律可知，机器的CPI越小，控制相关对性能的影响就越大。解释见下页

具有控制相关关系的指令必须串行执行，不具有控制相关关系的指令可以并行执行。控制相关的相对影响p用下式计算： 4.3 动态分支预测技术 具有控制相关关系的指令必须串行执行，不具有控制相关关系的指令可以并行执行。控制相关的相对影响p用下式计算： CPI并越小，p越大，即“机器的CPI越小，控制相关对性能的影响就越大”

4.3 动态分支预测技术 分支预测 前面已经讲过处理分支的基本方法，如总是预测分支成功，总是预测分支失败，延迟分支，分支取消等。不过这些方法都是静态技术，不能利用程序运行时的动态信息。 本节介绍通过硬件技术，对程序运行时的分支行为进行动态预测，提前对分支操作做出处理。利用动态信息，提高预测的准确度和适应性。 分支预测的有效性不仅取决于准确度，还取决于猜对和猜错情况下的分支开销。分支开销的决定因素：流水线的结构、预测的方法和猜错后的恢复策略等。 主要介绍三种方法 分支预测缓冲（Branch Prediction Buffer，BPB） 分支目标缓冲（Branch Target Buffer，BTB） 指令前瞻执行（Instruction Speculation，IS）

1. 分支预测缓冲技术简介 4.3.1 分支预测缓冲 BPB 最简单的动态分支预测方法 4.3 动态分支预测技术 4.3.1 分支预测缓冲 BPB 1. 分支预测缓冲技术简介 最简单的动态分支预测方法 适用情况：判定分支是否成功所需的时间大于确定分支目标地址所需的时间。 用BPB来记录分支指令最近一次或几次的执行情况（成功或不成功），并据此执行数据进行动态预测 BPB可以跟分支指令一起存放在指令Cache中，也可以用一个专门的硬件来实现，还可以放在内存中。

4.3 动态分支预测技术 2. 分支预测缓冲技术步骤。 分支结果预测。当分支指令达到ID段，读取BPB中的信息进行预测。如果BPB中预测位为“1”，则预测当前分支成功；否则，预测当前分支不成功。 预测状态修改。如果当前分支成功，则按照分支成功规则修改预测位；否则，按照分支失败规则修改预测位。 现场恢复。若预测正确，就继续处理后续指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

4.3 动态分支预测技术 3. BPB采用1个二进制预测位 最简单的BPB。 1位分支预测的状态转换如下所示： 例子见下页

例题4.3 一个循环体N共循环10次（分支成功9次，失败1次）。假设使用1位分支预测，那么分支预测的准确性是多少？ 4.3 动态分支预测技术 例题4.3 一个循环体N共循环10次（分支成功9次，失败1次）。假设使用1位分支预测，那么分支预测的准确性是多少？ 解：这种预测方式将会在第一次和最后一次循环中出现预测错误： （1）循环体N最后一次预测错误是不可避免的，因为最后一次之前所有的9次循环中，分支都是成功的。 （2）第一次预测错误，是源于前面执行的另一个循环体M，M的最后一次循环导致预测位被置0，该预测值保持到了循环体N的第一次预测。 （3）因此，尽管分支成功的比例率是90%，但分支预测的准确性为80%（两次不正确，8次正确）。 解毕。

4. 1位分支预测机制的缺点与改进 缺点：只要预测出错，往往是连续两次预测错误，而不是一次。 改进：采用多个预测位。 4.3 动态分支预测技术 4. 1位分支预测机制的缺点与改进 缺点：只要预测出错，往往是连续两次预测错误，而不是一次。 改进：采用多个预测位。 采用n位计数器，则计数器的值在0到2n-1之间： 当计数器的值大于或等于最大值的一半时，则预测下一次分支成功；否则预测下一次分支不成功。 当分支成功时计数器的值加1，不成功时减1。 研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。因而大多数处理器都只采用两位分支预测。

4.3 动态分支预测技术 5. BPB采用2个二进制预测位 2位分支预测的状态转换如下所示：

例题4.4 一个循环体N共循环10次（分支成功9次，失败1次）。假设使用2位分支预测，那么分支预测的准确性是多少？ 4.3 动态分支预测技术 例题4.4 一个循环体N共循环10次（分支成功9次，失败1次）。假设使用2位分支预测，那么分支预测的准确性是多少？ 解：这种预测方式只会在最后一次循环中出现预测错误： （1）循环体N最后一次预测错误是不可避免的，因为最后一次之前所有的9次循环中，分支都是成功的。最后一次循环中预测错误，导致预测位由11变为10. （2）前面执行的另一个循环体M，M的最后一次循环导致预测位由11变为10 ，该预测值保持到了循环体N的第一次预测，10导致此次预测正确。 （3）因此，分支成功的比例率是90%，分支预测的准确性为90%（1次不正确，9次正确）。 解毕。

4.3.2 分支目标缓冲 BTB 4.3 动态分支预测技术 原理： 如果能在IF段就能获得分支后继的地址，那么分支开销可以减少为0。 方法： 当一条分支指令分支成功时，将该分支指令的地址（作为标识）及其分支成功路径上的后继指令地址绑定为一个条目存到BTB中。 IF段每次取指令，所取当前指令地址都与BTB中的保存所有条目的标识进行匹配。一旦匹配，则就认为当前指令是分支指令，且预测分支成功，并用匹配条目中的分支后继指令更新PC值。如果没有匹配，无论当前指令是否分支指令，都用PC+4更新PC值。

4.3 动态分支预测技术 1. BTB的工作过程

4.3 动态分支预测技术 2. 引入BTB后，流水线各段的工作过程

EX段删除BTB条目，分支进入MEM段，真后继进入IF段 EX段添加BTB条目，分支进入MEM段，真后继进入IF段 4.3 动态分支预测技术 3. 采用BTB后，取到的指令在各种情况下的延迟 匹配BTB? 预测 实际 延迟 备注 是 成功 不成功 2 EX段删除BTB条目，分支进入MEM段，真后继进入IF段 无 EX段添加BTB条目，分支进入MEM段，真后继进入IF段

4. BTB的进一步改进 4.3 动态分支预测技术 BTB的局限性 BTB的改进 BTB改进的好处： 仅缓存了分支成功的后继指令地址，IF段下个周期才能取出后继指令，因此不支持一个周期流出多条指令的情况。 BTB的改进 在每个BTB条目中不仅存入目标指令的地址，而且还存入一个或多个后继指令。 BTB改进的好处： 更快地获得分支目标处的指令。节省出来的时间可以消耗在BTB的检索中，这样就能够支持更大的BTB。 可以一次提供分支目标处的多条指令，支持指令多流出的处理器。 可以支持分支折叠技术（branch folding）：流水线正常处理分支指令导致后继指令等待的时间内，可以从BTB中取出指令送入流水线占据气泡，使得分支指令和非分支指令同时被执行。

5. BTB v.s. BPB 4.3 动态分支预测技术 BTB BPB 缓冲内容 分支成功路径上的 后继指令地址或后继指令 分支是否成功的预测值 分支预测 预测分支成功 预测值动态改变 作用位置 IF段 ID段

4.3.3 指令前瞻执行 IS IS的基本思想 IS的主要技术 4.3 动态分支预测技术 为克服控制相关带来延迟，允许在处理器还未判断某些指令是否能执行之前就提前执行他们。 允许指令乱序执行，但必须顺序确认。确认即判断指令是否确实应该执行，该执行则执行结果有效，否则无效。 乱序执行的结果存放在FIFO的再定序缓冲区(ROB,ReOrder Buffer)中，如果分支预测正确，缓冲区中的结果顺序确认后才能直接作用在寄存器和存储器中；如果分支预测错误，清空缓冲区；如果产生异常，清空缓冲区。 IS的主要技术 采用动态的分支预测技术来选择后续执行指令 在控制相关消除之前允许指令前瞻执行 跨基本块进行指令动态调度

IS的特点 IS的浮点部件结构 4.3 动态分支预测技术 在大多数指令前瞻正确的前提下，前瞻就可以有效地加快分支处理的速度。以大幅度提高硬件复杂性为代价。 动态地根据数据相关性来选择指令和指令的执行时间。其实质是数据流驱动运行（data-flow execution），只要操作数有效，指令就可以执行。 前瞻执行的指令产生的结果要一直到指令处于非前瞻执行状态时，才能被确认。不被确认的指令不能改变机器状态和引发异常。 IS的浮点部件结构 以采用Tomasulo算法的浮点部件结构为基础 修改Tomasulo算法的控制逻辑，写结果段分成两个子段：写结果段 + 指令确认段。 加入再定序缓冲器ROB 很容易地推广到整数寄存器和整数功能单元上。

4.3 动态分支预测技术 注： LD缓冲器和ST缓冲器，甚至所有保留站可以都合并到ROB中，原理相同。

指令执行状态表：每条2项={指令字段,状态字段} 寄存器状态表：每条3项={寄存器号,ROB预约字段,Busy} 4.3 动态分支预测技术 IS机制需要的各信息表（1/2） 指令执行状态表：每条2项={指令字段,状态字段} 寄存器状态表：每条3项={寄存器号,ROB预约字段,Busy} 保留站状态表：每条8项={L,B,O,Vj,Vk,Qj,Qk,A,Dest} L：label，保留站标识字段。 B：Busy，保留站或缓冲单元是否“忙”。 O：Operation，流出指令的操作码。 A：地址计算前存Imm，地址计算后存有效地址。 Qj，Qk：将要产生源操作数的ROB号。 Vj，Vk：源操作数的数值。 Dest：指明哪个ROB项b将接收该保留站产生的结果

IS机制需要的各信息表（2/2） 4.3 动态分支预测技术 ROB状态表：每条6项={L,B,O,Target,Value,State} L：label，ROB标识字段。 B：Busy，保留站或缓冲单元是否“忙”。 O：Operation，流出指令的操作码 分支指令（尚无分支结果的） store指令（目的地址为存储器的） 寄存器操作指令（Load指令也看成寄存器操作指令） T: Target，目的寄存器标识 RR-ALU指令：Target = R[rd] RI-ALU指令 & Load指令：Target = R[rt] Store指令：Target=MemoryAddress Value：保存前瞻执行结果，直到指令得到确认 State：标识指令是否已完成且数据已就绪 已流出/已执行/已写结果/已确认

IS机制的指令执行步骤（1/4） 4.3 动态分支预测技术 IS流出 Tomasulo流出(比较) 流出条件：指令进入指令队列的头部，且有对应该指令的空闲保留站r，且有空闲的ROB项b，则指令可从指令队列的头部流出到保留站r和ROB项b。 流出动作：缓冲操作数，完成换名（记录将会产生该操作数的ROB项标识），预约目标寄存器。分支指令的流出直接进入ROB。 If Regs[rs].B=N, r.Vj= Regs[rs]. If (Regs[rs].B==Y&&Regs[rs].rob.Value!=Null); r.Vj= Regs[rs].rob.Value; If (Regs[rs].B=Y&&Regs[rs].rob.Value==Null); r.Qj= Regs[rs].rob; Tomasulo流出(比较) 流出条件：指令进入指令队列的头部，且有对应该指令的空闲保留站，则指令可从指令队列的头部流出到保留站r。 流出动作：缓冲操作数，完成换名（记录将会产生该操作数的保留站标识），预约目标寄存器。分支指令的流出不操作任何信息表。

IS机制的指令执行步骤（2/4） 4.3 动态分支预测技术 IS执行 Tomasulo执行(比较) 浮点指令执行条件：两个操作数就绪，且计算部件空闲。 LD/ST指令执行条件：地址操作数就绪，且地址部件空闲。 浮点指令执行动作：计算浮点操作，产生计算结果 LD/ST指令执行动作：计算有效地址，并将有效地址放入r，LD数据 Tomasulo执行(比较) 浮点指令执行条件：两个操作数就绪，无论r是否为保留站的头部，且计算部件空闲。 LD/ST指令执行条件：地址操作数就绪，且r成为LD/ST缓冲器队列的头部，且地址部件空闲。

IS机制的指令执行步骤（3/4） 4.3 动态分支预测技术 IS写结果 Tomasulo写结果 (比较) 浮点或LD指令写结果条件： r执行结束，且CDB就绪 浮点或LD指令写结果动作：将计算结果[b][Data]放到CDB上，送给所有等待该结果的ROB项和保留站，释放产生结果的保留站。 ST指令写结果条件：r执行结束，且待存数据就绪 ST指令写结果动作：将待存数据写入对应该指令的ROB项，释放产生结果的保留站。 Tomasulo写结果 (比较) 浮点或LD指令写结果动作：将计算结果[r][Data]放到CDB上，送给所有等待该结果的寄存器和保留站（包括store缓冲器），释放产生结果的保留站。 ST指令写结果动作：将待存数据写入存储器, 释放产生结果的保留站。

IS机制的指令执行步骤（4/4） 4.3 动态分支预测技术 IS指令确认（ Tomasulo无此步骤） 浮点或LD指令确认条件： 该指令完成写结果，且对应的b已到达ROB队列头部。 浮点或LD指令确认动作：将计算结果从b中取出，写入目标寄存器，释放b。 ST指令确认条件：该指令完成写结果，且对应的b已到达ROB队列头部。 ST指令确认动作：将待存数据从b中取出，写入目标存储器单元，释放b。 分支指令确认条件：该指令对应的b已到达ROB队列头部。 分支指令确认动作： 猜对，则前瞻执行均有效，释放b。 猜错，则前瞻执行均无效，清空ROB和所有保留站，且用真后继指令地址更新PC，重新流出

4.3 动态分支预测技术 例4.5 对于下述指令序列，考虑指令执行的延迟，给出MUL.D指令即将确认时，IS机制所用的各信息表中的内容。 L.D F6,34（R2） 1个时钟周期 L.D F2,45（R3） 1个时钟周期 MUL.D F0,F2,F4 10个时钟周期 SUB.D F8,F2,F6 2个时钟周期 DIV.D F10,F0,F6 40个时钟周期 ADD.D F6,F8,F2 2个时钟周期

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

保留站状态表 4.3 动态分支预测技术 Label Busy Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A(Imm) 序 指令 对应变量 流出 执行 写结果 确认 14周期结束状态 1 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 2 3 已确认 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 4 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 14 15 已写结果 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 6 16 5 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 55 56 已流出，操作数已就绪 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 7 9 57 Label Busy Op Vj(rs) Vk(rt) Qj(rs) Qk(rt) A(Imm) Dest Load1 N LD b1 Load2 b2 Add1 SUBD b4 Add2 ADDD b6 Add3 Mul1 MULTD Load2的值 (F4) b3 Mul2 Y DIVD Mul1的值 Load1的值 b5 保留站状态表

ROB状态表 4.3 动态分支预测技术 Label Busy Op State Target Value b1 No 序 指令 对应变量 流出 执行 写结果 确认 14周期结束状态 1 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 2 3 已确认 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 4 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 14 15 已写结果 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 6 16 5 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 55 56 已流出，操作数已就绪 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 7 9 57 Label Busy Op State Target Value b1 No LD F6 , 34(R2) 确认 F6 MEM[(R2)+34] b2 LD F2 , 45(R3) F2 MEM[(R3)+45] b3 yes MULTD F0 , F2 , F4 写结果 F0 MulResult b4 Yes SUBD F8 , F2 , F6 F8 SubResult b5 DIVD F10 , F0 , F6 准备执行 F10 b6 ADDD F6 , F8 , F2 AddResult ROB状态表

寄存器状态表 4.3 动态分支预测技术 F0 F2 F4 F6 F8 F10 … F30 ROB b3 b2 b1 b6 b4 b5 序 指令 对应变量 流出 执行 写结果 确认 14周期结束状态 1 LD F6 , 34(R2) Rt=F6, rs=R2, Imm=34 2 3 已确认 LD F2 , 45(R3) Rt=F2, rs=R3, Imm=45 4 MULTD F0 , F2 , F4 Rd=F0, Rs=F2, Rt=F4 14 15 已写结果 SUBD F8 , F2 , F6 Rd=F8, Rs=F2, Rt=F6 6 16 5 DIVD F10 , F0 , F6 Rd=F10, Rs=F0, Rt=F6 55 56 已流出，操作数已就绪 ADDD F6 , F8 , F2 Rd=F6, Rs=F8, Rt=F2 7 9 57 寄存器状态表 F0 F2 F4 F6 F8 F10 … F30 ROB b3 b2 b1 b6 b4 b5 Busy Y N

4.4 多指令流出技术 1. 从单流出到多流出 单流出处理器每个周期只能流出一条指令，理想CPI等于1，因此实际CPI>1。 如果处理机每个周期最多流出n条指令，就称该处理机为n流出。

4.4 多指令流出技术 2. 单流出和多流出的时空图对比

3. 典型的多指令流出技术： 4.4 多指令流出技术 静态超标量（Static Superscalar） 每个时钟周期流出的指令数不固定(有上限） 采用编译器静态指令调度，顺序执行 动态超标量（Dynamic Superscalar） 采用硬件动态指令调度（Tomasulo或IS），乱序执行 超长指令字（Very Long Instruction Word） 每个时钟周期流出的指令数是固定的，它们构成一条长指令，或说是一个混合指令包，指令包中指令间的并行性是显示的。 这种处理器目前只能通过编译器静态调度。 超流水（Super Pipeline） 在每个流水段进一步实现流水，特别是IF段或IS段被分解为多个子段，使得一个段在一个周期内可以流水的处理多条指令。

4.4.1 静态超标量 4.4 多指令流出技术 典型的超标量处理器每个周期可流出1到8条指令。 指令按序流出，在流出时由硬件进行冲突检测，判断能否流出。 检测包括结构冲突和数据冲突，通常在不同的段检测。 如果没有冲突，n流出处理器每周期可以流出n条指令， 如果其中r条指令与正在运行的指令存在冲突，则该周期可以流出n-r条指令。 对n流出处理器，如果允许任意类型的指令n流出，则硬件开销过大，且利用率低。因此，通常限制同时流出的指令的类型。 举例：2流出处理器，通常每周期可以处理一条整型指令和一条浮点指令，因此每个周期最多可以处理这样的组合指令包，而不能处理2条浮点或2条整型指令。

静态超标量MIPS处理机 4.4 多指令流出技术 假设：每个时钟周期可流出 1条整型指令＋1条浮点指令 LD/ST、分支归入整型指令，浮点LD/ST虽然属于整型指令，但是也要操作浮点寄存器，如果刚好1条浮点LD/ST与一条浮点指令同时流出，两条指令都要访问浮点寄存器。 可以增设一个浮点寄存器的读/写端口以避免冲突 也可以只允许浮点LD/ST单独流出与执行 为实现双流出，IF段每周期取2条指令，ID段每周期译码2条指令，因此IR应该具有64bit(即指令Cache宽度) 由于流水线的指令宽度增加了1倍，定向路径也要增加。 编译要求指令序列按类型组合成对，且与64位边界对齐，每对中整数指令顺序在前，且严格优先流出。（一列指令编译为两列例子）

静态超标量MIPS处理机例题 下面的循环程序段如果要工作在2流出静态超标量MIPS流水线上，如何进行编译器静态调度？ 4.4 多指令流出技术 静态超标量MIPS处理机例题 下面的循环程序段如果要工作在2流出静态超标量MIPS流水线上，如何进行编译器静态调度？ For(i=1; i<=1000; i++) x[i]=x[i]+s; 假设流水线的延迟如下： 生产者指令 消费者指令 延迟时钟周期数 浮点计算 另一个浮点计算 3 浮点ST 2 浮点LD 1

解: 先把高级语言程序翻译成MIPS汇编语言代码 For(i=1; i<=1000; i++) x[i]=x[i]+s; 翻译后 4.4 多指令流出技术 解: 先把高级语言程序翻译成MIPS汇编语言代码 For(i=1; i<=1000; i++) x[i]=x[i]+s; 翻译后 Loop: LD F0,0(R1); 取一个向量元素放入F0 ADDD F4,F0,F2; 加上在F2中的标量 ST 0(R1),F4; 存结果 SUBI R1,R1,#8; 指针减少8(一个DWord) BNEZ R1,R2,Loop; R1不等于R2，转移到Loop

分支在ID段完成，因此下轮循环延迟为1个周期 4.4 多指令流出技术 根据延迟表，给出一次循环内部各汇编指令的流出时钟延迟 标号 指令 流出 备注 Loop: LD F0,0(R1); 1 浮点LD后接浮点计算，1个周期延迟 空转 2 ADDD F4,F0,F2; 3 浮点计算后接浮点ST，2个周期延迟 4 5 ST 0(R1),F4; 6 SUBI R1,R1,#8; 7 减法指令在EX开始定向，此时BNEZ已经进入ID段但当前周期错过了定向结果，因此在ID段多等一个周期读到定向结果，此时减法指令已经进入M段，因此有1个周期的定向延迟 8 BNEZ R1,R2,Loop; 9 分支在ID段完成，因此下轮循环延迟为1个周期 10

使用循环展开技术展开循环 4.4 多指令流出技术 流出 第一轮 第二轮 第三轮 第四轮 第五轮 1 LD 2 空转 3 ADDD 4 5 6 ST 7 8 9 10 11 SUBI R1,R1,#40; 12 13 BNEZ R1,R2,Loop; 14 使用循环展开技术展开循环

展开后的指令直接紧凑 4.4 多指令流出技术 不同的颜色，使用不同的寄存器 不同的颜色，使用不同的地址偏移进行LD/ST，修正后的地址： 整数指令 浮点指令 1 LD 2 3 ADDD 4 5 6 ST 7 8 9 10 11 SUBI R1,R1,#40; 12 空转 13 BNEZ R1,R2,Loop; 14 不同的颜色，使用不同的寄存器 不同的颜色，使用不同的地址偏移进行LD/ST，修正后的地址： 0(R1)， -8(R1)， -16(R1)， -24(R1)， -32(R1) 五个SUBI合并成一个 因此8*5=40 展开后的指令直接紧凑

展开后的指令进行调度 4.4 多指令流出技术 调度过程： ST的作用就是将算好的值写回存储器，因此可以向后移动，填充到空转的位置。 整数指令 浮点指令 1 LD 2 3 ADDD 4 5 6 ST 7 8 9 10 11 SUBI R1,R1,#40; 12 空转 13 BNEZ R1,R2,Loop; 14 调度过程： ST的作用就是将算好的值写回存储器，因此可以向后移动，填充到空转的位置。 注意：由于ST的地址是由基址R1计算出来的，SUBI将R1减少了40，因此一旦某个ST移到SUBI之后，要把这40加回来，才能保证ST的目标地址仍旧为指令移动前的数值。 由此，将9号指令填充12号空转，10号指令填充13号空转，9号10号新空出来的位置由后面所有的指令前移补足，结果见下页 展开后的指令进行调度

展开后的指令进行调度 4.4 多指令流出技术 调度过程： SUBI之前的LD/ST指令的地址如下： 0(R1)， -8(R1)， 整数指令 浮点指令 1 LD 2 3 ADDD 4 5 6 ST 7 8 9 SUBI R1,R1,#40; 10 11 BNEZ R1,R2,Loop; 12 调度过程： SUBI之前的LD/ST指令的地址如下： 0(R1)， -8(R1)， -16(R1)， -24(R1)， -32(R1) SUBI之后的2个ST指令的地址如下： 16(R1)， 8(R1) 展开后的指令进行调度

4.4 多指令流出技术 为什么最好是5轮循环展开？ 流出 整数指令 浮点指令 1 LD 2 3 ADDD 4 5 6 ST 7 8 SUBI R1,R1,#40; 9 10 BNEZ R1,R2,Loop; 11 如果是4轮循环展开，结果如左图所示，第5个周期有一个空转无法填满，只有大于等于5轮展开，才能填上这个空转。 如果展开超过5轮，前两个周期浮点指令的空转仍旧不能填满，而展开的循环越多，占用的寄存器总量就越大，有可能导致寄存器不足而出错。 因此，5轮最佳。

指令展开与指令调度之前，每轮循环10个周期，5轮循环需要50个时钟周期 4.4 多指令流出技术 静态指令调度的性能分析： 指令展开与指令调度之前，每轮循环10个周期，5轮循环需要50个时钟周期 指令展开与指令调度之后，5轮循环一共需要12个周期 优化加速比：50/12=4 在硬件支持2路超标量的情况下，性能提高了4倍。 解毕。

影响静态超标量MIPS性能的因素 load指令 分支指令 多流出指令的效率平衡问题 4.4 多指令流出技术 编译器编译好的指令序列中，load指令后续的3条指令都不能使用该load的结果，否则就会引起流水线停顿。 分支指令 分支指令为整数指令，因此一定为指令对的第一条指令 即使分支延迟为1个时钟周期，由于每个周期流出2条指令，因此分支指令影响的是其后的3条指令可能进入流水线后由于分支成功而被作废。 多流出指令的效率平衡问题 由于指令分布的不均衡性，导致n流出处理器的n条流水线得不到足够的指令来达到饱和。

循环展开和静态指令调度时要注意 注意分支条件的修改和控制指令的合并 注意LD/ST指令地址偏移量的修正 注意对代码的相关性分析 4.4 多指令流出技术 循环展开和静态指令调度时要注意 注意分支条件的修改和控制指令的合并 注意LD/ST指令地址偏移量的修正 注意对代码的相关性分析 不同循环迭代中使用的寄存器地址和存储器地址是不相关的 循环展开可能引入新的相关性

4.4.2 动态超标量 4.4 多指令流出技术 指令按序流出，根据保留站空闲情况判断能否流出。 对于n流出处理器，每个周期可以流出n条指令，只要对应保留站空闲。一般每个周期最多有n条指令处于执行状态。 2流出处理器的设计实例： 一个流出段，每半个周期流出一条非分支指令，则每个周期最多可以流出2条非分支指令，分支指令单独流出。 两个执行段，一个整数ALU，一个浮点ALU，最多可以接受一条整型指令和一条浮点指令同时执行，整数运算需1个周期，浮点运算需3个周期，分支指令和LD/SD指令视为整数运算指令 一个写结果段，写结果1个周期 一个确认段，指令确认1个周期 采用IS机制进行指令动态调度 指令使用ROB按序确认，保留站都合并到ROB中 无定向路径

4.4 多指令流出技术 动态超标量MIPS处理机例题 解: 下面的循环程序段如果要工作在采用IS机制的2流出动态超标量MIPS流水线上，如何进行指令的动态调度？ （假设分支预测完美，且ROB足够大） Loop: LD F0,0(R1); 取一个向量元素放入F0 ADDD F4,F0,F2; 加上在F2中的标量 ST 0(R1),F4; 存结果 SUBI R1,R1,#8; 指针减少8(一个DWord) BNEZ R1,R2,Loop; R1不等于R2，转移到Loop 解: 在这里，不能使用静态的循环展开技术。 使用指令执行状态表表示指令的调度执行过程。 表格见下页

4.4 多指令流出技术 遍数 指令 流出 执行 写结果 确认 说明 1 LD F0,0(R1); 2 3 4 流出第一条指令 ADDD F4,F0,F2; 7 8 数据相关，浮点延迟 ST 0(R1),F4; 9 数据相关 SUBI R1,R1,#8; 5 10 R1操作数已缓冲，ALU冲突 BNEZ R1,R2,Loop; 6 11 12 R1被预约导致寄存器换名，ALU冲突+数据相关 13 数据相关+ALU冲突， 浮点延迟 14 R1被预约导致寄存器换名， ALU冲突，数据相关 15 R1被预约导致寄存器换名， ALU冲突 16

动态指令调度的性能分析： 解毕。 4.4 多指令流出技术 借用上一个例题的结果，调度优化之前，每轮循环10个周期 指令动态调度之后，1轮循环一共需要11个周期,2轮循环需要11+5个周期，n轮循环需要6+5n个周期 优化加速比： p=10n/(6+5n) 在硬件支持2路超标量的情况下， n=1,p=0.91; n=2,p=1.25; n=3,p=1.43; 性能随循环次数而提高，加速比极值为2倍。 解毕。 思考：若计算过程中除法指令导致除零异常，如何处理？

影响动态超标量MIPS性能的因素 整数部件和浮点部件的工作负载不平衡，没有充分发挥出浮点部件的作用。 每轮循环中的控制开销太大。 4.4 多指令流出技术 影响动态超标量MIPS性能的因素 整数部件和浮点部件的工作负载不平衡，没有充分发挥出浮点部件的作用。 应该设法减少循环中整数型指令的数量，或者增加整数处理部件 例如增加用于计算LD/ST指令地址的加法器 每轮循环中的控制开销太大。 5条指令中有两条指令是辅助指令，应该设法减少或消除这些指令 例如再加入循环展开技术，将控制指令合并 分支指令控制相关导致的延迟 处理机必须等到分支指令的结果出来后才能开始下一轮循环首条指令的执行。

4.4 多指令流出技术 4.4.3 超长指令字 VLIW VLIW处理器是一种特殊的n流出超标量处理器。在VLIW中，每次指令调度与执行的最小单位不再是一条一条的32bit指令，而是多条可并行的指令组成的长指令，每条长指令的平均长度为一百到几百比特。 VLIW处理器中，IR含有n个操作槽，每个操作槽固定的服务于一个独立的功能部件，并控制该功能部件执行操作槽中的指令。 每个操作槽对应的功能部件类型都是暴露给编译器的，编译器据此来进行指令调度，将可以并行执行且拼接起来满足操作槽类型要求的指令拼接为长指令。静态指令调度通常和循环展开技术共同使用。 不同的长指令之间是按序流出和执行的。同一个操作槽内部的所有并行指令都是同时流出和并行执行的。一旦一条长指令不能流出，其后所有的长指令都不能流出和执行。 由于相关等原因，编译器调度优化后的长指令序列，不能保证每条长指令都能填满n个操作槽。

5流出VLIW的设计实例 一个IF段，每个周期取一条长指令 一个ID段，每个周期流出一条长指令 一个EX段，含有5个独立处理部件 4.4 多指令流出技术 5流出VLIW的设计实例 一个IF段，每个周期取一条长指令 一个ID段，每个周期流出一条长指令 一个EX段，含有5个独立处理部件 2个LSU（浮点LD/ST） 2个浮点ALU（浮点计算） 1个整数ALU（整数计算和分支）

VLIW例题 下面的循环程序段如果要工作在5流出VLIW流水线上循环展开5次，如何进行指令的编译器静态调度？ 假设： 4.4 多指令流出技术 Loop: LD F0,0(R1); 取一个向量元素放入F0 ADDD F4,F0,F2; 加上在F2中的标量 ST 0(R1),F4; 存结果 SUBI R1,R1,#8; 指针减少8(一个DWord) BNEZ R1,R2,Loop; R1不等于R2，转移到Loop 假设： 生产者指令 消费者指令 延迟时钟周期数 浮点计算 另一个浮点计算 3 浮点ST 2 浮点LD 1

根据延迟表，给出一次循环内部各汇编指令的流出时钟延迟 4.4 多指令流出技术 根据延迟表，给出一次循环内部各汇编指令的流出时钟延迟 标号 指令 流出 备注 Loop: LD F0,0(R1); 1 浮点LD后接浮点计算，1个周期延迟 空转 2 ADDD F4,F0,F2; 3 浮点计算后接浮点ST，2个周期延迟 4 5 ST 0(R1),F4; 6 SUBI R1,R1,#8; 7 浮点计算EX段尾出结果定向给BNEZ的ID段，BNEZ在ID段开始读结果时浮点计算已经进入M段，因此有1个周期的定向延迟 8 BNEZ R1,R2,Loop; 9 分支延迟为1个周期，之后才能进入下轮循环 10

使用循环展开技术展开循环 4.4 多指令流出技术 流出 第一轮 第二轮 第三轮 第四轮 第五轮 1 LD 2 空转 3 ADDD 4 5 6 ST 7 8 9 SUBI R1,R1,#40; 10 11 BNEZ R1,R2,Loop; 12 使用循环展开技术展开循环

展开后的指令直接紧凑 4.4 多指令流出技术 流出 浮点ALU LSU 整数ALU 1 LD 2 3 ADDD 4 5 6 ST 7 8 9 SUBI R1,R1,#40; 10 空转 11 BNEZ R1,R2,Loop; 12 展开后的指令直接紧凑

展开后的指令进行调度 解毕。 4.4 多指令流出技术 调度过程： 不同颜色的指令，使用不同的寄存器和不同的偏移，和前面例题相同，此略。 9-12的整数指令提前到5-8，由于所有ST都从SUBI前移到SUBI后，所以偏移量都加40. 解毕。 流出 浮点ALU LSU 整数ALU 1 LD 2 3 ADDD 4 5 SUBI R1,R1,#40; 6 ST 空转 7 BNEZ R1,R2,Loop; 8 9 10 11 12 展开后的指令进行调度

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

一台每周期分时流出两条指令的超流水线计算机的时空图 4.4 多指令流出技术 一台每周期分时流出两条指令的超流水线计算机的时空图

一个典型超流水产品(MIPS R4000)指令流水线时空图 4.4 多指令流出技术 一个典型超流水产品(MIPS R4000)指令流水线时空图

4.4 多指令流出技术

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