-
Notifications
You must be signed in to change notification settings - Fork 32
/
7、指令调度.md
207 lines (110 loc) · 7.53 KB
/
7、指令调度.md
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
### 指令调度
#### 动态分支预测
重要性
* 在n-流出的处理机中，遇到分支指令的可能性增加了n倍。
* 要给处理器连续提供指令，就需要准确地预测分支。
动态分支预测
* 动态分支预测
* 在程序运行时，根据分支指令过去的表现来预测其将来的行为。
* 如果分支行为发生了变化，预测结果也跟着改变。
* 有更好的预测准确度和适应性。
* 分支预测的有效性取决于
* 预测的准确性
* 预测正确和不正确两种情况下的分支开销
* 决定分支开销的因素：
* 流水线的结构
* 预测的方法
* 预测错误时的恢复策略等
目标与关键问题
* 采用动态分支预测技术的目标
* 预测分支是否成功
* 尽快找到分支目标地址（或指令）（避免控制相关造成流水线停顿）
* 需要解决的关键问题
* 如何记录分支的历史信息，要记录哪些信息？
* 如何根据这些信息来预测分支的去向，甚至提前取出分支目标处的指令？
预测错误时的处理方法
* 在预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。
<img src="https://img-blog.csdnimg.cn/20201225154920415.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="30%" />
分支历史表 BHT
* 概念
* Branch History Table，BHT
* 最简单的动态分支预测方法。
* 用BHT来记录分支指令最近一次或几次的执行情况（成功还是失败 ），并据此进行预测。
* 只有1个预测位的分支预测表
* 记录分支指令最近一次的历史，BHT中只需要1位二进制位（最简单）
* 2个预测位的分支预测
* 提高预测的准确度
* 研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多。
<img src="https://img-blog.csdnimg.cn/20201225154618337.png" width="40%" />
* 预测步骤
* 分支预测：当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测 。
* 若预测正确，就继续处理后续的指令，流水线没有断流。
* 否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。
* 状态修改。
* BHT的作用范围
* 判定分支是否成功所需的时间大于确定分支目标地址所需的时间。
* BHT的作用效果
* 对于SPEC89测试程序来说，具有大小为4KB 的BHT的预测准确率为82%～99%。
* 一般来说，采用4KB的BHT就可以了。
* BHT的实现
* BHT可以跟分支指令一起存放在指令Cache中。
* 也可以用一块专门的硬件来实现。
分支目标缓冲器BTB
* 概念
* 目标：将分支的开销降为 0
* 方法：分支目标缓冲将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识。
* 这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB，或者分支目标Cache （ranch-Target Cache）。
* BTB的结构
* 看成是用专门的硬件实现的一张表格。
* 表格中的每一项至少有两个字段：执行过的成功分支指令的地址（作为该表的匹配标识 ）、预测的分支目标地址
<img src="https://img-blog.csdnimg.cn/20201225154642489.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="35%" />
* BTB的操作
<img src="https://img-blog.csdnimg.cn/20201225154712193.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="67%"/>
* 各种情况下的延迟
<img src="https://img-blog.csdnimg.cn/20201225154736733.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />
* 改进BTB——提升预测准确率
* 在分支目标缓冲器中增设一个至少是两位的“分支历史表”字段
<img src="https://img-blog.csdnimg.cn/20201225154801560.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />
* 更进一步，在表中对于每条分支指令都存放若干条分支目标处的指令，就形成了分支目标指令缓冲器。
<img src="https://img-blog.csdnimg.cn/20201225154832982.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />
#### 静态指令调度
指令调度
* 找出不相关的指令序列，让它们在流水线上重叠并行执行。
* 制约编译器指令调度的因素
* 程序固有的指令级并行
* 流水线功能部件的延迟
* 部件延迟示例
<img src="https://img-blog.csdnimg.cn/20201225154856651.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />
指令调度实例
* 对于下面的源代码，转换成 MIPS 汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。
```
for (i=1000; i>0; i --)
x[i] = x[i] + s;
```
* 先把该程序翻译成MIPS 汇编语言代码
```
Loop：L.D F0, 0(R1)
ADD.D F4, F0, F2
S.D F4, 0(R1)
DADDIU R1, R1, #-8
BNE R1, R2, Loop
```
* 延迟分析
<img src="https://img-blog.csdnimg.cn/20201225154414772.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="35%" />
* 仅使用指令调度优化
<img src="https://img-blog.csdnimg.cn/20201225154505144.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />
进一步的优化：循环展开
* 把循环体的代码复制多次并按顺序排放， 然后相应调整循环的结束条件。
* 开发循环级并行的有效方法
* 示例：将例1 中的循环展开3 次得到4 个循环体，然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。假定R1 的初值为32 的倍数，即循环次数为4 的倍数。消除冗余的指令，并且不要重复使用寄存器。
* 未展开：50%是空转周期
<img src="https://img-blog.csdnimg.cn/20201225154531436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="67%"/>
* 展开且再次调度后：没有空转周期
<img src="https://img-blog.csdnimg.cn/20201225154552754.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70" width="40%" />
循环展开和指令调度的注意事项
* 保证正确性
* 注意有效性
* 使用不同的寄存器
* 删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。
* 注意对存储器数据的相关性分析
* 注意新的相关性