08.srt

1
00:00:00,000 --> 00:00:04,366
字幕生成：qiaokai 字幕校对：mkwei

2
00:00:05,800 --> 00:00:07,466
嗨大家好我是ZOMI

3
00:00:07,466 --> 00:00:08,999
今天来到AI编译器

4
00:00:09,000 --> 00:00:10,533
系列里面的前端优化

5
00:00:10,533 --> 00:00:11,533
也是图优化里面

6
00:00:11,533 --> 00:00:14,599
去讲讲公共子表达式消除

7
00:00:14,666 --> 00:00:16,699
也就是CSE

8
00:00:17,966 --> 00:00:20,566
在公共子表达式CSE这个内容里面呢

9
00:00:20,566 --> 00:00:21,733
其实是比较简单

10
00:00:21,733 --> 00:00:24,533
先来看看CSE的一个概念的定义

11
00:00:24,533 --> 00:00:26,899
接着去看看AI编译器里面的CSE

12
00:00:26,900 --> 00:00:27,933
怎么去实现的

13
00:00:27,933 --> 00:00:29,566
跟传统的有什么区别

14
00:00:31,866 --> 00:00:33,466
现在呢来展开第一个内容

15
00:00:33,466 --> 00:00:34,766
就是公共子表达式消除

16
00:00:34,766 --> 00:00:36,699
的一个概念的定义

17
00:00:36,700 --> 00:00:37,333
可以看到啊

18
00:00:37,333 --> 00:00:38,933
其实公共子表达式消除呢

19
00:00:38,933 --> 00:00:41,199
是传统编译器优化里面的一个pass

20
00:00:41,200 --> 00:00:42,000
或者其中

21
00:00:42,066 --> 00:00:42,699
一个概念

22
00:00:42,700 --> 00:00:45,366
在LLVM里面呢它其实是变成了一个pass

23
00:00:45,533 --> 00:00:48,199
那在执行这个优化的时候呢

24
00:00:48,200 --> 00:00:50,333
编译器会把多个相同的表达式呢

25
00:00:50,333 --> 00:00:52,533
替换成为一个独立的变量

26
00:00:52,533 --> 00:00:53,966
下面看一个例子

27
00:00:53,966 --> 00:00:55,566
a=b*c+g

28
00:00:55,566 --> 00:00:57,966
那d=b*c+e

29
00:00:57,966 --> 00:00:59,066
可以看到这里面呢

30
00:00:59,066 --> 00:01:00,999
有一个公共的子表达式

31
00:01:01,100 --> 00:01:02,133
b乘以c

32
00:01:02,400 --> 00:01:04,600
都有一个公共的子表达是b乘以c

33
00:01:04,600 --> 00:01:05,133
于是呢

34
00:01:05,133 --> 00:01:07,599
编译器会帮做一个替换和优化

35
00:01:07,733 --> 00:01:08,333
这里面呢

36
00:01:08,333 --> 00:01:11,099
AI编译器就会抽取一个独立的子表达式

37
00:01:11,100 --> 00:01:12,666
temp=b*c

38
00:01:12,700 --> 00:01:15,366
然后呢去做一个替换a=temp+g

39
00:01:15,366 --> 00:01:16,599
d=temp+e

40
00:01:16,700 --> 00:01:19,000
抽取出来有什么好处呢

41
00:01:19,066 --> 00:01:20,599
其实呃很明显呢

42
00:01:20,600 --> 00:01:21,866
在计算机里面呢

43
00:01:21,866 --> 00:01:23,933
抽取了这个公共子表达式出来了

44
00:01:23,933 --> 00:01:26,666
可以把计算结果呢先存起来

45
00:01:26,666 --> 00:01:28,566
避免下次的重复的开销

46
00:01:28,600 --> 00:01:29,400
所以说它可以

47
00:01:29,400 --> 00:01:32,166
降低重复计算这个表达式的开销

48
00:01:33,266 --> 00:01:35,299
如果按照上面的执行方法呢

49
00:01:35,300 --> 00:01:37,066
我会执行b乘以c一次

50
00:01:37,066 --> 00:01:39,099
然后再执行b乘以c第二次

51
00:01:39,100 --> 00:01:39,933
而这里面呢

