2019, Vol. 45
图 1
表 1
b. 上海理工大学 光电信息与计算机工程学院, 上海 200093
b. School of Optical-Electrical and Computer Engineering, University of Shanghai for Science and Technology, Shanghai 200093, China
在计算机视觉、模式识别以及人工智能领域, 深度学习得到广泛应用, 其效果与性能优于传统方法, 如HOG(Histogram of Oriented Gradients)[1]、SIFT(Scale-Invariant Feature Transform)[2]等。在深度学习算法与模型中, 卷积神经网络(Convolutional Neural Network, CNN)[3-5]是重要的组成部分。CNN无需对图像进行复杂的前期预处理而直接输入原始图像, 且在如下3个方面具有明显优势:局部感受野, 有助于神经元从原始图像中提取基本信息, 包括边缘和角点信息; 权值共享, 局部感受野通过权值共享减少了神经网络需要训练的参数数目, 在不影响精度的情况下能够简化计算过程; 空间或时间子采样, 通过子采样可以降低特征映射的分辨率, 并输出对移位和失真的敏感度[6]。与传统方法相比, CNN在实际应用中面临的主要挑战是需要花费较多的检测时间, 其中, 卷积计算占据很大比例。因此, 对CNN中的卷积计算过程进行优化具有现实意义。
目前, 学者们主要从内存使用效率与处理速度2个方面对CNN进行优化, 提出快速CNN[7]、RCNN[8]等方法。这些方法在很大程度上提高了前馈过程的速度, 但是并未解决内存受限的问题。随着深度学习应用范围的扩大, 设备的内存受限问题越来越突出, 提升卷积中的内存占用效率对于深度学习在各种设备和平台上的应用至关重要。文献[9]提出将输入矩阵转换为列向量组合(im2col)的方法, 该方法虽然产生了中间矩阵转换开销, 但是转换后的矩阵与核函数卷积可以利用相关加速库(如cuBLAS、OpenBLAS中封装的矩阵-向量乘)进行加速。在此基础上, 文献[10]提出一种内存高效的卷积优化算法MEC, 该算法根据输出矩阵的行、列对输入矩阵分段读取并将其转换到一个中间矩阵中, 然后每次取转换矩阵的一段与核函数转换向量进行卷积。虽然MEC算法降低了额外的内存开销, 但是分段卷积控制逻辑复杂, 且分段矩阵地址不对齐, 不利于使用GPU进行并行控制。
针对上述问题, 本文提出一种基于计算统一设备架构(Computing Unified Device Architecture, CUDA)加速库的卷积计算优化算法MFCA。根据输出矩阵的大小对输入矩阵进行分块, 采用im2col方法转换各子块和相应的核函数矩阵, 利用cuBLAS中矩阵-矩阵乘法加速库对卷积运算实现加速, 在此基础上, 对输出结果按序存储以得到输出矩阵。
1 相关工作目前主流的CNN及相关计算架构有Caffe[9]、Theano[11]、cuDNN[12]等。他们使用的卷积计算加速算法可以分为以下3种:
1) im2col+GEMM:将输入的原始图像(image)信息转换为多个小的列向量(column)并重组为中间转换矩阵, 然后利用高度优化并封装好的BLAS[13]中的矩阵乘法进行加速。这类方法的典型代表有OpenBLAS[14]和文档处理[15]中的应用。
2) FFT(Fast Fourier Transform):基于FFT的卷积变换主要用于时域和频域之间的转换[16], 在频域中卷积可以作为乘法进行计算, 但这种计算会因为必须将卷积核填充到与输入图像相同大小而增加内存开销。因此, FFT不适用于卷积核较小的情况。
3) Winograd:基于Winograd的卷积来源于Coppersmith-Winograd算法[17]。该方法以增加中间计算开销为代价来减少乘法计算量, 目前, 其通常与FFT相结合被应用于NNPACK库中[18]。
2 MFCA算法 2.1 问题描述现有典型内存优化的卷积方法包括直接卷积、im2col卷积和MEC卷积, 三者的卷积过程如图 1所示。
|
Download:
|
| 图 1 3种卷积过程 | |
从图 1可以看出, 在相同输入矩阵 I (ih×iw×ic= 7×7×1)、卷积核 K (kh×kw×kc=3×3×1)、步长sh=sw=1且pad为0时, 3种卷积方法的输出矩阵均为 O (oh×ow×oc=5×5×1)。其中, 直接卷积根据卷积的定义进行计算, 如图 1(a)中灰色部分与卷积核的内积即为输出矩阵的一个元素, 随后按步长滑动卷积窗口直至得到整个输出。im2col卷积方法对输入矩阵和核函数进行转换, 得到中间矩阵和核函数的列向量并对两者进行相乘, 最终得到相同的输出矩阵。该卷积方法虽然因为中间转换矩阵增加了内存开销, 但是其可以利用矩阵向量乘库对卷积进行加速, 最终提升计算性能。MEC方法在im2col方法的基础上, 按输出矩阵大小分段读取输入矩阵并得到对应的中间矩阵, 该方法对计算性能的改进与im2col相同。MEC方法虽然也引入了中间矩阵, 但是其比im2col节省了51.2%的内存空间。但是, MEC方法也存在不足, 即在矩阵转换时矩阵分块逻辑复杂, 且得到的小矩阵地址空间不对齐。
2.2 MFCA算法实现为进一步提升卷积的计算性能, 本文基于im2col方法, 提出一种节省内存空间并能够利用cuBLAS[19]中矩阵-矩阵乘法加速库的MFCA算法。该算法对输入矩阵按行读取并转换为中间矩阵的一行, 即复制滑动窗口 W (ih×iw=3×7)所覆盖的部分作为中间矩阵 L 的一行, 滑动窗口步长设为1。MFCA算法具体卷积过程如图 2所示。
|
Download:
|
| 图 2 MFCA算法卷积过程 | |
在图 2中, A 是输入矩阵 I的第1部分, A = I [1:3, 1:7]。将步长sh=1的滑动窗口 W 所覆盖范围作为第2部分, B = I [2:4, 1:7]。继续滑动子窗口 W 直至覆盖到输入矩阵 I 的最后一行 E = I [5:7, 1:7]。得到的5个子块分别对应中间矩阵 L 的5行 A、B、C、D、E。核函数矩阵 K 中的元素分别与原始卷积中的位置相对应, 得到中间矩阵 K ′。其中, K ′中非零元素为KW×KH×OW个, 其余均是为利用加速库而填充的0值。最终, 通过调用BLAS3级库中矩阵-矩阵乘接口实现 O = K ′× L的输出。与MEC方法相比, MFCA的中间转换矩阵较大, 但控制逻辑简单, 易于GPU并行实现, 且具有更好的计算性能。
在实际应用中, 若输入矩阵为 I (IH×IW×IC), 卷积核为 K (KH×KW×KC), 输入矩阵的中间矩阵为 L (LH×LW×LC), 输出矩阵为 O (OH×OW×OC)。在使用MFCA算法后, 他们存在如表 1所示的关系(在计算过程中不考虑图像通道个数和卷积核个数)。
|
下载CSV 表 1 各矩阵信息对比 |
在表 1中, 核函数矩阵 K ′的行(高度)由中间矩阵 L 的列(宽度)IW×KH决定, 但在实际计算中, K ′只有KH×KW×OW个非0值, 其他的( IW-KW)×KH×OW个均为0。非0值所占比例越小, 计算所需的内存开销越大。因此, 为减少 K ′中值为0的元素个数, 本文对MFCA算法进行改进。
2.3 MFCA算法优化将原始输入矩阵 I 按列分为m块, 分别进行中间矩阵转换, 然后与核函数矩阵做卷积, 最终得到m个输出分量, 并按序组成输出矩阵。以图 3为例, 输入矩阵大小为8×8, 在计算过程中将输入矩阵平均分为2块, 即m=2, 则2个分块按序存放得到对应的输出矩阵。
|
Download:
|
| 图 3 分块卷积过程 | |
在图 3中, 根据输出矩阵的大小决定分块矩阵是否需要进行填充。若IW/m < OW/m+KW－1, 则需要对子矩阵 A 和 B 进行填充, 填充元素个数为n=(OW/m+KW－1)－IW/m, 填充元素来自与该块相邻的上/下一个块的按列存储的前n个元素, 例如图 3中子矩阵 A 中的右侧阴影部分和子矩阵 B 中的左侧阴影部分, 则转换矩阵为 A ′中的右侧虚线框部分和 B ′中的左侧虚线框部分。2个子矩阵分别与核函数矩阵进行卷积, 得到最终的输出矩阵 O 。
已知输出矩阵宽度为OW, 每块的输出宽度为
|
下载CSV 表 2 OW能被m整除时的矩阵信息 |
表 2显示了被分割后的一块输入矩阵所对应的中间矩阵、核函数矩阵及输出矩阵的行列信息, 则中间矩阵 L 的总内存开销为:
| ${M_L} = \left( {\frac{{{O_W}}}{m} + {K_W} - 1} \right) \times {K_H} \times {O_H} \times m$ | (1) |
核函数矩阵的内存开销为:
| ${M_\mathit{\boldsymbol{K}}} = \left( {\frac{{{O_W}}}{m} + {K_W} - 1} \right) \times {K_H} \times {O_W}$ | (2) |
其中,
| $\begin{array}{l} M = {M_\mathit{\boldsymbol{L}}} + {M_\mathit{\boldsymbol{K}}} = \\ \;\;\;\;\;\;\;\left( {\frac{{{O_W}}}{m} + {K_W} - 1} \right) \times {K_H} \times \left( {m \times {O_H} + {O_W}} \right) \end{array}$ | (3) |
上述转换需要满足3个条件:
1) 当M最小时确定分块个数m。
2) Mmin < Mim2col=OW×OH×KW×KH+KW×KH。
3) KW≤
结合上述条件可得:
| ${M_{{\rm{MFCA}}}} = \left( {\frac{{{O_W}}}{m} + {K_W} - 1} \right) \times {K_H} \times \left( {{O_H} \times m + {O_W}} \right)$ | (4) |
将式(4)对m求导可得:
| $M_{{\rm{MFCA}}}^\prime = \left( {{K_W} - 1} \right) \times {K_H} \times {O_H} - \frac{{{O_W}}}{{{m^2}}} \times {K_H} \times {O_W}$ |
则有:
| $m = \sqrt {\frac{{O_W^2}}{{\left( {{K_W} - 1} \right) \times {O_H}}}} $ | (5) |
得到的m值分为2种情况:
1) 当m为整数时, 输入矩阵的第m个子块矩阵无需进行0值填充。
2) 当m不是整数时, 则有2个可能值:
将得到的m值带入式(4), 得到最小的总内存开销MMFCAmin, 并与im2col和MEC的内存开销进行比较。其中, im2col和MEC的总内存开销可分别由式(6)、式(7)计算:
| ${M_{{\rm{im}}2{\rm{col}}}} = {O_W} \times {O_H} \times {K_W} \times {K_H} + {K_W} \times {K_H}$ | (6) |
| ${M_{{\rm{MEC}}}} = {O_H} \times {I_H} \times {K_W} + {K_H} \times {K_W}$ | (7) |
比较式(4)、式(6)和式(7)可知, MMCE < Mim2col, MMFCAmin < Mim2col, 而MMCE与MMFCAmin间的大小关系与需要计算的输入矩阵大小、卷积核尺寸以及m值都有关, 具体比较结果见3.2节。
3 实验结果与分析本文基于CUDA架构对深度学习中的卷积计算进行优化, 并通过多组实验来比较分析各算法的性能。
3.1 实验设置在CPU+GPU的实验平台上使用C+ +结合CUDA架构实现本文算法, CPU为Intel i7-4790 CPU@3.60 GHz, GPU为NVIDIA GTX 970。其中, 由NVIDIA提供的封装好的矩阵运算库cuBLAS对本文算法的卷积运算进行加速。为更全面地对算法进行验证与比较, 在该实验环境下执行im2col和MEC 2种方法, 实验的测试集信息如表 3所示。
|
下载CSV 表 3 测试集信息 |
3种算法的内存开销比较如表 4所示。为简化分析, 对表 4中的Mim2col、MMEC和MMFCA内存开销进行柱状图比较, 结果如图 4所示。其中, 为方便对比, 以im2col算法的内存开销为基准。
|
下载CSV 表 4 3种卷积算法的内存开销对比 |
|
Download:
|
| 图 4 3种卷积算法的内存开销柱状图比较 | |
从图 4可以看出, 本文MFCA算法产生的中间转换矩阵的内存开销明显优于im2col算法, 平均内存使用率提升61.25%。尤其对于大输入矩阵, 如CV2, 效果提升更高, 达到86.57%。与MEC算法相比, 本文算法在大输入矩阵中优势明显, 如CV7和CV8, 在输入矩阵较小时不占优势。
3.3 性能分析为验证本文算法对卷积计算的性能改进效果, 对不同算法的执行时间进行统计, 结果如图 5所示, 同样以im2col算法的运行时间为基准。
|
Download:
|
| 图 5 不同卷积算法的运行时间对比 | |
从图 5可以看出, 当输入矩阵较小时, MFCA与MEC对运行时间性能改进相差不大, 但是当输入矩阵较大时, 本文算法比MEC效果好, 情况最佳时其卷积计算速度为MEC的2倍, 如CV8。在图 5的9组不同实验中, MFCA比MEC的卷积计算速度平均提高20.57%。
3.4 算法复杂度分析离散二维卷积计算公式为:
| $\mathit{\boldsymbol{B}}(i,j) = \sum\limits_{m = 0} {\sum\limits_{n = 0} \mathit{\boldsymbol{K}} } (m,n)*\mathit{\boldsymbol{A}}(i - m,j - n)$ | (8) |
其中, A 为输入矩阵, K 为卷积核, B 为卷积结果, 即输出矩阵。卷积计算时间复杂度计算公式为:
| $Time \sim O\left( {{\mathit{\boldsymbol{B}}^2} \cdot {\mathit{\boldsymbol{K}}^2} \cdot {C_{{\rm{ in }}}} \cdot {C_{{\rm{ out }}}}} \right)$ | (9) |
为简化说明, 此处统一假设输入矩阵和卷积核都是正方形, Cin为每个卷积核通道数, Cout为输出通道数。通过分析可知, 3种算法的上述参数完全相同, 因此, 3种算法具有相同的时间复杂度。算法所需的存储空间包括3个部分:算法本身占用的存储空间, 算法的输入输出数据所占用的存储空间, 算法运行时临时占用的存储空间。根据2.3节相关分析可知, Mim2col>MMEC, 而MMEC与MMFCA的关系与输入数据大小有关, 当输入矩阵较大时, 有MMEC>MMFCA。且MFCA中分块输入矩阵地址空间连续能够提高缓存利用率, 同时能够充分利用矩阵乘法库来加速计算过程。因此, MFCA的空间复杂度较低, im2col的空间复杂度较高。
综上, 本文卷积优化方法MFCA在im2col的基础上, 能够明显提升内存使用率, 同时采用分块矩阵的思想能有效降低大矩阵计算对有限的访存资源的压力, 提高数据局部性与缓存利用率。此外, MFCA方法的中间转换过程可以利用cuBLAS中的矩阵-矩阵乘法库, 进一步提升卷积计算性能, 尤其对大输入矩阵, 其优势更加明显。
4 结束语本文提出一种基于矩阵转换的卷积计算优化方法MFCA。对输入矩阵按列进行分块, 采用im2col方法对各子块和卷积核矩阵实现转换, 以节省内存空间, 然后利用矩阵运算库cuBLAS对矩阵和矩阵乘的卷积运算进行加速, 达到提高卷积计算性能的目的。实验结果验证了MFCA方法的有效性。将该方法推广到多通道多区域的卷积应用场景是下一步的研究方向。
| [1] |
DALAL N, TRIGGS B.Histograms of oriented gradients for human detection[C]//Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D.C., USA: IEEE Computer Society, 2005: 886-893.
(  1)
|
| [2] |
ZHOU Huiyu, YUAN Yuan, SHI Chunmei. Object tracking using SIFT features and mean shift[J]. Computer Vision and Image Understanding, 2009, 113(3): 345-352. DOI:10.1016/j.cviu.2008.08.006 ( 1)
|
| [3] |
SHARIF R A, AZIZPOUR H, SULLIVAN J, et al.CNN features off-the-shelf: an astounding baseline for recognition[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition Workshops.Washington D.C., USA: IEEE Press, 2014: 156-163.
( 1)
|
| [4] |
王晓晖, 盛斌, 申瑞民. 基于深度学习的深度图超分辨率采样[J]. 计算机工程, 2017, 43(11): 252-260. ( 2)
|
| [5] |
李传朋, 秦品乐, 张晋京. 基于深度卷积神经网络的图像去噪研究[J]. 计算机工程, 2017, 43(3): 253-260. DOI:10.3969/j.issn.1000-3428.2017.03.042 ( 1)
|
| [6] |
周飞燕, 金林鹏, 董军. 卷积神经网络研究综述[J]. 计算机学报, 2017, 40(6): 1229-1251. ( 1)
|
| [7] |
YANG Fan, CHOI W, LIN Yuanqing.Exploit all the layers: fast and accurate CNN object detector with scale dependent pooling and cascaded rejection classifiers[C]//Proceedings of IEEE Conference on Computer Vision and Pattern Recognition.Washington D.C., USA: IEEE Press, 2016: 236-243.
( 1)
|
| [8] |
WANG Xiaolong, SHRIVASTAVA A, GUPTA A.A-fast-RCNN: hard positive generation via adversary for object detection[EB/OL].[2018-04-29].https://arxiv.org/pdf/1704.03414.pdf.
( 1)
|
| [9] |
JIA Yangqing, SHELHAMER E, DONAHUE J, et al.Caffe: convolutional architecture for fast feature embedding[C]//Proceedings of the 22nd ACM International Conference on Multimedia.New York, USA: ACM Press, 2014: 269-280.
( 2)
|
| [10] |
CHO M, BRAND D.MEC: memory-efficient convolu-tion for deep neural network[EB/OL].[2018-04-25].https://arxiv.org/pdf/1706.06873.pdf.
( 1)
|
| [11] |
BERGSTRA J, BASTIEN F, BREULEUX O, et al.Theano: deep learning on GPUs with Python[EB/OL].[2018-04-25].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.678.1889&rep=rep1&type=pdf.
( 1)
|
| [12] |
CHETLUR S, WOOLLEY C, VANDERMERSCH P, et al.cuDNN: efficient primitives for deep learning[EB/OL].[2018-04-25].https://arxiv.org/pdf/1410.0759.pdf.
( 1)
|
| [13] |
JIA Yangqing.Learning semantic image representations at a large scale[EB/OL].[2018-04-26].https://cloudfront.escholarship.org/dist/prd/content/qt64c2v6sn/qt64c2v6sn.pdf.
( 1)
|
| [14] |
ZEE F G V. BLIS:a framework for rapidly instantiating BLAS functionality[J]. ACM Transactions on Mathematical Software, 2013, 41(3): 1-33. ( 1)
|
| [15] |
CIRE AN D C, MEIER U, MASCI J, et al.High-performance neural networks for visual object classification[EB/OL].[2018-04-26].https://arxiv.org/pdf/1102.0183.pdf.
( 1)
|
| [16] |
SIMONYAN K, ZISSERMAN A.Very deep convolutional networks for large-scale image recognition[EB/OL].[2018-04-28].https://arxiv.org/pdf/1409.1556.pdf.
( 1)
|
| [17] |
WINOGRAD S. Arithmetic complexity of computations[M]. .
( 1)
|
| [18] |
VASILACHE N, ZINENKO O, THEODORIDIS T, et al.Tensor comprehensions: framework-agnostic high-performance machine learning abstractions[EB/OL].[2018-04-25].https://arxiv.org/pdf/1802.04730.pdf.
( 1)
|
| [19] |
NVIDIA C.CUBLAS library[EB/OL].[2018-04-28].https://arcb.csc.ncsu.edu/~mueller/cluster/nvidia/0.8/NVIDIA_CUBLAS_Library_0.8.pdf.
( 1)
|