指令级并行--计算机体系结构

参考书：《计算机体系结构量化研究方法》 作者：John L. Hennessy

一、基本概念

几乎所有处理器都使用流水线来重叠指令的执行过程，以提高性能。由于指令可以并行执行，所以指令之间可能实现的这种重叠称为指令级并行（ILP）。
ILP大体有两种不同开发方法

• 依靠硬件来帮助动态发现和开发并行
• 依靠软件技术在编译时静态发现并行

基本块：一段顺序执行代码，除入口外没有其他转入分支，除出口外没有其他转出分支
对于一段指令可能相互依赖，所以在基本块中可以开发的重叠数量可能要少于基本块的平均大小，为了提高性能，我们必须跨越多个基本块开发ILP。
提高ILP 的最简单、最常见的方法就是在循环的各次迭代之间开发并行。这种并行经常被称为循环级并行。
在开发指令级并行时，只要存在相关就必须保持程序顺序执行，共有三种不同类型的相关：

• 数据相关（也称真数据相关）
• 名称相关
• 控制相关

在介绍相关之前，先介绍几种冒险。考虑两条指令i和j,其中i指令根据程序顺序排在j的前面。可能出现的冒险有：
 RAW冒险（写后读）：j试图在i写入一个源位置之前读取它，所以j会错误的获得旧值
 WAW冒险（写后写）：j试图在i写入一个操作数之前写该操作数。
 WAR冒险（读后写）：j尝试在i读取一个目标位置之前写入该位置

1.1 数据相关

如果以下任一条件成立，则说j数据相关与指令i

• 指令i生成的结果可能会被指令j用到
• 指令j数据像关于指令k，指令k数据相关于指令i

第二个条件是说，如果两条指令之间存在第一类型的相关链，那么两条指令也是相关的。可以有以下两种不同的方法来克服相关性

• 保护相关性但避免冒险，比如代码的静态调度
• 通过转换代码来消除相关性，如寄存器重命名等

1.2 名称相关

当两条指令使用相同的寄存器或存储器位置（或名称），但与改名称相关的指令之间并没有数据流动时，就会发生名称相关。共有如下两种类型的名称相关。

• 当指令j对指令i读取的寄存器或存储器位置执行写操作时，就会在指令i和指令j之间发生反相关。为了确保指令i能够读取到正确的值，必须保持原来的顺序。即刚才介绍的读后写（WAR）冒险
• 当指令i和指令j对同一个寄存器或存储器位置执行写操作时，发生输出相关。即介绍的写后写（WAW）问题

解决方案：
改变这些指令中使用的名称，使这些指令不再冲突，那名称相关中涉及的指令就可以同时执行，或者重新排序。对于寄存器来说这一步骤更容易实现，这种操作成为寄存器重命名，可由编译器静态完成，也可由硬件动态完成。

1.3 控制相关

控制相关决定了指令i相对于分支指令的执行顺序。最简单的例子就是if语句。一般来说：控制相关会施加下述约束：

• 如果一条指令于一个分支控制相关，那就不能把这条指令移到这个分支之前，使它的执行不再受控于这个分支
• 如果一条指令于一个分支没有控制相关，那就不能把这个指令移到分支之后，使其受控于这个分支

这些前提都是针对于分支来说的，知道这条指令是分支之后，就不能随便进行代码的动态调度，即必须保持严格的程序顺序。但是，在不影响程序顺序正确性的情况下，我们希望可以执行一些此时还不应当执行的指令。从而会违反控制相关。因此，控制相关不是必须要保持的特性。但其必须满足异常行为和数据流。
异常行为是指，改变当前执行顺序的操作。如，当执行某条指令，产生中断，处理完中断服务程序时，必须能够还原到此指令的状态。意思是，不能允许此条指令之后的程序先行提交，不能允许此条指令之前的指令晚于此条指令提交。
数据流是指数据值在生成结果和使用结果之前的实际流动。换种说法，保证数据流是指要避免WAW,RAW,WAR冒险。
由于存在着多种相关，所以必须保持程序顺序。但在并行执行程序的过程中，仅在程序顺序影响程序输出时才保持程序顺序。检测和避免冒险可以确保不会打乱必要的程序顺序。

