快速傅里叶变换(FFT)

​ FFT的任务就是将多项式的系数表示法转化为点值表示法，再由点值表示法转化为系数表示法的过程。前面的过程称为求值（DFT），后面的过程称为插值（IDFT）。

​ 任取n+1个互不相同的$S=\lbrace p_1,p_2,…,p_{n+1}\rbrace$,对$f(x)$分别求值后得到$f(p_1),f(p_2),…,f(p_{n+1})$，此时称$A(x)=\lbrace(p_1,f(p_1)),(p_2,f(p_2)),…,(p_{n+1},f(p_{n+1}))\rbrace$为多项式f(x)在S下的点值表示法。

​ 得到一个n次多项式的点值表示法需要代入n+1个数到多项式里面去，如果只是随意选取n+1个，每个数值的计算复杂度为O(n)，那么n+1个数值的计算复杂度将仍然是O(n²)，因此想到了利用奇偶函数的对称性代入，这样计算量就变为了原来的一半，之后不断递归，但由于后续的递归过程如果代入的是实数平方，后续递归将不能进行。由此便引入了复数。通过将n次单位根组成S，记$A_0(x)$为偶次项和，$A_1(x)$为奇次项和：
$$
A_0(x)=a_0x^0+a_2x^1+…+a_{n-1}x^{\frac{n}{2}}
$$
$$
A_1(x)=a_1x^0+a_3x^1+…+a_{n-2}x^{\frac{n}{2}}
$$

于是有$A(\omega_n^m)=a_0\omega_n^0+a_1\omega_n^m+a_2\omega_n^{2m}+a_3\omega_n^{3m}+…+a_{n-1}\omega_n^{(n-1)*m}+a_n\omega_n^{nm}$

之后：$A(\omega_n^m)=A_0((\omega_n^m)^2)+\omega_n^mA_1((\omega_n^m)^2)=A_0(\omega_\frac{n}{2}^m)+\omega_n^mA_1(\omega_\frac{n}{2}^m)$

$A(\omega_n^{m+\frac{n}{2}})=A_0((\omega_n^m)^2)+\omega_n^{m+\frac{n}{2}}A_1((\omega_n^m)^2)=A_0(\omega_\frac{n}{2}^m)-\omega_n^mA_1(\omega_\frac{n}{2}^m)$

因此递归的FFT伪代码为：

1
2
3
4
5
6
7
8
9
10
11
12

def FFT(A)
# A-[a0,a1,...,an-1]
n=len(A)
if n==1:
    return A
A0,A1=[a0,a2,...,an-2],[a1,a3,...,an-1]
a=[0]*n
for i in range(n/2):
     a[i]=a0[i]+w*a1[i];
     a[i+n/2]=a0[i]-w*a1[i]
     w=w*wn
return a

大数据时代的到来，数据呈爆发式增长的态势，深度学习技术不断发展，比如图像识别、语音识别和自然语言处理等。但是这些深度学习技术都有着极为庞大的计算量，对芯片的性能功耗要求很高，现今，比较热门的比如神经网络被广泛应用于人工智能应用之中，而传统的通用芯片再处理复杂神经网络的时候收到了带宽和能耗的限制，因此就推动了人们对深度学习硬件加速器的研究，目前主流的硬件加速器有三类：GPU、ASIC和FPGA。

• GPU：与传统CPU不同，GPU的内部拥有大量的逻辑计算单元，远超其中的控制单元和寄存器的规模；GPU拥有一些存储单元可以使得GPU线程之间可以共享这些内存而不依赖于全局内存；GPU拥有相对高速且内存带宽相对较大的全局内存。

• ASIC：针对某一个或者某一类算法进行硬件定制，通常来说，相对于其他硬件加速器，ASIC加速深度学习算法能取得较高的性能和功耗，但是其开发周期长，成本高，缺乏灵活性。

• FPGA：与其他硬件加速其不同的是FPGA具有可编程性，也就是FPGA内部的逻辑块是可以通过编程进行调整的，因此灵活性较高，并且也拥有不错的性能和较低的功耗。现阶段，GPU更适合深度学习算法的训练阶段，FPGA更适合深度学习算法的推理阶段。

1. 人工设计的轻量级神经网络模型

1.1 使用小卷积核代替大卷积

​ 使用多层小卷积核代替一层大卷积核，可以减少网络的参数。如图所示：

例如使用两层3×3的卷积核代替5×5的卷积核，其卷积核的参数量可以从25减少到18，对于输入大小为 H×W×Cin 的特征,输出为 H×W×Cout 大小的特征图时，其浮点运算数从H×W×Cin×Cout×5²减少到了2×H×W×Cin×Cout×3。对于图b使用1×3核3×1的卷积核代替3×3的卷积核，可以使得参数量减少为原来的1/3。