# A Review of the Optimal Design of Neural Networks Based on FPGA
## 4 Neural Network Optimization Technology Based on FPGA
### Optimization of Data and Its Operations
#### 4.1.3 Convolution Optimization  
For the optimization of convolution algorithms, scholars have provided the following two ideas. One is the Winograd fast convolution algorithm, which speeds up convolution by increasing addition and reducing multiplication. Another is the Im2 col convolution optimization algorithm that sacrifices storage space in order to improve the speed of the convolution operation. This is described in detail below. (1) Winograd fast convolution algorithm  
The Winograd Fast Convolutional algorithm was first proposed by [PERSON] in his paper \"Fast Algorithms for Convolutional Neural Networks\" in 1980, but it did not cause much sensation at that time. In the 2016 CVPR conference, [PERSON] et al. [86] proposed the use of the Winograd fast convolution algorithm to accelerate the convolution  
Figure 7: Neural network optimization technology based on FPGA. operation. Since then, the Winograd algorithm has been widely used to accelerate the convolution algorithm. The Winograd algorithm can accelerate the convolution operation because it uses more addition to reduce multiplication calculation, thus reducing the amount of calculations, using less FPGA resources, and improving operation speed, not as well as when FFT (fast Fourier transform) is introduced into the plural. But with the premise being, in the processor, the clock cycle of the calculation of the multiplication are longer than the clock cycles of the addition. Taking the one-dimensional convolution operation as an example, the input signal as \(d=\left[d_{0}\ d_{1}\ d_{2}\ d_{3}\right]^{T}\), and the convolution kernel as \(g=\left[g_{0}\ g_{1}\ g_{2}\right]^{T}\), then the convolution can be written as the following matrix multiplication form:  
\[F(2,3)= \begin{pmatrix}d_{0}&d_{1}&d_{2}\\ d_{1}&d_{2}&d_{3}\end{pmatrix}\begin{pmatrix}g_{0}\\ g_{1}\\ g_{2}\end{pmatrix} = \begin{pmatrix}r_{0}\\ r_{1}\end{pmatrix}  \tag{1}\]  
For general matrix multiplication, six multiplications and four additions are required, as follows: \(r_{0}=d_{0}g_{0}+d_{1}g_{1}+d_{2}g_{2}\), \(r_{1}=d_{1}g_{0}+d_{2}g_{1}+d_{3}g_{2}\). However, the matrix transformed by the input signal in the convolution operation is not an arbitrary matrix, in which a large number of repetitive elements are regularly distributed, such as d\({}_{1}\) and d\({}_{2}\) in row 1 and row 2. The problem domain of the matrix multiplication transformed by convolution is smaller than that of the general matrix multiplication, which makes it possible to optimize. After conversion using a Winograd algorithm:  
\[F(2,3)= \begin{pmatrix}d_{0}&d_{1}&d_{2}\\ d_{1}&d_{2}&d_{3}\end{pmatrix}\begin{pmatrix}g_{0}\\ g_{1}\\ g_{2}\end{pmatrix} = \begin{pmatrix}m_{1}+m_{2}+m_{3}\\ m_{2}-m_{3}-m_{4}\end{pmatrix}  \tag{2}\]  
Among them, the \(m_{1}=\left(d_{0}-d_{2}\right)g_{0}\), \(m_{2}=\left(d_{1}+d_{2}\right)\left(g_{0}+g_{1}+g_{2}\right)/2\), \(m_{3}=\left(d_{2}-d_{1}\right)\) (\(g_{0}\)\(-\)\(g_{1}+g_{2}\))/2, \(m_{4}=\left(d_{1}-d_{3}\right)g_{2}\). To calculate \(r_{0}=m_{1}+m_{2}+m_{3}\), \(r_{1}=m_{2}-m_{3}-m_{4}\), the number of operations required are four additions (subtraction) on the input signal d and four multiplications and four additions on the output m, respectively. In the inference stage of the neural network, the elements on the convolution kernel are fixed, and therefore the operation on g can be calculated well in advance. In the prediction stage, it only needs to be calculated once, which can be ignored. Therefore, the total number of operations required is the sum of the operation times on \(d\) and \(m\), namely, four times of multiplication and eight times of addition. Compared with the direct operation of six multiplications and four additions, the number of multiplications decreases, and the number of additions increases. In FPGA, the multiplication operation is much slower than the addition operation, and it will occupy more resources. By reducing multiplication times and adding a small amount of addition, the operation speed can be improved.