52
00:01:39,933 --> 00:01:41,966
它只需要执行一次就可以了

53
00:01:42,900 --> 00:01:43,733
看一下

54
00:01:43,733 --> 00:01:46,466
公共子表达式消除的一个基本的原则

55
00:01:46,600 --> 00:01:49,266
执行这项公共子表达式的优化呢

56
00:01:49,266 --> 00:01:52,133
是基于表达式的定义可达性的

57
00:01:52,366 --> 00:01:53,899
而什么所谓可达性呢

58
00:01:53,900 --> 00:01:56,133
就是下面的两条定义

59
00:01:56,133 --> 00:01:57,533
那在一个表达式

60
00:01:57,533 --> 00:01:59,499
假设以b乘以c为例子呢

61
00:01:59,500 --> 00:02:01,933
在某个点p被定义为可达

62
00:02:01,933 --> 00:02:02,799
什么叫可达呢

63
00:02:02,800 --> 00:02:04,966
就是从初始的节点到点p

64
00:02:05,133 --> 00:02:07,299
每条路径到达p之前呢

65
00:02:07,300 --> 00:02:09,100
都计算过b乘以c

66
00:02:09,300 --> 00:02:11,500
而b乘以c呢被计算之后呢

67
00:02:11,500 --> 00:02:12,866
不管是b或者c呢

68
00:02:12,866 --> 00:02:15,566
到达p之前都没有被重新赋值过

69
00:02:15,666 --> 00:02:17,199
回到例子里面呢

70
00:02:17,200 --> 00:02:19,400
b乘以c这个计算完temp之后呢

71
00:02:19,400 --> 00:02:20,766
后面不管怎么用了

72
00:02:20,766 --> 00:02:23,133
b和c是没有被重新赋值的

73
00:02:23,133 --> 00:02:24,199
这一点很重要

74
00:02:24,533 --> 00:02:26,866
如果b或者c其中一个变量呢

75
00:02:26,866 --> 00:02:27,699
被重新赋值

76
00:02:27,700 --> 00:02:29,766
那这个temp的值呢就会改变了

77
00:02:29,766 --> 00:02:31,899
下面这条公式也就不成立了

78
00:02:31,933 --> 00:02:33,799
它就不是真正的可达了

79
00:02:35,600 --> 00:02:37,933
另外需要注意一点就是编译器呢

80
00:02:37,933 --> 00:02:40,366
他会去计算整个的成本收益

81
00:02:40,366 --> 00:02:42,166
去判断到底我是重复

82
00:02:42,166 --> 00:02:44,066
计算这个表达式的开销大呢

83
00:02:44,066 --> 00:02:44,499
还是

84
00:02:44,500 --> 00:02:47,166
存储这个表达式的内容的开销大呢

85
00:02:47,366 --> 00:02:50,799
如果里面存储的是一个非常大的小数

86
00:02:50,800 --> 00:02:51,566
那这个时候呢

87
00:02:51,566 --> 00:02:53,666
可能需要的存储空间会比较大

88
00:02:53,666 --> 00:02:54,099
但是呢

89
00:02:54,100 --> 00:02:56,300
如果只是简单的去做一个

90
00:02:56,300 --> 00:02:57,266
两次的计算

91
00:02:57,266 --> 00:03:00,166
可能会考虑以计算换空间

92
00:03:00,166 --> 00:03:03,066
就是我重复计算而不是把它存储起来

93
00:03:03,366 --> 00:03:04,266
这个分析呢

94
00:03:04,266 --> 00:03:06,533
需要结合寄存器等其他因素

95
00:03:06,533 --> 00:03:07,766
而传统的编译器呢

96
00:03:07,766 --> 00:03:09,866
会综合考虑这些问题

97
00:03:10,933 --> 00:03:13,133
现在来看一看最后一个principle

98
00:03:13,133 --> 00:03:14,333
就是最后一个原则

99
00:03:14,466 --> 00:03:15,499
编译器的开发者呢

100
00:03:15,500 --> 00:03:17,866
将公共子表达式消除呢分为两种

101
00:03:17,866 --> 00:03:19,999
一种是本地的公共子表达式

102
00:03:20,000 --> 00:03:22,666
另外一种是全局的公共子表达式

103
00:03:22,666 --> 00:03:24,466
之前在讲LLVM的时候呢

