date: 2019/08/23


上一篇文章《Winograd卷积原理 | Hey~YaHei!》已经介绍过Winograd卷积的基本原理,但终究是理论上的推导,在实际应用的时候其实有些耐人寻味的地方:数学推导假设的是无限的精度和数值范围,但实际计算机的运算精度与数值范围都是有限的,不过按照论文《Fast algorithms for convolutional neural(CVPR2016)》的报告,Winograd在浮点运算上的表现都不错:

VGG_errors.jpg



浮点运算的Winograd确实不错,但它却似乎也没那么轻易能套上量化——整型可没有浮点这么大的动态范围,如何保证运算过程整型不会溢出将是个令人头疼的问题。


溢出

假设将网络量化成int8,int8的权重和int8的输入,那么得益于int8 * int8,无论是Direct Convolution还是im2col+GEMM,这都能带来可观的加速。但在Winograd里可就不是这么回事了!

注意:im2col也没有对数值的大小进行变换


F(2,3)

回顾一下F(2,3)的变换矩阵:


接下来计算一下矩阵和矩阵:

from sympy import Matrix, Symbol

BT = Matrix([
    [1,  0, -1,  0],
    [0,  1,  1,  0],
    [0, -1,  1,  0],
    [0,  1,  0, -1]
])
G = Matrix([
    [2,  0, 0],
    [1,  1, 1],
    [1, -1, 1],
    [0,  0, 2]
])
AT = Matrix([
    [1,  1,  1,  0],
    [0,  1, -1, -1]
])
g = Matrix([[Symbol('g0')], [Symbol('g1')], [Symbol('g2')]])
d = Matrix([[Symbol('d0')], [Symbol('d1')], [Symbol('d2')], [Symbol('d3')]])
m = Matrix([[Symbol('m0')], [Symbol('m1')], [Symbol('m2')], [Symbol('m3')]])
print("G * g:", G * g)
print("BT * d:", BT * d)
print("AT * m:", AT * m)



输入、输出变换过程包含8次加法和2次移位;

同时可以看到,为了保证计算不溢出,需要额外的2个bits,而需要额外的1个bit,换言之,为了保证安全的int8 * int8,权重和输入分别得量化到int6和int7。


F(2x2,3x3)

g = Matrix(3, 3, [Symbol(f'g{i}') for i in range(3*3)])
d = Matrix(4, 4, [Symbol(f'd{i}') for i in range(4*4)])
m = Matrix(4, 4, [Symbol(f'm{i}') for i in range(4*4)])

print("G * g * GT:", G * g * G.T)
>>> Matrix([
... [              4*g0,                         2*g0 + 2*g1 + 2*g2,                         2*g0 - 2*g1 + 2*g2,               4*g2],
... [2*g0 + 2*g3 + 2*g6, g0 + g1 + g2 + g3 + g4 + g5 + g6 + g7 + g8, g0 - g1 + g2 + g3 - g4 + g5 + g6 - g7 + g8, 2*g2 + 2*g5 + 2*g8],
... [2*g0 - 2*g3 + 2*g6, g0 + g1 + g2 - g3 - g4 - g5 + g6 + g7 + g8, g0 - g1 + g2 - g3 + g4 - g5 + g6 - g7 + g8, 2*g2 - 2*g5 + 2*g8],
... [              4*g6,                         2*g6 + 2*g7 + 2*g8,                         2*g6 - 2*g7 + 2*g8,               4*g8]])

print("BT * d * B:", BT * d * BT.T)
>>> Matrix([
... [  d0 + d10 - d2 - d8,   d1 - d10 + d2 - d9, -d1 - d10 + d2 + d9,   d1 + d11 - d3 - d9],
... [ -d10 + d4 - d6 + d8,   d10 + d5 + d6 + d9,  d10 - d5 + d6 - d9,  -d11 + d5 - d7 + d9],
... [ -d10 - d4 + d6 + d8,   d10 - d5 - d6 + d9,  d10 + d5 - d6 - d9,  -d11 - d5 + d7 + d9],
... [-d12 + d14 + d4 - d6, -d13 - d14 + d5 + d6, d13 - d14 - d5 + d6, -d13 + d15 + d5 - d7]])

print("AT * m * A:", AT * m * AT.T)
>>> Matrix([
... [    m0 + m1 + m10 + m2 + m4 + m5 + m6 + m8 + m9,    m1 - m10 - m11 - m2 - m3 + m5 - m6 - m7 + m9],
... [-m10 - m12 - m13 - m14 + m4 + m5 + m6 - m8 - m9, m10 + m11 - m13 + m14 + m15 + m5 - m6 - m7 - m9]])


输出矩阵的各元素系数绝对值之和


输入、输出变换过程包含80次加法和4次移位();

同时可以看到,为了保证计算不溢出,需要额外的4个bits,而需要额外的2个bit,换言之,为了保证安全的 int8 * int8 ,权重和输入分别得量化到int4和int6。


F(4x4,3x3)


为了保证计算不溢出,需要额外的10个bits(最后一行绝对值之和最大,),而需要额外的7个bits(最后一行的绝对值之和最大,),换言之……压根没法保证 int8 * int8 的安全计算。这时候可能只能将int8扩展到int16,执行 int16 * int16 的乘法运算,即便如此,权重也只能量化到int6


大家是怎么做的?

ncnnmnn的量化计算本质上是int16 * int16,所以完全没有溢出的问题,而需要将权重量化到int6;

Tengine的量化计算是int8 * int8,1.6版本已经支持Winograd卷积,但目前还没有支持Winograd量化。


思考:先变换后量化?

对量化的输入和权重做变换时溢出问题着实让人头疼,既然如此,而前述的保留bits位的方式是非常保守的做法,往往数值范围在经过变换后不会发生如此夸张的膨胀,即使有些极端值我们也可以采用截断的方式控制数值范围以增加量化的分辨力。

那么我们能不能先做变换再进行量化呢?


首先考虑一下权重的量化。

由于权重是固定的,只需要在加载模型时做一次变换,这部分成本往往是忽略不计的,我们可以保持浮点数值的权重,对变换后的权重矩阵进行量化。但缺点在于,权重文件会比较大——以为例,权重规模扩大为原来的4倍,而 FP32->INT8 使每个权重的存储空间减小为原来的四分之一,相互抵消后,量化的模型文件大小没有发生变化。


再考虑输入的量化。

对输入进行变换的开销实际会被平摊,所以在输入输出通道数足够多的时候,用浮点数值进行变换再进行量化似乎也是可行的。如果浮点运算开销很大,那么可以考虑分两阶段量化,首先将输入量化到一个更高位宽的整型数值类型上(比如INT16/INT32),然后进行整数的变换,最后截断数值并收缩到位宽更小的整型数值类型的表示范围内(如INT8/INT16)。


更快的变换

上一篇文章我们已经提到过——

尽管的计算过程中也有大量的乘法,但观察可以发现矩阵和中有相当多的元素恰好是,也就是说,用Winograd计算量化的卷积应该会有神奇的加成


将输入、输出变换过程中的大量乘法替换成移位运算之后,理论上Winograd能变得更快!