现代处理器体系结构-指令集并行_块指令集 并行思想

指令集并行

概念

开发ILP的方法可以分为两大类：（ILP指令级并行）

• 主要基于硬件的动态开发方法
• 软件静态开发方法

流水线处理机实际CPI

• 理想流水线的cpi加上各类停顿的时钟周期数：
  • CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突
• 理想CPI是衡量流水线最高性能的指标
• IPC：每个时钟周期完成指令条数

基本程序块：一串连续的代码除了入口和出口 以外，没有其他的分支指令和转入点

• 程序平均每4～7条指令就会有一个分支

相关与指令级并行

相关与流水线冲突

• 相关：两条指令之间存在某种依赖关系。
  • 如果两条指令相关，则它们就有可能不能在流水线中重叠执行或者只能部分 重叠执行。
• 相关有3种类型
  • 数据相关（也称真数据相关）
  • 名相关
  • 控制相关

数据相关

对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立， 则称指令j与指令i数据相关。

• 指令j使用指令i产生的结果；
• 指令j与指令k数据相关，而指令k又与指令i数据相关。

数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者。

• 如果两条指令之间有数据相关，那么它们就不能同时执行或是完全重叠执行
• 同时执行这些指令会造成正在流水的处理机检测到这种冲突并插入暂停，从 而减少甚至取消指令之间的重叠
• 指令序列中存在的数据相关反映出产生该指令序列的程序源代码的相关关系

相关性是程序的一个特性， 是否一个相关会导致实际的冲突，是否该冲突会造成暂停， 这是流水线结构的基本特性。

数据相关性会限制可以开发的指令级并行性

解决方法：

• 保持相关关系但避免冲突

  • 对代码进行调度是保持相关关系并避免冲突常用的一个最基本方法

• 通过变换代码来消除相关关系

数据相关的检测：

• 当数据的流动是经过寄存器时，相关的检测比较直观和容易
• 当数据的流动是经过存储器时，检测比较复杂。
  • 相同形式的地址其有效地址未必相同；
  • 形式不同的地址其有效地址却可能相同。

名相关

名：指令所访问的寄存器或存储器单元的名称。

如果两条指令使用相同的名，但是它们之间并没 有数据流动，则称这两条指令存在名相关。

指令j与指令i之间的名相关有两种：

反相关

如果指令j写的名与指令i读的名相同，则称指令i和j发生了反相关

• 必须保证指令的原来顺序，以确保i能读到正确的值。

输出相关

如果指令j和指令i写相同的名，则称指令i和j发生了输出相关。

• 操作顺序必须得到保证，以使最后写入的值得以保存

名相关的两条指令之间并没有数据的传送。如果一条指令中的名改变了，并不影响另外一条指令的执行。

换名技术

• 通过改变指令中操作数的名来消除名相关。
• 既可以用编译器静态实现，也可以用硬件动态完成。

数据冲突

根据指令在流水线中要保留的读访问和写访问的顺序，可以将数据冲突 分为3种类型。

考虑两条指令i和j ，且i在j之前进入流水线， 可能发生的数据冲突有：

• 写后读冲突（RAW）
  • 在 i 写入之前，j 先去读。 j 读出的内容是错误的。
  • 这是最常见的一种数据冲突，它对应于真数据相关。
• 写后写冲突（WAW）
  • 在 i 写入之前，j 先写。 最后写入的结果是 i 的。错误！
  • 这种冲突对应于输出相关。
• 读后写冲突（WAR）
  • 在 i 读之前，j 先写。 i 读出的内容是错误的！
  • 由反相关引起。

控制相关

控制相关是指由分支指令引起的相关。

• 为了保证程序应有的执行顺序，必须严格按控制相 关确定的顺序执行。

对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和 异常行为。

• 保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变 程序中异常的发生情况。弱化为：指令执行顺序的改变不能导致程序中发生新的异常。

• 数据流：指数据值从其产生者指令到其消费者指令的 实际流动。

指令的动态调度

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

动态调度的优点：

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

动态调度的基本思想

流水线局限性

到目前为止我们所使用流水线的最大的局限性:

• 指令是按序流出和按序执行的
• 考虑下面一段代码：
  • DIV.D F4，F0，F2
  • ADD.D F10，F4，F6
  • SUB.D F12，F6，F14
  • ADD.D指令与DIV.D指令关于F4相关，导致流水线停顿。 SUB.D指令与流水线中的任何指令都没有关系，但也因此受阻。
