WO2018107383A1 - Neural network convolution computation method and device, and computer-readable storage medium - Google Patents

Abstract

A neural network convolution computation method and device, used for achieving convolution computation of a weight matrix and neurons in a neural network in a matrix multiplication manner. The method comprises: first performing winograd transform on a neuron matrix and a weight matrix to obtain a transformed neuron matrix and a transformed weight matrix (step 1); then performing a matrix multiplication operation on the transformed neuron matrix and the transformed weight matrix to obtain a multiplication matrix (step 2); and finally performing winograd inverse transform on the multiplication matrix to obtain the computation result (step 3).

Description

Neural network convolution operation method, device and computer readable storage medium Technical field

The present invention relates to the field of artificial neural network technologies, and in particular, to a convolution operation method and apparatus for a neural network, and a computer readable storage medium.

Background technique

Multi-layer artificial neural networks are widely used in the fields of pattern recognition, image processing, function approximation and optimization calculation. Multi-layer artificial networks have been accepted by academia in recent years due to their high recognition accuracy and good parallelism. The industry is getting more and more attention.

In order to adapt to the increasingly high task requirements, the scale of neural networks has become more and more large. At present, large convolutional neural networks already contain hundreds of layers of network layers. The resulting problems require a lot of operations on neural networks, especially convolutional neural networks. A large number of convolution operations reduce the computational speed of neural networks and affect the use of neural networks in practical applications.

Summary of the invention

(1) Technical problems to be solved

The object of the present invention is to provide a convolution operation method and device for a neural network and a computer readable storage medium, which can realize a convolution operation of a weight matrix and a neuron in a neural network by matrix multiplication, thereby reducing a volume The amount of computation required for the product increases the computational speed of the neural network and greatly improves the efficiency of data processing.

(2) Technical plan

An aspect of the present invention provides a convolution operation method for a neural network, which is used to implement a convolution operation of a weight matrix and a neuron in a neural network by matrix multiplication, and the method includes:

S1, performing a winograd transformation on the neuron matrix and the weight matrix to obtain the transformed nerve a metamatrix and a transformed weight matrix;

S2, performing a matrix multiplication operation on the transformed neuron matrix and the transformed weight matrix to obtain a multiplication matrix;

S3, the multiplication matrix is inverse-transformed by winograd, and the operation result is obtained.

Another aspect of the present invention provides a convolution operation device for a neural network, which is used to implement a convolution operation of a weight matrix and a neuron in a neural network by matrix multiplication, and the device includes:

a memory for storing instructions;

a controller for decoding an instruction;

a processor, configured to execute the decoded instruction to perform:

Performing a winograd transformation on the neuron matrix and the weight matrix to obtain a transformed neuron matrix and a transformed weight matrix;

Performing a matrix multiplication operation on the transformed neuron matrix and the transformed weight matrix to obtain a multiplication matrix;

The inverse matrix is inverse-transformed by the multiplication matrix to obtain the operation result.

Another aspect of the invention provides a computer readable storage medium storing instructions executable by a processor to cause the processor to perform the methods of the present invention.

(3) Beneficial effects

The invention can turn a complex convolution operation into a sparse matrix multiplication operation, and the transform and inverse transform processes can be realized by bit operations. By this method, the amount of calculation required for convolution can be greatly reduced, and the operation speed of the neural network can be improved. Improve the efficiency of data processing. At the same time, using sparse sequences can reduce the storage space required to store network parameters and reduce the bandwidth of memory access.

DRAWINGS

FIG. 1 is a flow chart schematically showing a convolution operation method of a neural network according to an embodiment of the present invention.

FIG. 2 is a schematic block diagram showing the structure of a convolution operation device of a neural network according to an embodiment of the present invention.

FIG. 3 is a schematic block diagram showing the structure of a processor according to an embodiment of the present invention.

Fig. 4 schematically shows a schematic diagram of a convolution operation.