二、ILP的基本编译器技术

本节研究一些简单的编译器技术，可以用来提高处理器开发ILP的能力。这些技术对于使用静态发射或静态调度的处理器非常重要。
2.1 基本流水线调度
为了使流水线保持满载，必须找出可以在流水线中重叠的不相关指令序列，充分开发指令并行。为了避免流水线停顿，必须将相关指令与源指令的执行隔开一定的时间周期，这一间隔等于源指令的流水线延迟。编译器执行这种调度的能力即依赖于程序中可用ILP的数目，也依赖于流水线中功能单元的延迟。
举一个循环的例子
for(i=999; i>=0; i=i-1)
x[i] = x[i] + s;
把这段代码转换为MIPS汇编语言。如下所示：

LOOP:	L.D		F0,0(R1)			；F0=数组元素
		ADD.D	F4,F0,F2			；加上F2中的标量
		S.D		F4,0(R1)			；存储结果
		DADDUI	R1,R1,#-8			；指向下一位
		BNE		R1,R2,LOOP		；R1不等于R2时跳转
1
2
3
4
5

在进行任何调度的情况下，循环的执行过程如下，共花费9个时钟周期：

LOOP:	L.D		F0,0(R1)			；F0=数组元素
		停顿
		ADD.D	F4,F0,F2			；加上F2中的标量
		停顿
		停顿
		S.D		F4,0(R1)			；存储结果
		DADDUI	R1,R1,#-8			；指向下一位
		停顿
		BNE		R1,R2,LOOP		；R1不等于R2时跳转
1
2
3
4
5
6
7
8
9

可以看出，1次循环共花费了9个时钟周期。但是我们可以循环这个调度，使其只有两次停顿如下：

LOOP:	L.D		F0,0(R1)			；F0=数组元素
		DADDUI	R1,R1,#-8			；指向下一位
		ADD.D	F4,F0,F2			；加上F2中的标量
		停顿
		停顿
		S.D		F4,0(R1)			；存储结果
		BNE		R1,R2,LOOP		；R1不等于R2时跳转
1
2
3
4
5
6
7

在调度之后，循环执行所花费的时间缩短至7个周期。但是实际运算仅占用7个时钟周期中的3个（载入，求和及存储）。其余四个时钟周期包括循环开销（DADDUI和BNE）和两次停顿。为了消除4个时钟周期，需要使循环体中的运算指令数多余开销指令数。要提高运算指令相对于分支和开销指令的数目，一种简单的方案就是循环展开。即将循环体复制多次，调整循环的终止代码。
如将上述指令进行循环展开：

LOOP:	L.D		F0,0(R1)			；F0=数组元素
		ADD.D	F4,F0,F2			；加上F2中的标量
		S.D		F4,0(R1)			；存储结果
		L.D		F6,0(R1)			
		ADD.D	F8,F6,F2			
		S.D		F8,-8(R1)			
		L.D		F10,0(R1)			
		ADD.D	F12,F10,F2			
		S.D		F12,-16(R1)
		L.D		F14,0(R1)			
		ADD.D	F16,F14,F2			
		S.D		F16,-16(R1)
		DADDUI	R1,R1,#-32			；指向下一位
		BNE		R1,R2,LOOP		；R1不等于R2时跳转
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们将循环展开了四次减少了三次DADDUI以及BNE。这个循环将运行27个时钟周期。可以看到，通过调循环展开可以显著提高其性能。但相应开销为

• 增加了代码规模
• 增多了寄存器消耗

对以上代码进行调度，执行情况如下：