104
00:03:24,466 --> 00:03:26,666
优化的过程有一些是基于基本块的

105
00:03:26,666 --> 00:03:28,533
有一些是基于整个过程的

106
00:03:28,733 --> 00:03:30,299
两种的方式是不一样的

107
00:03:30,300 --> 00:03:32,166
两种的范围也不一样的

108
00:03:33,000 --> 00:03:34,966
了解完公共子表达式的定义之后呢

109
00:03:34,966 --> 00:03:36,166
现在来看一下

110
00:03:36,166 --> 00:03:37,799
它的一个具体的算法

111
00:03:37,866 --> 00:03:39,166
下面要进行一个

112
00:03:39,166 --> 00:03:40,666
公共子表达式的抽取

113
00:03:40,666 --> 00:03:43,733
x op y就是x和y进行一个计算

114
00:03:44,533 --> 00:03:45,766
会从s开始

115
00:03:45,766 --> 00:03:48,133
逆向的搜索编译器里面的IR

116
00:03:48,133 --> 00:03:51,266
找到距离s最近执行x跟y计算

117
00:03:51,333 --> 00:03:53,133
x跟y一起计算的一个语句

118
00:03:53,133 --> 00:03:55,199
建立一个临时变量u

119
00:03:55,533 --> 00:03:57,999
然后呢把步骤一找到的一个语句w

120
00:03:58,000 --> 00:03:59,000
进行一个替换

121
00:03:59,000 --> 00:04:01,866
就是x op y呢赋值给u

122
00:04:01,933 --> 00:04:04,533
而u呢存到w里面

123
00:04:04,600 --> 00:04:05,266
最后一步

124
00:04:05,266 --> 00:04:07,666
使用z等于u去替换s

125
00:04:07,666 --> 00:04:08,499
重复步骤

126
00:04:08,500 --> 00:04:09,900
一直到遍历完

127
00:04:09,900 --> 00:04:11,000
整个IR

128
00:04:11,000 --> 00:04:12,300
就完成了

129
00:04:12,300 --> 00:04:14,066
公共子表达式的替换了

130
00:04:15,000 --> 00:04:15,366
现在呢

131
00:04:15,366 --> 00:04:17,733
看看AI编译器里面的公共子表达式

132
00:04:17,733 --> 00:04:19,166
是怎么去消除的

133
00:04:19,166 --> 00:04:21,899
因为AI编译器里面的第一个输入是计算图

134
00:04:22,333 --> 00:04:24,199
它跟传统编译器呢是不一样的

135
00:04:24,266 --> 00:04:25,566
那对于公共子表达式呢

136
00:04:25,566 --> 00:04:26,866
现在只需要计算

137
00:04:26,866 --> 00:04:28,399
其中一个表达式的值

138
00:04:28,400 --> 00:04:29,733
其他的表达式的值呢

139
00:04:29,733 --> 00:04:31,699
就可以通过赋值或者读内存

140
00:04:31,700 --> 00:04:32,666
就可以得到了

141
00:04:32,666 --> 00:04:35,599
这个过程叫做公共子表达式消除

142
00:04:35,933 --> 00:04:38,166
那他作为传统编译器的手段呢

143
00:04:38,166 --> 00:04:40,133
也是可以迁移到深度学习AI编译器

144
00:04:40,133 --> 00:04:43,133
里面的现在看一看这一个例子

145
00:04:43,266 --> 00:04:45,866
假设现在我有一个数x

146
00:04:45,866 --> 00:04:48,466
然后给Op1 Op2 Op3去执行

147
00:04:48,500 --> 00:04:50,600
那这边呢也有个Op1 Op2

148
00:04:50,766 --> 00:04:53,933
可以看到呢Op1 Op2的操作是相同的

149
00:04:53,966 --> 00:04:56,333
于是呢AI编译器就会对计算图呢

150
00:04:56,333 --> 00:04:57,599
进行一个提取

151
00:04:57,600 --> 00:04:59,733
提取公共子表达式出来

152
00:04:59,733 --> 00:05:01,333
变成Op1 Op2

153
00:05:01,333 --> 00:05:01,866
然后呢

154
00:05:01,866 --> 00:05:05,333
再分发给Op3 Op4分别去执行