FIG. 5 is a schematic diagram showing the process of performing the convolution operation of FIG. 4 according to an embodiment of the present invention in conjunction with the apparatus described in the embodiment of the present invention.

detailed description

Other aspects, advantages, and salient features of the present invention will become apparent to those skilled in the <

In the present invention, the terms "include" and "including" and their derivatives are intended to be inclusive and not limiting; the term "or" is inclusive, meaning and/or.

In the present specification, the following description of various embodiments for describing the principles of the present invention should not be construed as limiting the scope of the invention in any way. The following description of the invention is intended to be understood as The description below includes numerous specific details to assist the understanding, but these details should be considered as merely exemplary. Accordingly, it will be apparent to those skilled in the art that various changes and modifications may be made to the embodiments described herein without departing from the scope and spirit of the invention. In addition, descriptions of well-known functions and constructions are omitted for clarity and conciseness. Moreover, throughout the figures, the same reference numerals are used for the acacia function and operation.

Some block diagrams and/or flowcharts are shown in the drawings. It will be understood that some blocks or combinations of the block diagrams and/or flowcharts can be implemented by computer program instructions. These computer program instructions may be provided to a general purpose computer, a special purpose computer or a processor of other programmable data processing apparatus such that when executed by the processor, the instructions may be used to implement the functions illustrated in the block diagrams and/or flowcharts. / operating device.

Thus, the techniques of this disclosure may be implemented in the form of hardware and/or software (including firmware, microcode, etc.). Additionally, the techniques of the present disclosure may take the form of a computer program product on a computer readable medium storing instructions for use by an instruction execution system. In the context of the present disclosure, a computer readable medium can be any medium that can contain, store, communicate, propagate or transport the instructions. For example, a computer readable medium can include but not Limited to electrical, magnetic, optical, electromagnetic, infrared, or semiconductor systems, devices, devices, or propagation media. Specific examples of the computer readable medium include: a magnetic storage device such as a magnetic tape or a hard disk (HDD); an optical storage device such as a compact disk (CD-ROM); a memory such as a random access memory (RAM) or a flash memory; and/or a wired /Wireless communication link.

FIG. 1 is a flow chart schematically showing a convolution operation method of a neural network according to an embodiment of the present invention. As shown in FIG. 1, the method includes:

Step 1. Perform a winograd transformation on the neuron matrix and the weight matrix to obtain a transformed neuron matrix and a transformed weight matrix.

In this step, the neuron matrix d ₀ and the weight matrix w _{0 are} subjected to winograd transformation using the following formula to obtain the transformed neuron matrix d and the transformed weight matrix w:

d=C ^T d ₀ C,w=Gw ₀ G ^T ,

Where C is the transformation matrix of the neuron matrix d ₀ , C ^T is the transposed matrix of C, G is the transformation matrix of the weight matrix w ₀ , and G ^T is the transposed matrix of G.

In addition, the values in the neuron matrix and the weight matrix are binary, and the values of the transformation matrix C, G are 2 ⁿ , such as 1, -0.5, 0, 0.5, 1, and the like. Thus, the embodiment of the present invention implements a winograd transform using a bit operation, and implements operations of multiplying 2 and dividing 2 by left shift and right shift. For example, when a value in the neuron matrix d ₀ is multiplied by 0.5, the value is shifted to the right by one bit. When multiplied by -0.5, the value is shifted to the left by one bit and the highest bit is inverted. Therefore, in the embodiment of the present invention, the winograd transformation is realized by the bit operation, the calculation amount is reduced, and the operation speed is improved.

The transformation matrices C and G of the neuron matrix d ₀ and the weight matrix w ₀ are obtained using the winograd algorithm.

The winograd algorithm uses the block multiplication of the matrix to reduce the number of multiplications of the matrix multiplication. There are many different matrix blocking methods. A winograd algorithm is shown below.

Calculate matrix multiplication C=AB, block each matrix, there is

Remember

S ₁ = A ₂₁ + A ₂₂ , S ₂ = S _{1 -} A ₁₁ , S ₃ = A _{11 -} A ₂₁ , S ₄ = A _{12 -} S ₂

