体系结构复习 CH5 指令级并行5.1 指令级并行概念5.1.1 指令级并行
指令级并行（ILP）指通过通过流水线等技术实现多条指令同时并行执行的并行技术
实现ILP主要的方法有：
依靠硬件动态发现和开发并行依靠软件在编译时静态发现并行5.1.2 指令间相关性
指令间的相关性限制了指令级的并行度，相关性主要分为（真）数据相关、名称相关和控制相关
（1）数据相关
指令i位于指令j的前面，下面两种情况下称指令j数据相关于指令i：
指令i生成的结果可能会被指令j用到指令j数据相关于指令k，而指令k数据相关于指令j
数据相关在一定程度上限制了ILP，最常用客服相关性的方法是在不改变相关性的条件下通过指令调度消除数据冒险
（2）名称相关
当两条指令使用相同寄存器和存储器位置（称为名称），但与该名称相关的指令之间并没有数据流动，此时存在名称相关
主要分为以下两种情况（指令i位于指令j的前面）：
反相关：指令j对指令i读取的寄存器和存储器位置进行写操作时，发生反相关输出相关：指令i和指令j对相同寄存器和存储器位置进行写操作时，发生输出相关
名称相关并不是真正的数据相关，通过寄存器重命名技术来消除名称相关
（3）数据冒险
数据冒险是指指令间存在相关性并且这两条指令相聚非常接近，足以使执行期间的重叠改变相关操作数的访问顺序，数据冒险分成三类：
（4）控制相关
控制相关是指分支指令限定了指令i相对于其的执行顺序，和分支条件相关的指令必须先于分支指令执行，受控于分支指令的指令必须在分支指令后执行，不受控于分支指令的指令必须在分支指令前执行
5.2 软件方法的指令级并行——基本块内的指令级并行
基本块是指一段顺序执行的代码，除了入口处没有其他转入分支，除了出口处没有其他转出分支
考虑一下C语言代码：
for (i = 1; i <= 1000; i++) {x[i] = x[i] + s;}
其基本块对应的汇编程序为：
Loop: LDF0,0(R1)ADDD F4,F0,F2SD0(R1),F4DADDI R1,R1,#-8BNEZ R1,Loop
遵循以下指令延迟规定：
那么可以直接分析基本块汇编程序的指令周期延迟（共9个周期）：
1Loop: LDF0,0(R1)2<stall>3ADDD F4,F0,F24<stall>5<stall>6SD0(R1),F47DADDI R1,R1,#-88<stall>9BNEZ R1,Loop5.2.1 静态调度
静态调度是指通过改变指令顺序而不改变指令间数据相关来改善指令延迟，把上述R1的递减改到前面并利用延迟槽技术（设置延迟槽为1）可以让上述基本快代码压缩到6个周期完成：
1Loop: LDF0,0(R1)2DADDI R1,R1,#-83ADDD F4,F0,F24<stall>5BNEZ R1,Loop6SD8(R1),F4
说明：
DADDI让R1递减提前，那么SD中存储位置是R1+8而不是R1延迟槽是无论分支是否成功都要执行的指令5.2.2 循环展开
静态调度能够大幅提升基本快执行效率（50%），但是还有一个周期的停顿不能消除，那么由此引入另一种块内消除延迟方法——循环展开
循环展开是将循环中多个基本块展开成一个基本块从而填充stall间隙的方法
将上段基本块做4段展开，并做调度：
1Loop: LDF0,0(R1)2LDF6,-8(R1)3LDF10,-16(R1)4LDF14,-24(R1)5ADDD F4,F0,F26ADDD F8,F6,F27ADDD F12,F10,F28ADDD F16,F14,F29SD0(R1),F410SD-8(R1),F811DADDI R1,R1,#-3212SD16(R1),F1213BNEZ R1,Loop14SD8(R1),F16
平均每个次循环仅需要14/4=3.5个cycle，性能大幅增加！
5.2.3 编译器角度来看代码调度
上述最优循环展开代码调度是我们手工完成的，能够完成高效的调度是因为我们知道R1代表枚举变量，并知道R1-32前的-16(R1)和16(R1)指向的同一内存区域，但编译器确定对存储器引用却不是那么容易，如其无法确定：
同一次循环中，100(R4)和20(R6)是否相等不同次循环中，100(R4)和100(R4)是否相等5.2.4 循环间相关
上面举例不同次循环间是不相关的，但如果出现下述情况：
for (i = 1; i <= 100; i++) {A[i] = A[i] + B[i];//S1B[i+1] = C[i] + D[i];//S2}
S1和S2没有相关，但是S1依赖于前一次循环的B[i]，这种循环常不能直接并行执行，需要修改代码：
A[1] = A[1] + B[1]; for (i = 1; i <= 99; i++) {B[i+1] = C[i] + D[i];//S2A[i+1] = A[i＋1] + B[i＋1];//S1}B[101] = C[100] + D[100];5.3 硬件方法的指令级并行
之前所了解的静态调度技术存在困难，并且一旦出现无法消除的数据相关，那么流水线就会停顿，直到清除相关流水线才会继续流动
动态调度提出动态发射的思想，若流水线即将发生停顿，，硬件会动态选择后续不会违反相关性的指令发射，这也就是常说的顺序发射、乱序执行、乱序完成
动态调度有许多优点：
5.3.1 记分牌动态调度
记分牌算法把ID段分成两个步骤：
发射：译码，并检测结构相关读操作数：等到没有数据相关时读入操作数
其主要思想为，在没有结构冲突时尽可能的发射指令，若某条指令停顿则选取后续指令中与流水线正在执行和停顿的指令发射
（1）记分牌四阶段
阶段 内容
有本钱耍个性，离开睁眼闭眼看见的城市，逃离身边的纷纷扰扰，