LOOP:	L.D		F0,0(R1)		
		L.D		F6,0(R1)	
		L.D		F10,0(R1)
		L.D		F14,0(R1)	
		ADD.D	F4,F0,F2			
		ADD.D	F8,F6,F2	
		ADD.D	F12,F10,F2	
		ADD.D	F16,F14,F2		
		S.D		F4,0(R1)		
		S.D		F8,-8(R1)	
		DADDUI	R1,R1,#-32			；避免BNE的RAW冒险
		S.D		F12,-16(R1)
		S.D		F16,-16(R1)
		BNE		R1,R2,LOOP		；R1不等于R2时跳转
1
2
3
4
5
6
7
8
9
10
11
12
13
14

展开后的循环的执行时间缩减到14个时钟周期。比简单的循环展开的性能提高了近一倍。
循环展开与调度均属于静态调度。此类技术的关键在于判断合适能够改变指令顺序以及如何改变。为了获得最终展开后的代码，必须进行如下决策和转换：
 确认循环迭代不相关，判定循环展开是有用的
 使用不同寄存器，以避免不同运算对寄存器导致的约束
 去除多余的测试和分支指令
 观察不同迭代中的载入和存储指令互不相关
 对代码进行调度，保留必要相关
要进行所有的这些变换，最关键的要求就是要理解指令之间的相关依赖关系。但是会有三种不同的效果限制循环展开：
 每次展开操作分摊的开销数目降低
 代码规模限制
 编译器限制，如寄存器紧缺等

三、分支预测

由于需要通过分支冒险和停顿来实施控制相关，所以分支会伤害流水线性能。循环展开是降低分支冒险的一种方法（因为去除了大多数分支跳转指令）。我们还可以通过预测分支的行为方式来降低分支的性能损失。综上，降低分支冒险的两种方案：

• 循环展开
• 分支预测

如图所示，一种二级自适应预测器可以记住过去n次执行该指令时的分支情况的历史，可能的2n种历史模式的每一种都有1个专用的饱和计数器，用来表示如果刚刚过去的n次执行历史是此种情况，那么根据这个饱和计数器应该预测为跳转还是不跳转。

例如，n = 2。这意味着过去的2次分支情况被保存在一个2位的移位寄存器中。因此可能有4种不同的分支历史情况：00, 01, 10, 11。其中0表示未发生跳转，1表示发生了分支跳转。现在，设计一个模式历史表（pattern history table），有4个条目，对应于2n = 4种可能的分支历史情况。4种历史情况的每一种都在模式历史表对应于一个2位饱和计数器。分支历史寄存器用于选择哪个饱和计数器供现在使用。如果分支历史寄存器是00，那么选择第一个饱和计数器；如果分支历史寄存器是11，那么选择第4个饱和计数器。
假定，例如条件跳转每隔2次执行就发生一次，即分支情况的历史序列是001001001…。在这种情况下，00对应的饱和计数器将是状态“强选择”（strongly taken），表明在两个0之后必然是出现一个1。01对应的饱和计数器将是状态“强不选择”（strongly not taken），表示在01之后必然是出现一个0。这也同样适用于10状态。而11状态从未使用，因为不可能出现连续两个1。
2级自适应预测器的一般规则是n位分支历史寄存器，可以预测在所有n周期以内出现的所有的重复序列的模式。
（n,m）预测器指从n个分支中的2n行为中进行预测，每个预测其都是单个分支的m位预测器。
局部分支预测：
局部分支预测对于每个条件跳转指令都有专用的分支历史情况缓冲区；模式历史表可以是专用的，也可以是所有条件分支共享。
全局分支预测
全局分支预测并不为每条条件跳转指令保持专有的历史记录。相反，他保持一份所有条件跳转指令共享的历史记录。优点是能识别出不同跳转指令之间的相关性。缺点是历史记录被不相关的不同条件跳转指令的执行情况稀释了；甚至历史记录没有一位是来自同一个分支指令，如果有太多的不同分支指令。这种方法必须保证历史缓冲区足够长才能发挥出性能。
竞赛预测器
竞赛预测器采用了多个预测器，通常是一个基于全局信息的预测器和一个基于局部信息的与预测其，用选择器将他们结合起来。