• 为了使上述指令序列中的SUB.D指令能继续执行下去，必须把指令流出 的工作拆分为两步：
  • 检测结构冲突
  • 等待数据冲突消失
  • 只要检测到没有结构冲突，就可以让指令流出。并且流出后的指令 一旦其操作数就绪就可以立即执行

乱序执行

• 指令的执行顺序与程序顺序不相同
• 指令的完成也是乱序完成的

为了支持乱序执行，我们将5段流水线的译码阶段再分为两个阶段：

• 流出（Issue，IS）：指令译码，检查是否存在结构冲突。 （in-order issue)
• 读操作数（Read Operands，RO）：等待数据冲突消失，然后读操作数。 (out of order execution)

在前述5段流水线中，是不会发生WAR冲突和WAW冲突的。但乱序执 行就使得它们可能发生了。

• 可以通过使用寄存器重命名来消除。

指令乱序完成带来的最大问题:

• 异常处理比较复杂 （精确异常处理、不精确异常处理）
• 动态调度的处理机要保持正确的异常行为。对于一条会产生异常的指令来说，只有当处理机确切地知道该指令将被执行时，才 允许它产生异常

记分牌动态调度算法

基本思想

• 用一个称为记分牌的硬件实现了对指令的动态调度
• 该硬件中维护着3张表，分别用于记录指令的执行状态、功能部件状态、 寄存器状态以及数据相关关系等。
• 它把前述5段流水线中的译码段ID分解成了两个段：流出和读操作数，以 避免当某条指令在ID段被停顿时挡住后面无关指令的流动。

记分牌的目标：在没有结构冲突时，尽可能早地执行没有数据冲突的指 令，实现每个时钟周期执行一条指令。

要发挥指令乱序执行的好处，必须有多条指令同时处于执行阶段。

采用了记分牌的MIPS处理器的基本结构

• 每条指令都要经过记分牌
• 记分牌负责相关检测并控制指令的流出和执行。

执行过程

每条指令的执行过程分为4段 （主要看浮点操作数，因而不考虑涉及访问内存的 阶段）

• 流出
  • 如果当前流出指令所需的功能部件空闲，并且所有其他正在执行的指令的 目的寄存器与该指令的不同，记分牌就向功能部件流出该指令，并修改记分牌 内部的记录表。
  • 解决了结构冲突与WAW冲突
• 读操作数
  • 记分牌监测源操作数的可用性，如果数据可用，它就通知功能部件从寄存器中读 出源操作数并开始执行。
  • 动态地解决了RAW冲突，并导致指令可能乱序开始执行。
• 执行
  • 取到操作数后，功能部件开始执行。当产生出结果后，就通知记分牌它已经完成 执行。 在浮点流水线中，这一段可能要占用多个时钟周期。
• 写结果
  • 记分牌一旦知道执行部件完成了执行，就检测是否存在WAR冲突。如果不存在，或 者原有的WAR冲突已消失，记分牌就通知功能部件把结果写入目的寄存器，并释放该 指令使用的所有资源。

如果检测到WAR冲突，就不允许该指令将结果写到目的寄存器。这发生在以 下情况：

• 前面的某条指令（按顺序流出）还没有读取操作数；而且：其中某个源操作数寄存器 与本指令的目的寄存器相同。
• 在这种情况下，记分牌必须等待，直到该冲突消失。

记分牌

记分牌中记录的信息由3部分构成

• 指令状态表：记录正在执行的各条指令已经进入到了哪一段。
• 功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由以下9个 字段组成：
  • Busy：忙标志，指出功能部件是否忙。初值为“no”；
  • Op：该功能部件正在执行或将要执行的操作
  • Fi：目的寄存器编号
  • Fj，Fk：源寄存器编号
  • Qj，Qk：指出向源寄存器Fj、Fk写数据的功能部件 ；
  • Rj，Rk：标志位，为“yes”表示Fj，Fk中的操作数就绪且还未被取走。否则就被 置为“no”
• 结果寄存器状态表Result：每个寄存器在该表中有一项，用于指出哪个功能部件（编号） 将把结果写入该寄存器。
  • 如果当前正在运行的指令都不以它为目的寄存器，则其相应项置为“no”。
  • Result各项的初值为“no”（全0）

例题

具体算法

约定：