155
00:05:05,900 --> 00:05:07,366
从而在计算图里面呢

156
00:05:07,366 --> 00:05:09,666
搜索具有相同结构的子图

157
00:05:09,666 --> 00:05:11,366
简化整个计算图的结构

158
00:05:11,366 --> 00:05:13,399
从而减少计算的开销

159
00:05:13,400 --> 00:05:15,700
这种方式呢还是以空间换时间

160
00:05:16,600 --> 00:05:17,966
最重要的一个概念呢

161
00:05:17,966 --> 00:05:20,166
就是从寻找公共子表达式

162
00:05:20,166 --> 00:05:22,266
变成搜索相同结构的子图

163
00:05:22,266 --> 00:05:24,933
也就是鼠标所在的这句话

164
00:05:26,600 --> 00:05:27,866
接下来看一下

165
00:05:27,866 --> 00:05:29,599
它具体是怎么实现的

166
00:05:29,600 --> 00:05:30,366
一个算法呢

167
00:05:30,366 --> 00:05:31,666
其实算法很简单

168
00:05:31,666 --> 00:05:34,599
最重要的就是建立这个候选的哈希表

169
00:05:34,600 --> 00:05:36,133
就是黄色的这个

170
00:05:36,300 --> 00:05:38,500
然后呢去遍历计算图

171
00:05:38,500 --> 00:05:39,400
下面来看一下

172
00:05:39,400 --> 00:05:41,500
具体的算法是怎么实现的

173
00:05:41,533 --> 00:05:44,099
那这个算法呢可能分为步骤比较多

174
00:05:44,100 --> 00:05:44,866
文字比较多

175
00:05:44,866 --> 00:05:46,899
简单的去理解一下就好了

176
00:05:47,066 --> 00:05:47,899
算法比较简单

177
00:05:47,900 --> 00:05:49,666
但是怎么去优化这个算法

178
00:05:49,700 --> 00:05:51,733
或者找到更好的遍历方式

179
00:05:51,733 --> 00:05:54,399
可能是需要深入的去思考的

180
00:05:54,400 --> 00:05:55,166
那这个算法呢

181
00:05:55,166 --> 00:05:58,333
以一个最简单最naive的算法来看

182
00:05:58,466 --> 00:05:59,199
首先第一个呢

183
00:05:59,200 --> 00:06:01,733
输入的是一个计算图的IR

184
00:06:01,733 --> 00:06:03,099
就是Graph IR

185
00:06:04,133 --> 00:06:05,466
这个IR或者计算图呢

186
00:06:05,466 --> 00:06:07,733
是从AI框架里面去获取的

187
00:06:07,733 --> 00:06:08,999
接着呢第一步

188
00:06:09,000 --> 00:06:11,600
需要去获取逆后续节点

189
00:06:11,600 --> 00:06:12,800
就是对计算图呢

190
00:06:12,800 --> 00:06:14,533
进行一个深度优先遍历

191
00:06:14,533 --> 00:06:16,366
从根节点开始

192
00:06:16,900 --> 00:06:19,200
所以会叫做逆向后续

193
00:06:19,200 --> 00:06:21,100
那逆向后续的主要作用呢

194
00:06:21,100 --> 00:06:22,733
就是找到拓扑排序

195
00:06:23,700 --> 00:06:25,400
接着呢创建一个map

196
00:06:25,400 --> 00:06:26,200
那这个map呢

197
00:06:26,200 --> 00:06:26,900
主要是存储

198
00:06:26,900 --> 00:06:29,066
公共子表达式的候选集

199
00:06:29,066 --> 00:06:29,866
也就是

200
00:06:30,100 --> 00:06:32,866
也就是在计算图里面相同结构的子集

201
00:06:32,866 --> 00:06:35,499
接着呢去遍历步骤一得到的一个图

202
00:06:36,000 --> 00:06:37,000
从候选集里面呢

203
00:06:37,000 --> 00:06:39,166
查找有没有可使用的表达式

204
00:06:39,200 --> 00:06:39,800
那接着呢

205
00:06:39,800 --> 00:06:42,000
去遍历计算图的所有节点

206
00:06:42,000 --> 00:06:44,533
去判断是否有公共子表达式

