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

大家好，欢迎来到IT知识分享网。

ILP instruction-level parallelism

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读取的寄存器和存储器位置进行写操作时，发生反相关(由此可能引发RAW冲突)
• 输出相关：指令i和指令j对相同寄存器和存储器位置进行写操作时，发生输出相关(由此可能引发WAW冲突)

名称相关并不是真正的数据相关，通过寄存器重命名技术来消除名称相关

（3）数据冒险

数据冒险是指指令间存在相关性并且这两条指令相聚非常接近，足以使执行期间的重叠改变相关操作数的访问顺序，数据冒险分成三类：

• RAW写后读：j在i还没写入时就读取同一位置，会读取旧值
• WAW写后写：j在i还没写入时就写入同一位置，会被i写入覆盖（存在于i指令执行时间较长，如浮点运算或乘法指令）
• WAR读后写：j在i还没读入时就写入同一位置，i错误读取新值（一般先读后写的指令集不会出现，可能情况是j提前写而i在流水线后期才读的情况）

（4）控制相关

控制相关是指分支指令限定了指令i相对于其的执行顺序，和分支条件相关的指令必须先于分支指令执行，受控于分支指令的指令必须在分支指令后执行，不受控于分支指令的指令必须在分支指令前执行

相关与冲突的区别和联系:

相关包括数据相关,名称相关和控制相关

冲突包括结构冲突,数据冲突,控制冲突

其中: 

结构冲突是由硬件资源冲突造成的

数据冲突是由数据相关和名称相关造成的

控制冲突是由控制相关造成的

 

相关是程序的固有属性,它反映了程序汇中指令之间的相互依赖关系

冲突是流水线的属性,存在相关不一定会引起冲突

 

因此,开发指令级并行可以从两方面考虑:

1. 保持相关但避免冲突的发生(如指令调度)
2. 进行代码变换直接消除相关性

5.2 软件方法的指令级并行——基本块内的指令级并行

基本块是指一段顺序执行的代码，除了入口处没有其他转入分支，除了出口处没有其他转出分支

考虑一下C语言代码：

for (i = 1; i <= 1000; i++) { x[i] = x[i] + s; }

其基本块对应的汇编程序为： 

#简化起见,假设最低地址是8 Loop: LD F0,0(R1) # R1处给F0赋值 <- ADDD F4,F0,F2 # F0+F2->F4 SD 0(R1),F4 #存储结果到F4 -> DADDI R1,R1,#-8 R1作为地址下标 BNEZ R1,Loop # R1 != 0 

遵循以下指令延迟规定：

那么可以直接分析基本块汇编程序的指令周期延迟（共9个周期）：

1Loop: LD F0,0(R1) 2 <stall> 3 ADDD F4,F0,F2 4 <stall> #由上表可知加操作需要两个停顿周期 5 <stall> 6 SD 0(R1),F4 7 DADDI R1,R1,#-8 8 <stall> 9 BNEZ R1,Loop

5.2.1 静态调度

静态调度是指通过改变指令顺序而不改变指令间数据相关来改善指令延迟，把上述R1的递减改到前面并利用延迟槽技术（设置延迟槽为1）可以让上述基本快代码压缩到6个周期完成：

1Loop: LD F0,0(R1) 2 DADDI R1,R1,#-8 3 ADDD F4,F0,F2 4 <stall> 5 BNEZ R1,Loop 6 SD 8(R1),F4

说明：

• DADDI让R1递减提前，那么SD中存储位置是R1+8而不是R1
• 延迟槽是无论分支是否成功都要执行的指令

5.2.2 循环展开

静态调度能够大幅提升基本快执行效率（50%），但是还有一个周期的停顿不能消除，那么由此引入另一种块内消除延迟方法——循环展开

循环展开是将循环中多个基本块展开成一个基本块从而填充stall间隙的方法

将上段基本块做4段展开，并做调度：

1Loop: LD F0,0(R1) 2 LD F6,-8(R1) 3 LD F10,-16(R1) 4 LD F14,-24(R1) 5 ADDD F4,F0,F2 6 ADDD F8,F6,F2 7 ADDD F12,F10,F2 8 ADDD F16,F14,F2 9 SD 0(R1),F4 10 SD -8(R1),F8 11 DADDI R1,R1,#-32 12 SD 16(R1),F12 13 BNEZ R1,Loop 14 SD 8(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]; //S1 B[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]; //S2 A[i+1] = A[i＋1] + B[i＋1]; //S1 } B[101] = C[100] + D[100];

5.2.5 循环展开和调度小结

由上例可知,通过循环展开,寄存器重命名,指令调度可以有效地开发出指令级并行,但是循环展开和指令调度需要注意以下几个问题:

1. 正确性(展开后代码要正确,如循环控制和操作数偏移量的修改)
2. 有效性(能否进行展开,不同循环体之间需要有无关性)
3. 重命名(使用不同的寄存器避免名称冲突)
4. 删除冗余指令(删除多于的测试指令和分支指令并对循环结束代码和新的循环体代码进行相应修正)
5. 特别保证载入和存储指令的不相关(load和store在不同循环体中访问的地址不相同)