• FU：表示当前指令所要用的功能部件；
• D：目的寄存器的名称；
• S1、S2：源操作数寄存器的名称；
• Op：要进行的操作；
• Fj[FU]：功能部件FU的Fj字段（其他字段依此类推）；
• Result[D]：结果寄存器状态表中与寄存器D相对应的内容。其中存放的是将把结 果写入寄存器D的功能部件的名称。

指令流出

进入条件：
not Busy[FU] & not Result[D]；// 功能部件空闲且没有 //写后写（WAW）冲突。
计分牌内容修改：
Busy[FU]←yes； // 把当前指令的相关信息填入功能部件状态表。
Op[FU]←Op； // 记录操作码。
Fi[FU]←D； // 记录目的寄存器编号。
Fj[FU]←S1； // 记录第一个源寄存器编号。
Fk[FU]←S2； // 记录第二个源寄存器编号。
Qj[FU]←Result[S1]； // 记录将产生第一个源操作数的部件。
Qk[FU]←Result[S2]； // 记录将产生第二个源操作数的部件。
Rj[FU]←not Qj[FU]； // 置第一个源操作数是否可用的标志。
如果Qj[FU]为“no”，就表示没有操作部件要写S1，数据可用。
置Rj[FU]为“yes”。否则置Rj[FU]为“no”。
Rk[FU]←not Qk[FU]；// 置第二个源操作数是否可用的标志。
Result[D]←FU； // D是当前指令的目的寄存器。功能部件FU将把结果写入D。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

读操作数

进入条件：
Rj[FU] & Rk[FU]；// 两个源操作数都已就绪。
计分牌内容修改：
Rj[FU]←no； // 已经读走了就绪的第一个源操作数。
Rk[FU]←no； // 已经读走了就绪的第二个源操作数。
Qj[FU]←0； // 不再等待其他FU的计算结果
Qk[FU]←0；
1
2
3
4
5
6
7

执行

结束条件：
功能部件操作结束。
1
2

写结果

进入条件：
任意f((Fj[f]不等于Fi[FU] or Rj[f]=no)
& (Fk[f]不等于Fi[FU] or Rk[f]=no))；// 不存在WAR冲突。
计分牌内容修改：
任意f(if Qj[f]=FU then Rj[f]←yes)； // 如果有指令在等待该结果（作为第一源操
作数），则将其Rj置为“yes”，表示数据可用。
任意f(if Qk[f]=FU then Rk[f]←yes)； // 如果有指令在等待该结果（作为第二源操
作数），则将其Rk置为“yes”，表示数据可用。
Result(Fi[FU])←0； // 释放目的寄存器Fi[FU]。
Busy[FU]=no； // 释放功能部件FU。
1
2
3
4
5
6
7
8
9
10

记分牌性能受限

• 程序代码中可开发的并行性，即是否存在可以并行执行的不相关的指 令
• 记分牌的容量。
• 功能部件的数目和种类。功能部件的总数决定了结构冲突的严重程度。
• 反相关和输出相关。它们引起计分牌中更多的WAR和WAW冲突

Tomasulo算法

核心思想：

• 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突 的可能性减少到最小；
• 通过寄存器换名来消除WAR冲突和WAW冲突。

保留站（reservation station）

每个保留站中保存一条已经流出并等待到本功能部件执行 的指令（相关信息）。

包括：操作码、操作数以及用于检测和解决冲突的信息：

• 在一条指令流出到保留站的时候，如果该指令的源操作数已经在寄存器中就绪，则 将之取到该保留站中。
• 如果操作数还没有计算出来，则在该保留站中记录将产生这个操作数的保留站的标 识。

浮点加法器有3个保留站：ADD1，ADD2，ADD3

浮点乘法器有两个保留站：MULT1，MULT

每个保留站都有一个标识字段，唯一地标识了该保留站。

公共数据总线CDB

• 所有功能部件的计算结果都是送到CDB上，由它把这些结果直接送到（播送到） 各个需要该结果的地方。
• 在具有多个执行部件且采用多流出（即每个时钟周期流出多条指令）的流水线 中，需要采用多条CDB。

load缓冲器和store缓冲器

• 存放读/写存储器的数据或地址
• load缓冲器的作用有3个：
  • 存放用于计算有效地址的分量；
  • 记录正在进行的load访存，等待存储器的响应；
  • 保存已经完成了的load的结果（即从存储器取来的数据），等待CDB传输。
