SYSTEM AND METHOD OF PERFORMING CONVOLUTION EFFICIENTLY ADAPTING WINOGRAD ALGORITHM

1 . A method of convolving an input tensor with weights w using hardware comprising a plurality of linear operation engines, the method being an adaptation of a Winograd algorithm, the Winograd algorithm splitting each input channel i of a total of C in input channels into one or more tiles d i and calculating a result A[Σ i=1 C in (Gw ji G T )∘(B T d i B)]A T for each output channel j, wherein G, B and A are constant matrices, the method comprising:

determining a first filter F 1 from matrix B wherein the filter F 1 comprises n kernels, each kernel being an outer product of two columns of the matrix B; and

using the linear operation engines to perform a convolution of the input tensor with the first filter F 1 .

2 . The method according to claim 1 , wherein the convolution of the input tensor with the first filter F 1 is performed for determining a tensor equivalent to B T d i B, for all tiles of all input channels i.

3 . The method according to claim 1 , wherein the convolution of the input tensor with the first filter F 1 includes performing a first grouped convolution of each input channel i of the input tensor with the n kernels of the first filter F 1 to generate a first intermediate tensor having C in groups of n channels, and wherein the method further comprises determining a tensor equivalent to Σ i=1 C in (Gw ji G T )∘(B T d i B) by using the linear operation engines to perform a second grouped convolution with a weight tensor W′, the weight tensor W′ being composed of partial weight tensors W′ji, where each W′ji is determined from constant matrix G and is equivalent to Gw ji G T .

4 . The method according to claim 3 ,

wherein C in =1, and the second grouped convolution is a grouped convolution of the first intermediate tensor with the weight tensor W′; or

wherein:

C in ≥2;

before performing the second grouped convolution, the method comprises permuting the channels of the first intermediate tensor to rearrange the C in groups of n channels into n groups of C in channels; and

the second grouped convolution is a grouped convolution of the n groups of C in channels with the weight tensor W′.

5 . The method according to claim 4 , wherein the second grouped convolution operation is performed by convolving each group of the first intermediate tensor with a corresponding part of the weight tensor W′ to generate a second intermediate tensor having n groups of C out channels.

6 . The method according to claim 5 , wherein the method further comprises determining a tensor equivalent to the result A[Σ i=1 C in (Gw ji G T )∘(B T d i B)]A T for each output channel j by using the linear operation engines to perform convolution transpose using a second filter F 2 to generate an output tensor having C out channels.

7 . The method according to claim 6 ,

wherein C out =1, and the convolution transpose is of the second intermediate tensor; or

wherein:

C out ≥2;

before performing the convolution transpose, the method further comprises permuting the channels of the second intermediate tensor to rearrange the n groups of C out channels into C out groups of n channels; and

the convolution transpose is of the C out groups of n channels.

8 . The method according to claim 6 , wherein the second filter F 2 comprises a plurality of kernels, each kernel being an outer product of two columns of the matrix A.

9 . The method according to claim 3 , wherein the first grouped convolution is a stride m convolution to generate an (h/m)×(b/m) first intermediate tensor, where m is equal to the output tile size of the Winograd algorithm being adapted.

10 . The method according to claim 1 , wherein the convolution of the input tensor with the first filter F 1 includes performing n separate grouped convolutions of the C in input channels, each grouped convolution applying a corresponding kernel of the first filter F 1 to generate n separate first results, each having C in channels.

11 . The method according to claim 10 , wherein the method further comprises:

after performing the n separate grouped convolutions, concatenating the n first results to generate a first intermediate tensor having n groups of Cn channels,

determining Σ i=1 C in (Gw ji G T )∘(Bd i B T ) by using the linear operation engines, to perform a second grouped convolution by convolving each group of the first intermediate tensor having C in channels with a corresponding part of the weight tensor W′ to generate a second intermediate tensor having n groups of C out channels, where W′ is determined from constant matrix G and is equivalent to the matrices Gw ji G T for all output channels j and input channels i; and

permuting the channels of the second intermediate tensor having n groups of C out channels to generate C out groups of n channels; and

determining the result A[Σ i=1 C in (Gw ji G T )∘(Bd i B T )]A T by using the linear operation engines to perform convolution transpose of the second intermediate tensor using the second filter F 2 to generate an output tensor having C out channels.

12 . The method according to claim 10 , wherein the method further comprises, after performing the n separate grouped convolutions to generate n separate first results, performing another n separate convolutions of each of the first results with a corresponding kernel of the weight tensor to generate n second results, each having C out channels.

13 . The method according to claim 12 , wherein after performing the another n separate convolutions, concatenating the n second results having C out channels to generate a second intermediate tensor having n groups of C out channels.

14 . The method according to claim 13 , wherein after performing concatenation, the method further comprises:

permuting the channels of the second intermediate tensor having n groups of C out channels to generate C out groups of n channels; and

determining the result A[Σ i=1, C in , (Gw ji G T )∘(Bd i B T )]A T by using the linear operation engines to perform convolution transpose of the second intermediate tensor using the second filter F 2 to generate an output tensor having C out channels.

15 . The method according to claim 12 , wherein the method further comprises after performing the another n separate grouped convolutions to generate n second results, interleaving the second results on a spatial axis to generate a third result.

16 . The method according to claim 15 , wherein the method further comprises obtaining an output tensor having C out channels by performing a third grouped convolution followed by depth to space conversion.

17 . A data processing system for implementing a neural network comprising a plurality of layers, wherein at least one of the layers is configured to perform an adaptation of a Winograd algorithm, the Winograd algorithm splitting each input channel i of a total of C in input channels into one or more tiles d i and that calculates a result A[Σ i=1 C in (Gw ji G T )∘(B T d i B)]A T convolution of an input tensor with weights w as part of an adaptation of a Winograd algorithm, the Winograd algorithm splitting each input channel i of a total of C in input channels into one or more tiles d i and calculating a result A[Σ i=1 C in (Gw ji G T )∘(B T d i B)]A T for each output channel j, wherein G, B and A are constant matrices, the data processing system comprising:

a neural network accelerator comprising a plurality of linear operation engines implemented in a fixed-function hardware circuitry, wherein the data processing system is configured to:

determine a first filter F 1 from matrix B wherein the filter F 1 comprises n kernels, each kernel being an outer product of two columns of the matrix B; and

using the linear operation engines, perform a convolution of the input tensor with the first filter F 1 .

18 . The data processing system of claim 17 , wherein the data processing system further comprises a memory configured for storing a plurality of predetermined factors including the constant matrices G, B and A, a first filter based on matrix B, a second filter based on matrix A and a weight tensor W based on matrix G.

19 . A data processing system for implementing a neural network configured to perform the method as set forth in claim 1 .

20 . A non-transitory computer readable storage medium having stored thereon computer readable code configured to cause the method as set forth in claim 1 to be performed when the code is run.