循环展开的不足之处:

1. code size 增大,这可能会造成cache缺失率增大
2. reg pressure 增大,寄存器的数量可能不足导致寄存器紧缺,影响重命名

5.3 硬件方法的指令级并行

5.3.0动态分支预测

分支预测（Branch Prediction）是现代处理器用来提高CPU执行速度的一种手段, 其对程序的分支流程进行预测, 然后预先读取其中一个分支的指令并解码来减少等待译码器的时间.维基百科上对此的解释是”a strategy in computer architecture design for mitigating the costs usually associated with conditional branches, particularly branches to short sections of code.”

分支预测的方法有 静态预测 和 动态预测 两类：静态预测方法行为比较简单，如预测永远不转移、预测永远转移(jmp)、预测后向转移等等，它并不根据执行时的条件和历史信息来进行预测，因此预测的准确性不会很高；动态预测方法则根据同一条转移指令过去的转移情况来预测未来的转移情况。

由于程序中的条件分支是根据程序指令在流水线处理后的结果来执行的，所以当CPU等待指令结果时，流水线的前级电路也处于等待分支指令的空闲状态，这样必然出现时钟周期的浪费。如果CPU能在前条指令结果出来之前就预测到分支是否转移，那么就可以提前解码并执行相应的指令，这样就避免了流水线的空闲等待，也就相应提高了CPU的整体执行速度。但另一方面，一旦前条指令结果出来后证明分支预测是错误的, 也就是产生了错误的分支预测，那么就必须将已经装入流水线执行的指令和结果全部清除，然后再装入正确的指令重新处理，这样就比不进行分支预测而是等待结果再执行新指令有额外的周期消耗。

看体系结构，看了流水线，知道流水线流起来之后，就会产生hazard，然后就会对hazard进行分类，找出解决hazard的方法；然后大伙蜂拥而上，发现hazard中，对于branch hazard这部分带来的性能影响很大，根据量化书中写的，branch带来的性能影响是10%~30%，并且流水级数越长，性能影响越大，这个其实很好理解的。所以大伙就集中精力解决这个问题了。然后出现了各种方法了啊，根据书上写的，以及我的理解，对于分支指令的处理就两大类：静态的和动态的。

——————— 

常见的分支预测器: 计算机体系结构-第五章-指令级并行

https://www.zhihu.com/question/

5.3.1动态调度

之前所了解的静态调度技术存在困难，并且一旦出现无法消除的数据相关，那么流水线就会停顿，直到清除相关流水线才会继续流动

动态调度提出动态发射的思想，若流水线即将发生停顿，硬件会动态选择后续不会违反相关性的指令发射，这也就是常说的顺序发射、乱序执行、乱序完成

动态调度有许多优点：

• 对一种流水线编译的代码可以在不同流水线上高效执行，而不需要针对不同微体系结构重新编译
• 动态调度能克服编译器静态调度不能确定的相关性（上述难题）
• 允许处理器容忍一些不确定/动态的延迟，如缓存缺失带来的延迟，静态调度是无论如何也不能做到这一点的

5.3.1 记分牌动态调度

记分牌算法把ID段分成两个步骤：

• 发射：译码，并检测结构相关
• 读操作数：等到没有数据相关时读入操作数

其主要思想为，在没有结构冲突时尽可能的发射指令，若某条指令停顿则选取后续指令中与流水线正在执行和停顿的指令发射

（1）记分牌四阶段

（2）记分牌硬件部件

1.Instruction status记录正在活动的指令处于四阶段中的哪一步

2.Function unit status记录功能部件（完成运算的单元）的状态，其中每个FU有9个记录参量：

• Busy：该功能部件是否正在使用
• Op：该功能部件当前完成的操作
• Fi：目的寄存器编号
• Fj,Fk：两个源寄存器编号
• Qj,Qk：产生源操作数Fj,Fk的功能部件
• Rj,Rk：标识Fj,Fk是否就绪的标志位

3.Register result status记录哪个FU对某个寄存器是否进行写操作（还未写入），若没有该域为空

（3）动态调度算法

有了上述三个部件，就可以完成四阶段中一些查看操作，如FU是否空闲、操作数是否就绪（能否执行）、是否存在WAW等

之所以该算法称为记分牌算法，是因为这三个部件就像公示的记分牌一样，流水线中各操作都需要去查看记分牌的状态并根据执行情况在记分牌中写入相应参数信息

将四阶段和记分牌控制用伪代码的形式给出，wait util是某指令向下阶段流水的必要条件，Book keeping是该流水段执行完毕后需要记录的信息：

5.3.2 Tomasulo动态调度

另一种动态调度算法是Tomasulo动态调度算法，它和记分牌的区别主要有：