四、动态调度与推测

简单理解Tomasulo算法与重加载缓冲区

五、多发射和静态调度

前几节介绍了消除数据冒险和控制停顿地方法，使CPI（一条指令耗费的时钟周期数）到达理想值1。为了提高性能，我们希望将CP降低至小于1。但是我们如果每一个时钟周期只发射一条指令，那CPI的值是不可能降低到小于1的。
因此开发了多发射处理器，目标：允许一个时钟周期中发射多条指令。多发射处理器主要有以下三类

• 静态调度超标量处理器
• VLIW（超长指令字）处理器
• 动态调度超标量处理器

不同处理器采用静态调度的方式循序执行指令，动态调度处理器采用动态调度乱序执行指令。
VLIW处理器每个时钟周期发射固定数目的指令，这些指令可以设置为两种指令之一：一种格式是长指令；另一种是固定长度的指令包，指令之间有一定的并行度。VLIW处理器由编译器采用静态调度。
静态调度超标量处理器在每个时钟周期内发射的指令数目是可变的，不是固定的。但它在概念上与VLIW更接近一些，因为这种方法都依靠编译器为处理器调度代码。尽管静态调度超标量处理器的收益会随着发射宽度的增长而逐渐减少，所以静态调度超标量处理器最主要用于发射宽度较窄的情况，通常只有两条指令。下图总结了多发射的基本方法和他们的突出特征：

5.1 VLIW处理器

VLIW使用多个独立功能单元。VLIW没有尝试向这些单元发射多条独立指令，而是将多个操作包装在一个非常长的指令中。VLIW的收益会随着发射指令长度的增长而增长，所以VLIW主要用在宽发射处理器中。
我们考虑一个VLIW处理器，在上面运行5种运算的指令，这五种运算是：一个整数运算、两个浮点运算和两个存储器引用。
为了使功能单元繁忙，代码序列必须具有足够的并行度，以填充可用操作插槽。这种并行是通过展开循环和调度单个更大型循环体中的代码而展开的。举个简单的例子，现需要将循环x[i] = x[i] + s展开。VLIW执行情况如下：

执行情况如上所示，该循环被展开后形成了循环体的7个副本，消除了所有停顿，运行了9个时钟周期，生成了7个结果。
但是VLIW模块仍然有相当多的局限：
1） 静态调度增大了代码的大小
2） 只要指令未被填满，那些没有用到的功能单元都会在指令编码时变为多余的位
3） 没有冒险检测硬件，所有的功能单元都必须保持同步
4） 二进制代码的兼容性

5.2 以动态调度、多发射和推测来开发ILP

在动态调度处理器中，每个时钟周期发射多条指令都非常复杂，原因很简单，这些指令之间可能存在相关性。因此必须为这些并行指令更新控制表；否则，这些控制表中可能会出现错误，或者会丢失相关性。
在动态调度处理器中，已经采用两种方法在每个时钟周期内发射多条指令，这两种方法都基于这样一个事实：要在每个时钟周期中发射多条指令，其关键在于保留站的分配和流水线控制表的更新。两种方法如下：

• 在一个时钟周期的一半时间运行这一步骤，从而可以在一个时钟周期内运行两条指令
• 构建必要的逻辑，一次处理两条或者多条指令，包括指令之间可能存在的相关性。

第一种方法仅适应两条指令发射，无法处理多条指令发射。这两种方法每个时钟周期都会发射新的指令，所以必须能够分配保留站，并更新流水线表，使下一个时钟周期进行的相关指令发射能够利用更新后的信息。
下图给出了一种情境下的发射逻辑

