Dataflow模式对循环计算的加速效果研究
摘要
本文是计算机组织与体系结构的作业报告。我把本报告放在这里，是为了展示，当代大学生对自己一个字都看不懂的东西，还能写出来自己一个字都看不懂的报告的能力。
本报告是基于论文Interstellar: Using Halide’s Scheduling Language to Analyze DNN Accelerators，对不同的dataflow模式对循环加速效果的探究。伴随着深度神经网络（DNN）正在包括自动驾驶、人脸识别、人脸检索和图像识别在内的各领域得到更加广泛地应用，业界对DNN加速器的需求也在不断增加。而DNN对算力的要求增长非常快，远超摩尔定律所预测的CPU集成度与性能的增长速度。因此，对DNN加速器的研究是非常重要的。
Interstellar对DNN加速空间分为3个维度。本报告只研究dataflow维度的加速效果。在dataflow维度，当将各类数据放到SRAM等片上global-buffer里面，如何将片上数据传输到并行的处理单元，以及如何在处理单元之间进行最大化的共享同样需要很多技巧和策略，实际上要探索的是将哪些数据放在PE上运算，及PE运算哪些数据的问题。本报告使用C++语言，实现了3种基于dataflow模式的循环处理方式的模拟器，并研究了不同模式下，各组件在计算时所需的周期数与能量消耗，即基本目标与额外目标1。
问题介绍
问题背景
近些年来机器学习已经渗透到社会的方方面面，对日常生活产生了广泛影响。为了使得机器学习模型达到足够高的精度，常用的方法是提高模型自身的复杂度以及采用更大规模的训练数据集。然而这使得模型训练成为一个非常耗时的工作。
而根据摩尔定律对计算硬件算力增长的预测，集成电路上可容纳的元器件的数目，约每隔18-24个月便会增加一倍，性能也将提升一倍。但与此同时，机器学习的模型复杂度与数据规模的增长的速度远超过硬件的算力增长速度。
因此，研究CNN、DNN等网络的加速算法是非常重要的。提升模型训练速度对科学技术的发展会有很大的促进。除去一些机器学习领域本身的算法优化方法外（如剪枝），体系结构领域更关注更低维的加速方式，如底层硬件架构的设计。而在关注底层硬件架构的基础上，也需要把目光聚焦在上层软件层面，探索如何调度以及更好地使用底层硬件，从而最大化算力的资源使用。
目前上层软件主要根据CNN等卷积神经网络相关算法进行调度。CNN是由多个2D的input features maps（ifmaps）产生多个输出的output features maps(ofmaps)，在每一对ifmaps和ofmaps之间对应一对2D的filters，同时由于ifmaps和ofmaps是3D的，每一对均对应一对filters，所以filters实际上存在4D的张量结构，即除了每一个2D的filters之外，可以认为所有的ifmaps的一组和相同数量的filters产生一个ofmaps，而每一个ofmaps都对应一组filters。
同时，在input和output之间均作一个Nb大小的batching，则input、output和filters三者均会形成一种4D结构（2维图像结构以及1维通道channel维度和1维batch维度），如果用循环的形式表示这种框架，则为七层循环架构。具体如下图：
可以看到CNN的架构较为复杂，而所有neural network硬件的实现，均为针对这种七层循环结构进行的合理调度，使其最大化利用计算的便携性和硬件资源。
可以进行优化的3个维度分别为：
- Resource Allocation（资源配置），这是硬件层面的维度，具体如采用多少并行的PE处理单元，采用寄存器大小或SRAM缓存大小参数的设计等。该维度主要作用为提供硬件资源，为软件调度提供约束。
- Dataflow调度（On-chip），主要描述片上数据在多个单元之间流动的方式。这也是本报告详细研究的方向。
- Blocking维度（Off-chip），将DRAM迁移到SRAM里，进行片上运算，我们称为Blocking，具体研究如何将大的数据集划分为小的数据块，然后将这些数据块分别放到片上进行计算。这其中就涉及如何将数据切分成小的数据块。
Dataflow模式
在dataflow维度，当将各类数据放到SRAM等片上global-buffer里面，如何将片上数据传输到并行的处理单元，以及如何在处理单元之间进行最大化的共享同样需要很多技巧和策略。下图展示了原文中提到的几种常用的数据流传输模式。
- 最简单的adder tree结构，所有的PE在input和weight之间进行乘法运算，之后进行加和得到某一个输出结果。
- MIT的Eyeriss架构所采用的unrolling simultaneously片上算法，即将weight按行放到PE里，output每一行按列放到PE的列里，input按照对角线的形式进行传输，从而避免PE分别从global-buffer获取数据，使得数据可以在PE之间传输，减少数据读出操作。
- Google TPU所采用的方式。利用fully connected layer，将input channel和output channel分别放到PE列和PE行里，input从上到下进入PE array，output从左到右走出PE array，将其划分成systolic array。
总而言之，Dataflow解决的主要是将哪些数据放在PE上运算及PE运算哪些数据的问题。在本报告中，我实现了三种数据流传输方式，分别选择不同的循环节，将之放入PE进行并行操作。这三种分别为：$X|Y$，$F_Y|Y$与$C|K$。具体操作非常类似，我们以$X|Y$为例，实际上就是将图中的for x = 0 until X与for y = 0 until Y两个语句所表示的循环放入PE进行并行执行。因此实际上循环变为for x = 0 until X / PE.size_X与for y = 0 until Y / PE.size_Y。
基础假设
片上的网络传输没有延迟，buffer可以瞬间提供想要的数据，因此计算周期数的时候只需考虑访存数量。
硬件假设为systolic array（脉动阵列），即数据流同步流过相邻的二维阵列单元的处理器结构，一般不同方向流过不同数据。二维不同数据在同一时钟下依次输入每个处理单元，而后完成乘法并存在其寄存器中。
基本目标忽略访存的时间，在进行计算次数的计数时，只要把所有循环的轮数的乘积除以并行度（PE的数量）即可（忽略systolic array初始和结束时，可能有些PE是空的的情况）。
在计算能耗时，主要复杂的是访存时Regiester File的各种forwarding和multicast机制。在分析中我们也尽量简化。
初始参数将PE设为4*4。
对于三种dataflow mode，对数据传递进行如下假设：
$X|Y$ (Output Stationary): 读input, weight；将Output放入Regiester File中。
在multicast阶段：16个weight实际上只需要读1次，这里用到了PE的并行性。
在forwarding阶段：最底层wy走一步，只有下标最大的一列PE需要重新读input，其他可以forwading，所以实际上只需要读4次。这里面由于Register File的Size不明确，不再考虑x方向的reuse甚至只需要读1次的情况。
$C|K$ (Weight Stationary): 读output, input；将weight放入Register File中。
在multicast阶段：一步只需要读4次output, 4次input。
$F_y|Y$ (Row Stationary): 读output，input， weight
在multicast阶段: 如果依然用4*4的systolic array举例的话，一步只需要读4次output, 4次weight，7次input（可以发现output和weight multicast的方向是沿着systolic array的行或列，input是沿对角线）。
再假设：除了展开的两个维度和满足一些stationary的要求外，其他维度的顺序没有要求。但在具体实现时，我们尽量和原论文的描述一致。
理论分析
基于上一节中对模拟器在执行过程中的基本假设，本节将对三种dataflow模式下，周期数与能量消耗进一步进行详细的分析。
周期与能耗数据
由于我们假设了片上的网络传输没有延迟，因此直接将所有操作的单位执行周期设为1即可，那么每次指令执行时，只需要按照执行次数依次叠加就可以计算出总的周期数。
单位能耗按照lab的要求中所给定的设置，见下图。
下面具体分析三种dataflow的周期数与能量消耗计算方法。规定进行计算的真实代码为：
1 2 3 |
ix = ox_0 * PE.x + ox_1+wx; iy = oy_0 * PE.y + oy_1+wy; O[b][oc][ox][oy] = I[b][ic][ix][iy] * W[oc][ic][wx][wy]; |
我们将主要分析周期数，能耗与周期数类似，只不过周期数每次加1，能耗加的是该器件的单位能耗，因此只作简略叙述。在能耗分析上，我们仅当遇到并行的地方，能耗可能会与PE的SIZE有倍数关系时，再详细分析。
$X|Y$ (Output Stationary)
在实现时，batch size与channel out的循环在最外层。由于是将feature map的X与Y放到PE上去进行计算，因此对x和y的循环分别是ceil((double)pa.size_x / PE.SIZE_x 和 ceil((double) pa.size_y / PE.SIZE_y，这里使用ceil函数进行向上取整操作。
此处实际上是ox和oy的并行，因此，首先从GLB中读partial sum，因此GLB的读周期数增加PE.SIZE。接下来从memory中读一组数到GLB，由于scatter是并行的，因此scatter只需要加1。然后将partial sum写入register file，因此register file的读周期数增加1。
能量消耗类似，首先从GLB中读partial sum，因此GLB的能耗增加GLB的单位能耗*PE.SIZE。接下来从memory中读一组数到GLB，但这里虽然scatter是并行的，能耗仍然是增加PE.SIZE倍单位能耗。类似地，然后将partial sum写入register file，因此register file的能耗增加PE.SIZE倍单位能耗。
然后是ic，wx和wy的三层循环，全部都在register file中进行。GLB读weight并广播，会使GLB的读周期数和广播周期数都加1。GLB再读input并scatter，会使GLB的读周期数加PE.SIZE，并使scatter的周期数加1。接下来要将input和weight写进register file，故register file的写周期数加2。再从register file中读input，output和weight，故register file的读周期数加3。然后进行乘法、加法操作，使mac周期数加1。最后把output写回，使register file的写周期数再加1。
能量消耗类似，不同的地方在于：1. 广播时的能耗是单位能耗PE.SIZE，2. scatter时的能耗是单位能耗PE.SIZE，3. 并行读input、weight与写input、output、weight时，能耗是单位能耗PE.SIZE，4. 最后将output写回时，能耗是单位能耗PE.SIZE。
最后是从register file中读并将output写回buffer。因此register file的读周期数加1，GLB的写周期数加PE.SIZE；而能耗都加PE.SIZE。
$C|K$ (Weight Stationary)
在实现时，batch size与channel out的循环在最外层。由于是将feature map的Y与kernel的Y放到PE上去进行计算，因此对oy和wy的循环分别是ceil((double)pa.size_y / PE.SIZE_x 和 ceil((double) pa.conv_size_y / PE.SIZE_y，这里使用ceil函数进行向上取整操作。
此处实际上是ox和oy的并行，然后是ox和wx和两层循环，全部都在register file中进行。
首先有如下操作计算出每次循环执行时，周期数增加的规模：
1 2 |
int tmp_x = min(PE.SIZE_x, pa.size_y - oy * PE.SIZE_x); int tmp_y = min(PE.SIZE_y, pa.conv_size_y - wy * PE.SIZE_y); |
与从GLB中读output，weight和input，因此GLB的读周期数依次增加tmp_x，tmp_y和tmp_x+tmp_t-1。接下来从memory中读一组数到GLB，由于scatter是并行的，因此scatter只需要加3。这里的思路和1类似，然后将input，output和weight都写入register file，因此register file的读周期数增加1。每次运算，mac的周期数也加1。接下来register file中再分别读input，output和weight共3次。然后将output写回buffer，因此register file的读周期数与写周期数分别加1，GLB的写周期数加1。
能量消耗类似，不同的地方在于：1. 虽然scatter是并行的，能耗仍然是增加tmp_xtmp_y倍单位能耗，2. mac的能量消耗也需要乘tmp_xtmp_y，3. register file中的读写能量消耗是tmp_x*tmp_y倍的，4. 最后写回时，从register file中读取，其读的能量消耗需要乘以tmp_x，这是由于取的时候会成行取走；类似的，写入GLB中时，能量消耗也需要乘以其写的能量消耗也需要乘以tmp_x。
最后是从register file中读并将output写回buffer。因此register file的读周期数加1，GLB的写周期数加PE.SIZE；而能耗都加PE.SIZE。
$Fy|Y$ (Row Stationary)
在实现时，channel in与channel out的循环在最外层。且要将它们放在PE上进行执行，因此对ic和oc的循环分别是ceil((double)pa.channel_in / PE.SIZE_x 和 ceil((double) channel_out / PE.SIZE_y，这里使用ceil函数进行向上取整操作。实际上是ic和oc的并行。
接下来是对kernel的x和y进行循环。循环时，每次先从input中读取数据，因此GLB读周期数加1。然后scatter的周期数会加1，mac会加PE.Y-1倍，这是因为读的时候是按列读入。能量消耗类似，只不过GLB和scatter都会乘以PE.SIZE倍。
接下来对batch size和feature map的x与y进行循环。在此之后，会从GLB中读input，需要读PE.Y次，然后从GLB中读output，需要读PE.X次。之后仍旧是从scatter中读取input和output，所以scatter的周期数加2。再从register file中读取weight，input和output，共3次，所以register file的读周期数加3。进行一次算术运算，mac的周期数加1。运算完毕后，将input，output写回register file，但output需要写2次，因此register file的写周期数加3。最后将output写回buffer，因此register file的读周期数加1，GLB的写周期数加1。
能量消耗类似，不同的地方如下：1. 一个重要的区别是，在scatter input与output时，分别对应的是PE.X与PE.Y倍的能量消耗。2.从register file中 读weight，input和output时，能耗为PE.SIZE倍。3. 算术运算时，mac的能耗为PE.SIZE倍。4. 写回input和2遍output时，能耗为PE.SIZE倍。5. 写回buffer时，从register file中的读操作，能耗为PE.Y倍。
实验结果
本节将首先介绍实验开展的具体环境，模拟器撰写方式，以及默认参数，然后对实验结果进行分析。
实验环境
实验的执行环境如下：
- 服务器: Ubuntu Server 16.04 LTS, Kernel=4.13.0-36-generic
- CPU（中央处理器）: Intel Xeon E5-2620V3@2.4GHZ $\times$2
- Memory（内存）: 62G DRAM
模拟器实现
在实验中，我用C++代码实现了模拟器。模拟器sim函数的格式为：
1 |
result sim(para pa, PE pe, int data_flow, int RF_SIZE, int SRAM_SIZE) |
即其可传入的参数为：CNN的各项参数，PE的各项参数，所选的data flow模式编号，register file的size与SRAM的size。
其中，CNN（即para结构体）的成员变量为：
1 2 3 4 5 6 7 |
int size_x; int size_y; int channel_in; int channel_out; int conv_size_x; int conv_size_y; int batch_size; |
PE结构体的成员变量为：
1 2 3 |
int size_x; int size_y; int SIZE; |
这两者的成员变量涵盖了要求中需要实现的所有参数。
默认参数
在pa和pe的构造函数中，我们默认对各项参数设为以下数据：
1 2 |
para pa(16, 16, 64, 128, 3, 3, 4); PE pe(4, 4); |
即feature map的size为1616，卷积的kernel size为33，batch size为3，输入与输出的channel number分别为64与128，PE的大小设为4*4。实际上，这些都可以根据实验需要进行修改。
register file的size从16B到512B，对应的SRAM的size从32KB到512KB，并依此计算对应的能耗。
实验结果
详细的实验结构展示在附件re.txt中。以使用Output Stationary data flow，RF size = 16 B，SRAM size = 32KB为例，实验结果的格式如下：
———–begin data flow mode:(X, Y)———–
———–RF SIZE: 16B and SRAM SIZE: 32KB———–
Output Stationary: Cycle
MAC: 4718592
GLB read: 80478208
GLB write: 131072
memory read: 287744
memory write: 131072
register file read: 14163968
register file write: 14163968
scatter: 4726784
broadcast: 4718592
Output Stationary: Energy
MAC: 5.66231e+06
GLB read: 4.82869e+08
GLB write: 786432
memory read: 1.72646e+06
memory write: 786432
register file read: 6.7987e+06
register file write: 6.7987e+06
scatter: 1.51257e+10
broadcast: 2.64241e+06
———–end data flow mode:(X, Y)———–
附件中给出了详细的涉及各个组件的周期数与能量消耗的实验结果。
实验结果与理论分析保持一致。
结论
在本次lab中，我主要实现了文献中所介绍的3种data flow模式对CNN的七层循环计算方式的影响，并自己实现了3种不同的循环展开撰写方式，体会了这些不同模式对计算组件的执行周期数与能量消耗的影响。
由于lab中的许多要求与论文中都不是很详细，因此本次lab的完成基于我个人的很多理解与假设。可能我的想法仍有欠缺之处，但我的确从中学到了不少关于CNN计算优化的知识，并更大程度上理解了PE的并行计算对循环计算的优势。
附录
实验代码（C++）：
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 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 |
``` #include |