• store缓冲器的作用有3个：
  • 存放用于计算有效地址的分量；
  • 保存正在进行的store访存的目标地址，该store正在等待存储数据的到达；
  • 保存该store的地址和数据，直到存储部件接收。

浮点寄存器FP

• 共有16个浮点寄存器：F0，F2，F4，…，F30。
• 它们通过一对总线连接到功能部件，并通过CDB连接到store缓冲器。

指令队列

• 指令部件送来的指令放入指令队列
• 指令队列中的指令按先进先出的顺序流出

运算部件

• 浮点加法器完成加法和减法操作
• 浮点乘法器完成乘法和除法操作

在Tomasulo算法中，寄存器换名是通过保留站和流出逻辑来共同完成的。

• 当指令流出时，如果其操作数还没有计算出来，则将该指令中相应的寄存 器号换名为将产生这个操作数的保留站的标识。
• 指令流出到保留站后，其操作数寄存器号或者换成了数据本身（如果该数 据已经就绪），或者换成了保留站的标识，不再与寄存器有关系。

Tomasulo算法具有以下两个特点：

• 冲突检测和指令执行控制是分布的
  • 每个功能部件的保留站中的信息决定了什么时候
  • 指令可以在该功能部件开始执行。
• 计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而 不用经过寄存器。

指令执行的步骤

使用Tomasulo算法的流水线需3段：

• 流出：从指令队列的头部取一条指令。
  • 如果该指令的操作所要求的保留站有空闲的，就把该指令送到该保留站（设为r）。
    • 如果其操作数在寄存器中已经就绪，就将这些操作数送入保留站r。
    • 如果其操作数还没有就绪，就把将产生该操作数的保留站的标识送入保留站r。
    • 一旦被记录的保留站完成计算，它将直接把数据送给保留站r。 （寄存器换名和对操作数进行缓冲，消除WAR冲突）
  • 完成对目标寄存器的预约工作（消除了WAW冲突）
  • 如果没有空闲的保留站，指令就不能流出。（发生了结构冲突）
• 执行
  • 当两个操作数都就绪后，本保留站就用相应的功能部件开始执行指令规定的操作。
  • load和store指令的执行需要两个步骤：
    • 计算有效地址（要等到基地址寄存器就绪）
    • 把有效地址放入load或store缓冲器
• 写结果
  • 功能部件计算完毕后，就将计算结果放到CDB上，所有等待该计算结果的寄存器和 保留站（包括store缓冲器）都同时从CDB上获得所需要的数据。

每个保留站有以下7个字段：

• Op：要对源操作数进行的操作
• Qj，Qk：将产生源操作数的保留站号
  • 等于0表示操作数已经就绪且在Vj或Vk中，或者不需要操作数。
• Vj，Vk：源操作数的值
  • 对于每一个操作数来说，V或Q字段只有一个有效。
  • 对于load来说，Vk字段用于保存偏移量。
• Busy：为“yes”表示本保留站或缓冲单元“忙”
• A：仅load和store缓冲器有该字段。开始是存放指令中的立即数字段， 地址计算后存放有效地址
• Qi：寄存器状态表
  • 每个寄存器在该表中有对应的一项，用于存放将把 结果写入该寄存器的保留站的站号。
  • 为0表示当前没有正在执行的指令要写入该寄存器， 也即该寄存器中的内容就绪。

例题

Tomasulo算法具有两个主要的优点：

• 冲突检测逻辑是分布的（通过保留站和CDB实现）
  • 如果有多条指令已经获得了一个操作数，并同时在等待同一运算结果，那么这个 结果一产生，就可以通过CDB同时播送给所有这些指令，使它们可以同时执行。
• 消除了WAW冲突和WAR冲突导致的停顿
  • 使用保留站进行寄存器换名，并且在操作数一旦就 绪就将之放入保留站。

例题

具体算法

• 各符号的意义

  • r：分配给当前指令的保留站或者缓冲器单元编号；

  • rd：目标寄存器编号；

  • rs、rt：操作数寄存器编号

  • imm：符号扩展后的立即数；

  • RS：保留站；

  • result：浮点部件或load缓冲器返回的结果；

  • Qi：寄存器状态表；

  • Regs[ ]：寄存器组；

• 与rs对应的保留站字段：Vj，Qj

• 与rt对应的保留站字段：Vk，Qk