该图并没有显示指令发射逻辑，这在稍后将会介绍到。
为了实现多发射的动态调度，必须做到：
 为可能在下一个发射包中发射的每条指令指定保留站和重排序缓冲区。
 分析发射包中指令之间的所有相关
 如果包中的一条指令依赖于包中的先前指令，则使用指定的重排序缓冲区编号来更新相关指令的保留表

六、用于指令传送和推测的高级技术

在高性能流水线中，特别是在多发射流水线中，仅仅很好的预测分支还不够；实际上还得能够提交高带宽的指令流。多发射处理器需要每个时钟周期提取的平均指令数至少等于平均吞吐量。当然，提取这些指令需要有足够宽的路径能够连向指令缓存，但最重要的部分还是分支的处理。在本节中先讨论两种处理分支的办法，然后讨论现在处理器如何将指令预测和预取功能结合在一起。

6.1 分支目标缓冲区

分支预测有两种情况：

• 检测到分支，预测程序计数器PC
• 未检测到分支，该干嘛干嘛

如果检测到分支，需要预测下一个程序技术去PC应当是什么，如果预测正确，就可以将分支代价将为0。于是，就需要一个分支预测缓存，用以存放分支下一条指令的预测地址，这一个缓存被称为分支目标缓冲区或分支目标缓存。如图所示：

需要注意的是，我们只需要在分支目标缓冲区中存储预测选中的分支，而不用存储非分支的一般指令。因为未被选中的分支应当直接提取下一条指令。如果预测正确，就不存在分支延迟；否则，至少存在两个时钟周期的代价。下图使分支目标缓冲区中处理指令时涉及的步骤。

分支目标的一种变体使存储一个或多个目标指令，用于作为预测目标地址的补充或替代。这一变体有两个好处。第一，它允许分支目标缓冲区访问花费的时间长于连续两次指令提取之间的时间，从而可能允许采用更大型的分支目标缓冲区。第二，通过缓存实际目标指令可以让我们一种称为分支折合的优化方法。其可以实现0时钟周期的无条件分支，也有可能实现0时钟周期的分支条件。

6.2集成指令提取单元

为了满足多发射处理器的要求，进来的设计人员选择实现了一个集成指令提取单元，作为独立的自主单元，为流水线的其余部分提供指令。这是因为：由于多发射的复杂性，不能再将取指过程视为简单的单一流水线。
最近的设计已经开始使用集成了多种功能单元的集成指令提取单元，包括以下功能：
1） 集成分支预测：分支预测器变为指令提起单元的组成部分，它持续预测分支
2） 指令预取：为了在每个时钟周期内提交多条指令，指令提取单元可能需要提取指令。
3） 指令存储器访问与缓存：在每个时钟周期提取多条指令时会遇到不同的复杂性，包括：提取多条指令可能需要访问多个缓存行。

6.3 推测：实现问题与扩展

ROB(重排序缓冲区)的一种替代方法时明确使用更大的物理寄存器集，并与寄存器重命名方法结合在一起。在Tomasulo算法中，在执行的任意时刻，体系结构可见的寄存器都包含在寄存器集和保留站的某一个组合中。在添加了推测功能后，寄存器值还会临时保存在TOB中。在任一情况下，如果处理器在一段时间内没有发射新指令，所有现有指令都会 提交，寄存器值将出现在寄存器堆中，寄存器堆直接与在体系结构中可见的寄存器相对应。
扩展后的寄存器取代了ROB的发部分功能；只需要一个队列来确保循序完成指令。在指令的发射期间，一种重命名过程会将体系结构寄存器的名称映射到扩展寄存器堆中的物理寄存器编号，为目的地分配一个新的未使用寄存器。在提交指令时重命名表被永久更新。
与ROB相比，重命名方法的一个优点时简化了指令的提交过程，它只需要两个简单操作：