S ₅ =B ₁₂ -B ₁₁ ,S ₆ =B ₂₂ -S ₅ ,S ₇ =B ₂₂ -B ₁₂ ,S ₈ =S ₆ -B ₂₁

M ₁ =S ₂ S ₆ , M ₂ =A ₁₁ B ₁₁ , M ₃ =A ₁₂ B ₂₁ , M ₄ =S ₃ S ₇

M ₅ =S ₁ S ₅ , M ₆ =S ₄ B ₂₂ , M ₇ =A ₂₂ S ₈

T ₁ = M ₁ + M ₂ , T ₂ = T ₁ + M ₄

then

C ₁₁ =M ₂ +M ₃ +M ₆ , C ₁₂ =T ₁ +M ₅

C ₂₁ =T ₂ -M ₇ , C ₂₂ =T ₂ +M ₅

The transformation matrix required for convolution is obtained by the above winograd algorithm, for example, for a one-dimensional convolution [d ₁ , d ₂ , d ₃ ]*[w ₁ , w ₂ ], assuming that each convolution slip is 1, The convolution can be extended into a matrix multiplied form

Available through the winograd algorithm

M ₁ = (-a ₁ + a ₂ + a ₃ ) b ₁ , M ₂ = a ₁ b ₁ , M ₃ = a ₂ b ₂ , M ₄ =0

M ₅ = (a ₂ + a ₃ ) (-b ₁ ), M ₆ =0, M ₇ = a ₃ (b ₁ - b ₂ )

Output ₁ = M ₂ + M ₃ + M ₆ , output ₂ = M ₁ + M ₂ + M _{4 -} M ₇

Remove the 0 value item, and the unused part can be rewritten as

m ₁ = (-a ₁ + a ₂ + a ₃ ) b ₁ , m ₂ = a ₁ b ₁ , m ₃ = a ₂ b ₂ , m ₄ = a ₃ (b ₁ - b ₂ )

Output ₁ = m ₂ + m ₃ , output ₂ = m ₁ + m _{2 -} m ₄

Thus a convolutional transformation matrix can be obtained

For high-dimensional matrices, the convolutional transformation matrix can be obtained by multiple matrix partitioning. The winograd algorithm has different matrix blocking methods. For the same matrix blocking method, the specific values and dimensions of the transformation matrix are determined by the dimensions of the input neurons and the weight matrix and the convolution sliding step size.

It can be seen from the above algorithm that the specific value and dimension of the transformation matrix are determined by the dimensions of the input neuron and the weight matrix. The specific influencing factors include the dimension of the input neuron, the dimension of the weight matrix, and the sliding step size of each convolution operation. When these three factors are determined, the values and dimensions of the transformation matrices are also determined, because in the neural network structure, the three influencing factors are things. It is set first, so this embodiment operates offline to complete the setting for each transformation matrix.

Step 2: performing a matrix multiplication operation on the transformed neuron matrix and the transformed weight matrix to obtain a multiplication matrix t:

t=w⊙d.

It should be noted that, in the usual convolution process, the two matrices participating in the operation may have different scales, so multiple matrix multiplication operations need to be performed by a sliding operation, and in the embodiment of the present invention, the converted neurons are The matrix d and the weight matrix w conform to the matrix multiplication rule, that is, only one matrix multiplication operation is performed, which greatly saves the calculation amount.

In addition, when two matrices are multiplied, if the value of a part of a matrix is known to be 0, the value obtained by multiplying the corresponding element of another matrix must be 0. Then, in the actual data calculation process, the above process can actually not participate in the operation, which can save unnecessary calculations. Therefore, in the embodiment of the present invention, the transformed weight matrix is mapped into a sparse sequence consisting of “0” and “1”, where “0” corresponds to an element whose value is “0” in the transformed weight matrix, and “1” corresponds to An element whose value is not 0 in the transformed weight matrix. When the matrix multiplication operation is performed, the elements of the corresponding positions in the transformed neuron matrix are extracted according to the "1" recorded by the sparse sequence to be multiplied by the corresponding elements in the transformed weight matrix.