• Qi、Qj、Qk的内容或者为0，或者是一个大于0的整数

  • Qi为0表示相应寄存器中的数据就绪。
  • Qj、Qk为0表示保留站或缓冲器单元中的Vj或Vk字 段中的数据就绪
  • 当它们为正整数时，表示相应的寄存器、保留站或 缓冲器单元正在等待结果。

• 指令流出

浮点运算指令 进入条件：有空闲保留站（设为r）
操作和状态表内容修改：
if （Qi[rs] ≠ 0） //检测第一操作数是否就绪
{ RS[r].Qj <- Qi[rs] }； //第一操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号放入当前保留站的Qj。该编号是一个大于0的整数。
else { 
	RS[r].Vj <- Regs[rs] ； //第一操作数就绪。把寄存器rs中的操作数取到当前保留站的Vj。
	RS[r].Qj <- 0  //置Qj为0，表示当前保留站的Vj中的操作数就绪。
}
if （Qi[rt] ≠ 0） // 检测第二操作数是否就绪
{
	RS[r].Qk <- Qi[rt] ； //第二操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号放入当前保留站的Qk。该编号是一个大于0的整数。
}
else { 
	RS[r].Vk <- Regs[rt] ； //第二操作数就绪。把寄存器rt中的操作数取到当前保留站的Vk。
	RS[r].Qk <- 0 // 置Qk为0，表示当前保留站的Vk中的操作数就绪。
}
RS[r].Busy <- yes； //置当前保留站为“忙”
RS[r].Op <- Op； //设置操作码
Qi[rd] <- r； // 把当前保留站的编号r放入rd所对应的寄存器状态表项，以便rd将来接收结果。



load和store指令
进入条件：缓冲器有空闲单元（设为r）
操作和状态表内容修改：
if （Qi[rs] ≠ 0） // 检测第一操作数是否就绪
{RS[r].Qj <- Qi[rs] } //第一操作数没有就绪，进行寄存器换名，即把将产生该操作数的保留站的编号存入当前缓冲器单元的Qj。
else
{RS[r].Vj <- Regs[rs]； // 第一操作数就绪，把寄存器rs中的操作数取到当前缓冲器单元的Vj
RS[r].Qj <- 0 }； // 置Qj为0，表示当前缓冲器单元的Vj中的操作数就绪。
RS[r].Busy <- yes； // 置当前缓冲器单元为“忙”
RS[r].A <- Imm； // 把符号位扩展后的偏移量放入当前缓冲器单元的A 

对于load指令：
Qi[rt] <- r； // 把当前缓冲器单元的编号r放入load指令的目标寄存器rt所对应的寄存器状态表项，以便rt将来接收所取的数据。

对于store指令：
if （Qi[rt] ≠ 0） // 检测要存储的数据是否就绪
{RS[r].Qk <- Qi[rt] } //该数据尚未就绪，进行寄存器换名，即把将产生该数据的保留站的编号放入当前缓冲器单元的Qk。
else
{RS[r].Vk <- Regs[rt]； // 该数据就绪，把它从寄存器rt取到store缓冲器单元的Vk
RS[r].Qk <- 0 }； // 置Qk为0，表示当前缓冲器单元的Vk中的数据就绪。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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]读取数据； //从存储器中读取数据
1
2
3
4
5
6
7
8
9
10
11

• 写结果

浮点运算指令和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中的操作数就绪
任意x （if（RS[x].Qk = r） // 对于任何一个正在等该结果作为第二操作数的保留站x
{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； //释放当前缓冲器单元，将之置为空闲状态。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

Tomasulo算法的缺陷是需要大量的硬件

• 需要大量高速运转的存储器件及复杂的控制逻辑，特别是每个保留站都要有一个相关联的逻辑复 杂的高速缓存
• 使用单条完整的总线（CDB），所以反过来会限制性能的提高。即使可以增加CDB，但是增加 CDB即意味着需要增加与流水线中所有硬件的连接，包括保留站

对于单发射流水线，Tomasulo算法比起编译器调度所带来的有利之处，则会少于实 现起来所需要的成本的增加

• 但是随着处理机在发射能力方面的提高及代码复杂度的增加，将使寄存器换名、动态调度、推测 执行技术变得越来越重要

对指令执行存在一个限制，如果流水中存在分支指令未完成，当前指令不能进入“ 执行“