• 控制和缓存在记分牌中是集中的，Tomasulo是分布在各部件中
• Tomasulo的FU称做Reservation Station保留站（RS），RS中表示寄存器要么是寄存器值，要么是指向RS或Load Buffer（也可以看做特殊的RS）的指针；RS可以完成寄存器重命名，避免WAR、WAW，RS可以多于寄存器，实现更多编译器无法完成的优化
• Register result status中记录的结果都是RS的名字，而不是寄存器
• FU计算完毕后通过Common Data Bus（CDB）广播给所有其他RS，并修改Register result status中记录
• Tomasulo可以跨越分支！不仅仅局限于基本快内部FP操作的乱序执行

Tomasulo受限于CDB的性能，一般采用高速CDB

（1）寄存器重命名

为什么寄存器重命名能够避免WAR和WAW？事例如下：

DIVD F0,F2,F4 ADDD F6,F0,F8 SD F6,0(R1) SUBD F8,F10,F14 MULD F6,F10,F8

存在下列三个名称相关：

• SUBD的目的操作数是F8，ADDD源操作数是F8，存在WAR冒险
• MULD的目的操作数是F6，SD源的操作数是F6，存在WAR冒险
• MULD的目的操作数是F6，ADDD目的操作数是F6，存在WAW冒险

用T、S重命名寄存器，有：

DIVD F0,F2,F4 ADDD S,F0,F8 SD S,0(R1) SUBD T,F10,F14 MULD F6,F10,T

且后续F8都用T代替，那么有：

• SUBD写入T可以先于ADDD读F8，WAR冒险消除
• MULD写入F6可以在SD读入S之前，WAR冒险消除
• MULD写入F6可以在ADDD写入S之前，WAW冒险消除

（2）部件结构

1.RS的结构和记分牌算法的FU相似，因为有了寄存器重命名，它省去了F和R两个标志位：

• Busy：该RS是否正在使用
• Op：该RS当前完成的操作
• A：存放存储器地址，开始存立即数，计算出有效地址后存有效地址
• Vj,Vk：源操作数的值
• Qj,Qk：产生源操作数的RS

2.Register result status中存对某一寄存器写操作的RS名字

（3）三阶段

（4）Tomasulo流水控制

Tomasulo动态调度算法的伪代码表示如下：

1.发射阶段：

// rs、rt为源操作数 // rd为目的操作数 void issue() { if op == FP operation { wait until: RS[r].busy == false; // r是和FP Operation对应的RS编号 if RegisterStatus[rs].Qi != null { RS[r].Vj = null; RS[r].Qj = RegisterStatus[rs].Qi; } else { RS[r].Vj = Register[rs]; RS[r].Qj = null; } if RegisterStatus[rs].Qk != null { RS[r].Vk = null; RS[r].Qk = RegisterStatus[rs].Qi; } else { RS[r].Vk = Register[rs]; RS[r].Qk = null; } RS[r].busy == true; RegisterStatus[rd].Qi = r; } if op == Load or Store { wait until: RS[r].busy == false; // Load Buffer和RS相同数据结构 if RegisterStatus[rs].Qi != null { RS[r].Vj = null; RS[r].Qj = RegisterStatus[rs].Qi; } else { RS[r].Vj = Register[rs]; RS[r].Qj = null; } RS[r].A = imm; RS[r].busy = true; if op == Load { // Load only RegisterStatus[rt].Qi = r; } else { // Store only if (RegisterStatus[rd].Qi != null) {// 避免WAW RS[r].Vk = null; RS[r].Qk = RegisterStatus[rt].Qi; } else { RS[r].Vk = Register[rt]; RS[r].Qk = null; } } } } 

2.执行阶段：

void execute() { if op == FP Operation { wait until: RS[r].Qj == null && RS[r].Qk == null compute result with Operand in Vj and Vk; } if op == Load or Store { wait until: RS[r].Qj = 0 && r is head of load-store queue（每次处理队头元素） RS[r].A = RS[r].Vj + RS[r].A; if op == Load { wait until: RS[r].A写入完成 Read from Mem[RS[r].A] } } }

3.写结果阶段：

void write() { if op == FP Operation { wait until: Execution of r is complete & CDB available for all x in RegisterStatus_Index_Set par-do { // 硬件并行执行，模拟直接for循环串行模拟即可 if RegisterStatus[x].Qi == r { Register[x] = result; RegisterStatus[x].Qi = null; } } for all x in RS_Index_Set par-do { if RS[x].Qj == r { RS[x].Vj = result; RS[x].Qj = null; } if RS[x].Qk == r { RS[x].Vk = result; RS[x].Qk = null; } } RS[r].busy = false; } if op == Store { wait until: Execution of r is complete & RS[r].Qk == null Mem[RS[r].A] = RS[r].Vk; RS[r].busy = false; } }

5.3.3 Tomasulo处理循环

Tomasulo算法能够循环覆盖执行，关键点在于：

• 寄存器重命名：不同循环中处理不同的物理存储位置，寄存器重命名将寄存器表示为动态的指针，增加了寄存器的个数
• 整数部件先行：以便能够发射多个循环中操作

参考链接: 计算机体系结构-第五章-指令级并行

参考链接: 计算机体系结构-第五章-指令级并行

参考链接: https://www.zhihu.com/question//answer/

参考链接: 计算机体系结构-第五章-指令级并行