• 记录体系结构寄存器编号与物理寄存器编号之间的映射不再是推测结果
• 释放所有用于保存体系结构寄存器旧值的物理寄存器

但是在释放之前必须知道它不在与体系结构寄存器相对应，而且该物理寄存器的所有使用都已完成。
动态调度超标量的关键复杂性瓶颈仍然在于所发射的指令包中包含相关性的情景。在采用寄存器重命名发射指令时，所部署的策略可以类似于采用重排序缓冲区进行发射时的策略，如下
1） 发射逻辑预先为整个发射包保留足够的物理寄存器
2） 发射逻辑判断包中存在的相关性
3） 如果一条指令依赖于该发射包排列在前的某条指令，那么将使用在其中存放结果的预留物理寄存器来为发射指令更新信息

6.4 值推测

值推测尝试预测一条指令可能生成的值。当然，值预测的成功率非常有限。
不过有种比较简单的与值预测相关的较早思想已经得到了应用，那就是地址别名预测。地址别名预测用来预测两个存储指令或者一个载入指令与一个存储指令是否引用同一个存储器地址。如果这样两条指令没有应用一个地址，那就可以放心地交换他们的顺序。否则，就必须等待。

七、多线程

多线程是向硬件展示更多并行的主要技术。尽管使用ILP来提高性能有很大优势：他对编程人员适度透明。但是在很多种情况下，ILP会受到很大的局限或者难以开发，主要的局限性有以下三点：
1） 访问存储器的WAW和WAR冒险：这一研究通过寄存器重命名消除了WAW和WAR冒险，但却没有消除存储器使用中的冒险。
2） 不必要的相关：有无数个寄存器时，就可以消除真寄存器数据相关之外的所有数据相关。但是由于递归或代码生成约定而造成的相关仍然会引入一些不必要的真数据相关
3） 克服数据流限制：如果值预测的精度很高，那就可能克服数据流限制。但目前为止，没有一种现实预测方案来显著提高ILP。显然完美的数据预测可以得到高效的无限并行，因为每个指令的每个值都可能提前预测得出。
另外，当指令发射率处于合理范围时，那些到达存储器或片外缓存的缺失不太可能通过可用ILP隐藏。由于人们试图通过更多的ILP来应对很长的存储器停顿时，效果非常有限。
多线程技术支持多个线程以重叠的方式共享单个处理器的功能单元。与之相对的是，开发线程级并行TLP的更一般方法是使用多处理器，它同时平行运行多个独立线程。但是多线程不会像多处理器那样复制整个处理器。而是在一组线程之间共享处理器核心的大多数功能，仅复制私有状态，比如寄存器和程序计数器。
要复制处理器核心中每个线程的状态，就要为每个线程创建独立的寄存器堆、独立的PC和独立的页表。当然，硬件必须支持对不同线程进行较快速的修改；具体来说：线程切换的效率应当远远高于进程切换，后者通常需要上百个到数千个时钟周期。实现多线程的硬件方法主要有三种。
1） 细粒度多线程：每个时钟周期在多线程之间进行一次切换，多个线程的指令执行过程交织在一起。好处是它能隐藏因为长短停顿的所导致的吞吐量损失。主要不足是他会减缓个体线程的执行程度
2） 粗粒度多线程：其设计目的就是用来作为细粒度的替代选项。粗粒度多线程仅发生在成本较高的停顿时才切换线程。粗粒度多线程有个严重的不足：克服吞吐量损失的能力非常有限，特别是由于较短停顿导致的损失
3） 同时多线程（SMT）：利用线程级并行来隐藏处理器中的长延迟事件，从而提高功能单元的利用率。SMT的关键在于认识到通过寄存器重命名和动态调度可以执行来自独立线程的多个指令，而不用考虑这些指令之间的相关性；这些相关性留给动态调度功能来处理。
下面是这些方法应用在一个超标量处理器功能单元执行槽的表现情况：

小结：