E.g:

The sparse sequence corresponding to w is 1110111011101100 (read line by line). When performing matrix multiplication operation, according to the sequence, it can be known that the transformed neuron matrix [d ₀₃ , d ₁₃ , d ₂₃ , d ₃₂ , d ₃₃ ] Do not participate in the operation. Therefore, the use of sparse sequences can further reduce the amount of computation of matrix multiplication operations.

In step 3, the multiplication matrix is inverse-transformed by winograd to obtain an operation result.

In this step, the multiplication matrix t is inverse-transformed by winograd using the following formula to obtain an operation result:

Output=A ^T tA,

Where A is the inverse transformation matrix and A ^T is the transposed matrix of A.

It should be noted that the inverse transformation matrix A is the same as C and G, and is obtained by using the winograd algorithm. The specific process is not repeated here. In addition, the value of the inverse transformation matrix A is also 2 ⁿ , which is also realized by bit operations. The operation between values.

FIG. 2 is a schematic structural diagram of a convolution operation device of a neural network according to an embodiment of the present invention. As shown in FIG. 2, the device includes:

The data access unit 1 is configured to acquire a neuron matrix and a weight matrix from an external address space, and provide the same to the processor 5, and can also obtain an instruction from the outside and provide it to the memory 2.

The memory 2 is configured to read an instruction through the data access unit 1 and cache the read instruction.

The controller 3 is configured to read an instruction in the memory 2, decode the read instruction, obtain a micro instruction that controls the corresponding module, and send the micro instruction to the corresponding module.

The data buffer unit 4 is configured to store data required for data processing, and cache data during the operation.

The processor 5 is configured to perform a corresponding operation operation under the control of the controller unit, and the processor 5 acquires data from the data buffer unit 4 or through the data access unit 1, and the result of the operation is output to the data buffer unit 4 or Output through the data access unit 1.

FIG. 3 is a schematic structural diagram of a processor according to an embodiment of the present invention. As shown in FIG. 3, the processor 5 includes an operation control unit 51, a matrix multiplication unit 52, and a thinning processing unit 53, wherein the thinning processing unit 53 specifically includes a mapping unit 531, wherein the matrix multiplication unit 52 also performs the operations shown in the method of FIG. 1, and details are not described herein again.

The thinning processing unit 53 includes a mapping unit 531, and the mapping unit 531 implements mapping between the matrix and the sparse sequence to map the transformed weight matrix into a sparse sequence consisting of “0” and “1”, where “0” corresponds to the transformed An element whose value is "0" in the weight matrix, "1" corresponds to an element whose value is not 0 in the transformed weight matrix; when the matrix operation unit performs the matrix multiplication operation, the thinning unit records "1" according to the sparse sequence And extracting the elements of the corresponding positions in the transformed neuron matrix to be multiplied by the corresponding elements in the transformed weight matrix.

The matrix multiplication is specifically implemented as follows. The portion with the sparse sequence value of 0 does not contribute to the multiplication, does not participate in the operation, and the portion with the sparse sequence value of 1, reads the corresponding weight data through the mapping unit 531, and is read by the processor 531. Corresponding neuron data, the multiplication operation is completed, and when the sparse sequence completes the weight matrix, one row is added, and the value obtained by the multiplication operation is added. Due to moment Most of the multiply-and-accumulate operations in the matrix multiplication do not affect each other. Therefore, in the present embodiment, a plurality of multiply-and-accumulate operations are performed in parallel.

In the practical application of the neural network, the sparse sequence is completed offline, and the storage space occupied by the sparse sequence relative to the sparse storage space is very small, so the process does not affect the operation speed and storage space of the neural network.

4 is a schematic diagram showing a convolution operation. As shown in FIG. 4, the convolution kernel is a 3×3 matrix, and the convolution kernel slides on the input image, wherein the convolution kernel in the figure is the present invention. The layer weight matrix, the input image is the neuron matrix of the present invention.

