2.18 深度学习算法的计算与访存特征

图 1 是一个用于手写识别的深度卷积神经元网络 LeNet5 [6] ，以此为例讨论深度学习算法的计算特征。在 LeNet5 中，包括了卷积层 C1、C3、C5 和Subsampling 层 S2、S4，以及全连接层 F6。其中卷积层是最为费时的操作。

对 于 有 R 个 输 入 feature map 和 Q 个 输 出feature map 的卷积层，假设 feature map 的大小为 M×N，卷积核的大小为 K×L，则该卷积层的代码大致可以表示为如下的循环嵌套[7] （为表示简洁起见， featuremap 的循环界未考虑卷积带来的大小缩减），其中 Y 是最后生成的 feature map，X 是输入的 feature map，W 则是卷积核。

可 以 看 到， 卷 积 层 的 计 算 复 杂 度 为O(R×Q×M×N×K×L)。 以 LeNet5 的 C1 层 为 例，其卷积核为 5×5(K×L), 输入 feature map 个数为1(Q)，大小为 32×32(M×N), 输出 featuremap 个数为 6(R)。即每生成目标 featuremap 的一个元素，需要读取数组 W 和 X 分别 25 次，并进行 25 次乘法运算和加法运算。

对于给定的 m 和 n，在 k、l 变化时，访问了数组 Y 的固定元素，说明数组 Y 的访问具有较好的局部性；W 是一个较小的数组（因为卷积核通常远小于 feature map），而且对于给定的 m 和 n，变化k 和 l 时，对数组 W 的访问是连续的；对数组 X 的访问在 l 变化时是连续的，但在 k 变化时会产生不连续的内存访问，地址的间隔约为 N 个元素。

由上面分析可以看出，CNN 为代表的深度学习神经元网络中，占主要计算时间的卷积层具有较好的访存局部性特征，仅在访问输入 feature map(X)时会产生一定比例的非连续访问（约为 1/L）。整个卷积的计算由规则的多层紧嵌循环完成，循环体内也没有引入很多复杂的条件分支等。

更进一步，卷积层的计算没有任何循环间的先读后写依赖，仅对目标数组 Y 在 r、m、n 相同时存在写 - 写依赖。因此，卷积层的计算可以在 r、m、n 循环直接进行循环级并行，如果需要进一步在 q、k、l层进行并行化，可以通过规约来消除写-写依赖，进一步提高并行度。