207
00:06:44,533 --> 00:06:46,099
而在遍历的过程当中呢

208
00:06:46,100 --> 00:06:48,733
其实是去获取值点的哈希值

209
00:06:48,733 --> 00:06:51,066
然后呢去计算哈希值的key

210
00:06:51,566 --> 00:06:54,166
这个key呢主要是由节点的输出个数

211
00:06:54,166 --> 00:06:54,933
输出类型

212
00:06:54,933 --> 00:06:58,166
输出节点的ID进行组成一个哈希的key

213
00:06:58,200 --> 00:06:58,966
那这个key呢

214
00:06:58,966 --> 00:07:01,666
可以保证输入输出相同的情况下呢

215
00:07:01,666 --> 00:07:03,999
得到的哈希值都是相同的

216
00:07:04,400 --> 00:07:07,166
接着呢第四步就是记录到候选集里面

217
00:07:07,166 --> 00:07:08,266
把哈希值呢

218
00:07:08,266 --> 00:07:09,699
记录到候选集里面

219
00:07:09,700 --> 00:07:11,900
当候选集为空的时候就第一次遇到

220
00:07:11,900 --> 00:07:14,000
这种情况那直接把这个节点

221
00:07:14,000 --> 00:07:15,266
记录进去就好了

222
00:07:16,800 --> 00:07:17,666
然后第五步

223
00:07:17,666 --> 00:07:20,299
就是去判断公共子表达式呢

224
00:07:20,300 --> 00:07:22,166
就是map里面假设有了

225
00:07:22,166 --> 00:07:23,599
怎么去判断

226
00:07:24,700 --> 00:07:26,000
如果节点的输入呢

227
00:07:26,000 --> 00:07:27,500
是来自于Const的节点呢

228
00:07:27,500 --> 00:07:30,200
那可以保证输入的数据是相同的

229
00:07:30,600 --> 00:07:32,866
而输出个数的类型相同的前提下呢

230
00:07:32,866 --> 00:07:35,066
可以保证输出的结果相同

231
00:07:35,066 --> 00:07:36,066
通过这种方式呢

232
00:07:36,466 --> 00:07:39,166
可以判断是否可以复用公共子表达式

233
00:07:39,166 --> 00:07:40,066
那最后一步

234
00:07:40,066 --> 00:07:41,933
就是找到公共子表达式之后呢

235
00:07:41,933 --> 00:07:44,599
就去删除重复的节点

236
00:07:45,366 --> 00:07:47,566
记得只是删除节点

237
00:07:47,566 --> 00:07:48,699
但是呢也要把

238
00:07:48,700 --> 00:07:50,733
上一个节点跟下一个节点之间的连线

239
00:07:50,733 --> 00:07:51,999
把它连起来

240
00:07:52,000 --> 00:07:54,533
就把边把数据流给它补充起来

241
00:07:54,533 --> 00:07:56,199
不然说你说我删了个节点

242
00:07:56,200 --> 00:07:57,933
但是呢后续是断了链

243
00:07:58,366 --> 00:08:00,166
计算图呢就是不完整了

244
00:08:01,666 --> 00:08:03,166
今天内容比较简单

245
00:08:03,166 --> 00:08:05,099
主要是分享了公共子表达式消除

246
00:08:05,100 --> 00:08:05,933
在传统编译器

247
00:08:05,933 --> 00:08:07,099
里面的一个概念

248
00:08:07,100 --> 00:08:08,566
他到底是怎么消除的

249
00:08:08,566 --> 00:08:10,533
接着呢去讲了AI编译器

250
00:08:10,533 --> 00:08:12,866
里面的公共子表达式的消除

251
00:08:13,133 --> 00:08:13,599
目的呢

252
00:08:13,600 --> 00:08:15,933
是在计算图里面找到相同结构的

253
00:08:15,933 --> 00:08:19,466
子图然后对他进行一个消除优化

254
00:08:20,966 --> 00:08:22,666
卷的不行了卷的不行了

255
00:08:22,666 --> 00:08:24,366
记得一键三连加关注哦

256
00:08:24,400 --> 00:08:25,766
所有的内容都会开源

257
00:08:25,766 --> 00:08:27,599
在下面这条链接里面

258
00:08:27,966 --> 00:08:28,966
拜了个拜