For the convolution operation commonly used in neural networks, it is assumed that each time a pixel is slid, a total of four convolution operations are required, and each convolution operation, the convolution kernel and the corresponding data image data are multiplied and added. Therefore, for different output neurons on the same output feature map, the required input neurons are different, and the weights and connection relationships are the same. For example, in Figure 3, the calculation process of the first convolution result is: 1*1+1*0+1*1+0*0+1*1+1*0+0*1+0*0+ 1*1=4, the calculation process of the second convolution result is: 1*1+0*1+1*0+1*0+1*1+1*0+0*1+1*0+1 *1=3, and so on.

FIG. 5 is a schematic diagram showing a process for performing the convolution operation of FIG. 4 according to an embodiment of the present invention, as shown in FIG. 5:

In step S1, the controller 3 reads an instruction from the memory 2.

In step S2, the controller 3 decodes the microinstruction, and the data access unit 1 reads the data required to perform the convolution operation from the external address space according to the microinstruction, including the neuron matrix d ₀ and the weight matrix w ₀ . Then, the transformation matrices C, G, and the inverse transform matrix A are obtained, in the example of FIG. 4:

In step S3, the processor 5 reads the neuron matrix d ₀ and the weight matrix w ₀ from the data buffer unit 4, and performs a winograd transformation on the neuron matrix d ₀ and the weight matrix w ₀ , namely:

In step S4, the thinning processing unit 53 obtains the sparse sequence of the transformed weight matrix w by the mapping unit 531, that is, [1110111011101100]. The creation of the sparse sequence is performed by the mapping unit. The mapping unit traverses the weight matrix, and the non-zero value of the weight matrix is marked with a bit 1 and the zero value is marked with a bit 0, and finally a bit sequence is obtained as a sparse sequence, the bit sequence. The length is the same as the number of values of the weight matrix.

Step S5, the processor 5 selects the corresponding neuron and the weight according to the sparse sequence to perform a multiplication operation, and completes the matrix multiplication of the input neuron and the weight, wherein the transformed neuron matrix d is based on the index sequence [d ₀₃ , d ₁₃ , d ₂₃ , d ₃₂ , d ₃₃ ] do not participate in the operation, and finally get the operation result, namely:

Step S6, the processor 5 performs a winograd inverse transform operation on the result of multiplying the matrix, and obtains the output as follows

The computer readable storage medium provided by the present invention may be, for example, any medium capable of containing, storing, transmitting, transmitting or transmitting instructions. For example, a readable storage medium may include, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium. Specific examples of the readable storage medium include: a magnetic storage device such as a magnetic tape or a hard disk (HDD); an optical storage device such as a compact disk (CD-ROM); a memory such as a random access memory (RAM) or a flash memory; and/or a wired /Wireless communication link.

The readable storage medium includes computer executable instructions that, when executed by a processor, cause the processor to perform, for example, the method flow described above in connection with FIGS. 1 and 5, and any variations thereof.

The specific embodiments of the present invention have been described in detail, and are not intended to limit the present invention. Any modifications, equivalent substitutions, improvements, etc., made within the spirit and scope of the present invention are intended to be included within the scope of the present invention.

Claims (13)

A convolution operation method of a neural network, which is used for realizing a convolution operation of a weight matrix and a neuron in a neural network by matrix multiplication, wherein the method comprises: S1, performing a winograd transformation on the neuron matrix and the weight matrix to obtain a transformed neuron matrix and a transformed weight matrix; S2, performing matrix multiplication operation on the transformed neuron matrix and the transformed weight matrix to obtain a multiplication matrix; S3, performing inverse winograd transformation on the multiplication matrix to obtain an operation result. The convolution operation method of the neural network according to claim 1, wherein the step S1 comprises: The neuron matrix d ₀ and the weight matrix w _{0 are} subjected to winograd transformation using the following formula to obtain a transformed neuron matrix d and a transformed weight matrix w: d=C ^T d ₀ C,w=Gw ₀ G ^T , Where C is the transformation matrix of the neuron matrix d ₀ , C ^T is the transposed matrix of C, G is the transformation matrix of the weight matrix w ₀ , and G ^T is the transposed matrix of G. The convolution operation method of the neural network according to claim 2, wherein the step S3 comprises: The multiplication matrix t is inverse-transformed by winograd using the following formula to obtain an operation result: Output=A ^T tA, Where A is the inverse transformation matrix and A ^T is the transposed matrix of A. The convolution operation method of a neural network according to claim 3, wherein the values in the neuron matrix and the weight matrix are binary, and in the transformation matrix C, G and the inverse transformation matrix A The value is 2 ⁿ and n is an integer; Wherein, the winograd transform and the winograd inverse transform are implemented by using a bit operation. The convolution operation method of a neural network according to claim 1, wherein the transformed weight matrix is mapped into a sparse sequence consisting of "0" and "1", wherein "0" corresponds to the transformed weight An element with a value of "0" in the value matrix, and a "1" corresponding to the transformed weight matrix An element whose value is not 0; When performing the matrix multiplication operation, elements corresponding to positions in the transformed neuron matrix are extracted according to "1" of the sparse sequence record, and multiplied by corresponding elements in the transformed weight matrix. A convolution operation device for a neural network, which is used for realizing a convolution operation of a weight matrix and a neuron in a neural network by matrix multiplication, wherein the device comprises: a memory for storing instructions; a controller for decoding the instruction; a processor, configured to execute the decoded instruction to perform: Performing a winograd transformation on the neuron matrix and the weight matrix to obtain a transformed neuron matrix and a transformed weight matrix; Performing a matrix multiplication operation on the transformed neuron matrix and the transformed weight matrix to obtain a multiplication matrix; The multiplication matrix is inverse-transformed by winograd to obtain an operation result. The apparatus for convolution operation of a neural network according to claim 6, wherein said processor comprises a matrix operation unit for performing winograd on said neuron matrix d ₀ and weight matrix w ₀ using the following formula; Transform to obtain the transformed neuron matrix d and the transformed weight matrix w: d=C ^T d ₀ C,w=Gw ₀ G ^T , Where C is the transformation matrix of the neuron matrix d ₀ , C ^T is the transposed matrix of C, G is the transformation matrix of the weight matrix w ₀ , and G ^T is the transposed matrix of G. The convolution operation device of the neural network according to claim 7, wherein the matrix operation unit is further configured to: inversely transform the multiplication matrix t by winograd using the following formula to obtain an operation result: Output=A ^T tA, Where A is the inverse transformation matrix and A ^T is the transposed matrix of A. The convolution operation device of a neural network according to claim 8, wherein values in said neuron matrix and weight matrix are binary, and wherein said transformation matrix C, G and inverse transformation matrix A The value is 2 ⁿ and n is an integer; The matrix operation unit implements the winograd transform and the winograd inverse transform by using a bit operation. The apparatus for convolution operation of a neural network according to claim 6, wherein the processor further comprises a thinning processing unit for mapping the transformed weight matrix to "0" and "1" a sparse sequence composed of “0” corresponding to an element whose value is “0” in the transformed weight matrix, and “1” corresponding to an element whose value is not 0 in the transformed weight matrix; When the matrix operation unit performs the matrix multiplication operation, the thinning unit extracts an element of a corresponding position in the transformed neuron matrix according to the “1” of the sparse sequence record, and the transformed weight The corresponding elements in the matrix are multiplied. The convolution operation device of a neural network according to claim 6, further comprising a data access unit for acquiring a neuron matrix and a weight matrix from an external address space and providing the same to the processor. The convolution operation device of the neural network according to claim 6, further comprising a data buffer unit for buffering data generated by said processor. A computer readable storage medium storing instructions, wherein the instructions are executable by a processor to cause the processor to perform the method of any of claims 1-5.

Images