Nibble Block Format

A matrix multiplication system and method are provided. The system includes a memory that stores one or more weight tensors, a processor and a matrix multiply accelerator (MMA). The processor converts each weight tensor into an encoded block set that is stored in the memory. Each encoded block set includes a number of encoded blocks, and each encoded block includes a data field and an index field. The MMA converts each encoded block set into a reconstructed weight tensor, and convolves each reconstructed weight tensor and an input data tensor to generate an output data matrix.

BACKGROUND

The present disclosure relates to computer systems. More particularly, the present disclosure relates to a matrix multiplication system and method.

Artificial neural networks (ANNs), such as deep neural networks (DNNs), convolutional neural networks (CNNs), etc., are a popular solution to a wide array of challenging classification, recognition and regression problems. However, many ANN models require a large number of matrix calculations involving a large number of weights and activations, which presents a significant challenge with respect to access, storage and performance, particularly for mobile and other power or storage-constrained devices. An ANN hardware accelerator accelerates these matrix calculations, such as, for example, convolution operations performed by CNNs.

Generally, matrices may be classified as either sparse or dense. Most elements of a sparse matrix have a value of zero, while most elements of a dense matrix have a non-zero value. For the simple matrix multiplication operation C=A·B, when matrix A or matrix B is sparse, most of the matrix calculations will include a value of zero for at least one of the operands. When both matrix A and matrix B are sparse, an even greater number of matrix calculations will include a value of zero for at least one of the operands. Since multiplication by an operand that has a value of zero will always result in a product that has a value of zero, applying standard matrix multiplication techniques to sparse matrices is very inefficient due to the large number of operands that have a value of zero. Additionally, sparse matrices are allocated memory storage space in excess of their actual requirements due to the large number of elements that have a value of zero.

ANN matrices may be sparse or dense, with values that range from a minimum value to a maximum value, such as, for example, 0 to 255 for a matrix storing 8-bit unsigned integers, −128 to 127 for a matrix storing signed 8-bit integers, etc. Many ANN matrices, such as CNN weight matrices, include a large number of zero values, a number of small magnitude values, and a small number of large magnitude values. In other words, CNN weight matrices often have very sparse data with some small weight values and an occasional, and important, large weight value. Similar to sparse matrices in general, applying standard matrix multiplication techniques to many ANN matrices is very inefficient, and these matrices are allocated memory storage space in excess of their actual requirements.

DETAILED DESCRIPTION

Embodiments of the present disclosure will now be described with reference to the drawing figures, in which like reference numerals refer to like parts throughout.

Deep neural network inference involves operating on large tensors. Loading and manipulating this data tends to dominate the power consumption of inference tasks, even when running on custom hardware, such as an neural processing unit (NPU), graphics processing unit (GPU), etc. The cost may be advantageously reduced for ANN weight tensors, for example, by quantizing the weights to reduce the number of bits per weight, and pruning the weights to remove small values at or close to zero.

Embodiments of the present disclosure advantageously provide a matrix encoding process that reduces storage requirements and allows for flexibility in both quantization and pruning within a fixed block size format. ANN data, such as ANN weight tensors, tend to have a large number of zeros, a smaller number of non-zeros, and an even smaller number of large magnitude non-zero values. Embodiments of the present disclosure advantageously provide a block-based encoding process for ANN data, such as weight tensors, that is of fixed storage size, but allows trade-off in the tensor elements between zero values, small non-zero values and large non-zero values. Many embodiments of the present disclosure also provide a fixed computation size per block, which is advantageous in many situations.

In one embodiment, a system includes a memory, a processor coupled to the memory and a matrix multiply accelerator (MMA) coupled to the processor and the memory. The memory is configured to store one or more weight tensors, each weight tensor including a number of weights. The processor is configured, for each weight tensor, to generate, based on the weight tensor, a basic block matrix set including a number of basic block matrices, each basic block matrix including a number of weights; to generate, based on the basic block matrix set, an encoded block set, the encoded block set including a number of encoded blocks, each encoded block including a data field and an index field, the data field including a number of encoded weights, the index field including an index associated with each weight in the basic block matrix, the number of encoded weights being less than the number of weights in the basic block matrix, each encoded block having a same size; and to store the encoded block set in the memory. The MMA is configured to convert each encoded block set into a reconstructed weight tensor having a number of weights equal to the number of weights of the respective weight tensor, and convolve each reconstructed weight tensor and an input data tensor to generate an output data matrix.

An ANN models the relationships between input data or signals and output data or signals using a network of interconnected nodes that is trained through a learning process. The nodes are arranged into various layers, including, for example, an input layer, one or more hidden layers, and an output layer. The input layer receives input data, such as, for example, image data, and the output layer generates output data, such as, for example, a probability that the image data contains a known object. Each hidden layer provides at least a partial transformation of the input data to the output data. A DNN has multiple hidden layers in order to model complex, nonlinear relationships between input data and output data.

In a fully-connected, feedforward ANN, each node is connected to all of the nodes in the preceding layer, as well as to all of the nodes in the subsequent layer. For example, each input layer node is connected to each hidden layer node, each hidden layer node is connected to each input layer node and each output layer node, and each output layer node is connected to each hidden layer node. Additional hidden layers are similarly interconnected. Each connection has a weight value, and each node has an activation function, such as, for example, a linear function, a step function, a sigmoid function, a tanh function, a rectified linear unit (ReLU) function, etc., that determines the output of the node based on the weighted sum of the inputs to the node. The input data propagates from the input layer nodes, through respective connection weights to the hidden layer nodes, and then through respective connection weights to the output layer nodes.

More particularly, at each input node, input data is provided to the activation function for that node, and the output of the activation function is then provided as an input data value to each hidden layer node. At each hidden layer node, the input data value received from each input layer node is multiplied by a respective connection weight, and the resulting products are summed or accumulated into an activation value that is provided to the activation function for that node. The output of the activation function is then provided as an input data value to each output layer node. At each output layer node, the output data value received from each hidden layer node is multiplied by a respective connection weight, and the resulting products are summed or accumulated into an activation value that is provided to the activation function for that node. The output of the activation function is then provided as output data. Additional hidden layers may be similarly configured to process data.

FIG.1Adepicts ANN10, in accordance with an embodiment of the present disclosure.

In one embodiment, N equals 3, i equals 3, j, k and m equal 5 and o equals 2 (depicted inFIG.1A). Input node21is coupled to hidden nodes31to35, input node22is coupled to hidden nodes31to35, and input node23is coupled to hidden nodes31to35. Hidden node31is coupled to hidden nodes41to45, hidden node32is coupled to hidden nodes41to45, hidden node33is coupled to hidden nodes41to45, hidden node34is coupled to hidden nodes41to45, and hidden node35is coupled to hidden nodes41to45. Hidden node41is coupled to hidden nodes51to55, hidden node42is coupled to hidden nodes51to55, hidden node43is coupled to hidden nodes51to55, hidden node44is coupled to hidden nodes51to55, and hidden node45is coupled to hidden nodes51to55. Hidden node51is coupled to output nodes61and62, hidden node52is coupled to output nodes61and62, hidden node53is coupled to output nodes61and62, hidden node54is coupled to output nodes61and62, and hidden node55is coupled to output nodes61and62.

Many other variations of input, hidden and output layers are clearly possible, including hidden layers that are locally-connected, rather than fully-connected, to one another.

Training an ANN includes optimizing the connection weights between nodes by minimizing the prediction error of the output data until the ANN achieves a particular level of accuracy. One method is backpropagation, or backward propagation of errors, which iteratively and recursively determines a gradient descent with respect to the connection weights, and then adjusts the connection weights to improve the performance of the network.

A multi-layer perceptron (MLP) is a fully-connected ANN that has an input layer, an output layer and one or more hidden layers. MLPs may be used for natural language processing applications, such as machine translation, speech recognition, etc. Other ANNs include recurrent neural networks (RNNs), long short-term memories (LSTMs), sequence-to-sequence models that include an encoder RNN and a decoder RNN, shallow neural networks, etc.

A CNN is a variation of an MLP that may be used for classification or recognition applications, such as image recognition, speech recognition, etc. Typically, native convolution operations are not performed by a CNN due to the complicated dataflow and expensive datapaths that are usually required. Instead, native convolution operations are converted into generic matrix multiplication (GEMM) operations, and then the GEMM operations are executed more efficiently by a central processing unit (CPU), specialized processor, hardware accelerator processing engine, etc., using optimized software libraries or specialized hardware. More particularly, an “IM2COL” software function may be used to convert the filter (weight) matrix and the input feature map (IFM) matrix for each convolution operation into an expanded format that is compatible with a GEMM operation. The IM2COL versions of each filter (weight) matrix and each IFM matrix are generated and stored in memory, and then loaded from memory and processed by the GEMM operation.

A CNN has an input layer, an output layer and multiple hidden layers including convolutional layers, pooling layers, normalization layers, fully-connected layers, etc. Each convolutional layer applies a sliding dot product or cross-correlation to an input volume, applies an activation function to the results, and then provides the activation or output volume to the next layer. Convolutional layers typically use the ReLU function as the activation function. In certain embodiments, the activation function is provided in a separate activation layer, such as, for example, a ReLU layer. A pooling layer reduces the dimensions of the output volume received from the preceding convolutional layer, and may calculate an average or a maximum over small clusters of data, such as, for example, 2×2 matrices. In certain embodiments, a convolutional layer and a pooling layer may form a single layer of a CNN. The fully-connected layers follow the convolutional and pooling layers, and include a flatten layer and a classification layer, followed by a normalization layer that includes a normalization function, such as the SoftMax function. The output layer follows the last fully-connected layer; in certain embodiments, the output layer may include the normalization function.

FIG.1Bdepicts CNN15, in accordance with an embodiment of the present disclosure.

CNN15includes input layer20, one or more hidden layers, such as convolutional layer30-1, pooling layer30-2, hidden (flatten) layer40, hidden (classification) layer50, etc., and output layer60. Many other variations of input, hidden and output layers are contemplated.

Input layer20includes one or more input nodes21, etc., that present the input data, such as a color image, as an input volume to the first convolutional layer, e.g., convolutional layer30-1. The input volume is a three-dimensional matrix that has a width, a height and a depth. For example, input data that represent a color image are presented as an input volume that is 512 pixels×512 pixels×3 channels (red, green, blue); other input volume dimensions may also be used, such as 32×32×3, 64×64×3, 128×128×3, etc., 32×32×1, 64×64×1, 128×128×1, 512×512×1, etc.

Convolutional layer30-1is locally-connected to input layer20, and includes a plurality of nodes that are connected to local regions in the input volume (not depicted for clarity). For a CNN that uses a standard convolution, each node computes a dot product between the node's weights and the respective local region of the input volume. An activation function is then applied to the results of each convolution calculation to produce an output volume that is provided as an input volume to the subsequent layer. The activation function may be applied by each convolutional layer node or by the nodes of a subsequent locally-connected ReLU layer.

Pooling layer30-2is locally-connected to convolutional layer30-1, and includes a plurality of nodes that are connected to local regions in the input volume (not depicted for clarity). Pooling layer30-2also produces an output volume that is provided as the input volume to the subsequent layer, such as, for example, another convolutional layer30-1, a flatten layer40, etc. In certain embodiments, convolutional layer30-1and pooling layer30-2form a single hidden layer30. Similarly, in certain embodiments, convolutional layer30-1, a ReLU layer and pooling layer30-2form a single hidden layer30. Generally, the output volumes of the convolutional and pooling layers may be described as feature maps, and one or more single hidden layers30form a feature learning portion of CNN15.

Hidden layer40is a “flatten” layer that is locally-connected to pooling layer30-2, and includes one or more hidden (flatten) nodes41,42,43,44,45, etc. Hidden (flatten) layer40“flattens” the output volume produced by the preceding pooling layer30-2into a column vector, which is provided to the subsequent, fully-connected hidden layer50.

Hidden layer50is a classification layer that is fully-connected to hidden (flatten) layer40, and includes one or more hidden (classification) nodes51,52,53,54,55, etc.

Output layer60includes one or more output nodes61,62, etc., and is fully-connected to hidden (classification) layer50. Fully-connected output layer60receives the classification results output by hidden (classification) layer50, and each node outputs a predicted class score. A normalization function, such as a Softmax function, may be applied to the predicted class scores by output layer60, or, alternatively, by an additional layer interposed between hidden (classification) layer50and output layer60.

Similar to ANNs, training a CNN includes optimizing the connection weights between nodes by minimizing the prediction error of the output data until the CNN achieves a particular level of accuracy. As noted above, backpropagation may be used to iteratively and recursively determines a gradient descent with respect to the connection weights, and then adjusts the connection weights to improve the performance of the network. Matrix multiplication operations, and, more particularly, multiply-and-accumulate (MAC) operations, are used extensively by CNNs, as well as other ANNs.

FIG.2Adepicts convolutional layer calculation200for a CNN, in accordance with an embodiment of the present disclosure.

Input feature maps form an input data tensor204that includes eight input channels and one input data matrix for each channel, i.e., input data matrices2041,2042,2043,2044,2045,2046,2047and2048. Filter202includes three filter or weight tensors2021,2022and2023, and each filter or weight tensor includes eight weight matrices, one weight matrix for each channel, i.e., weight tensor2021includes weight matrices20211,20212,20213,20214,20215,20216,20217and20218, weight tensor2022includes weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and weight tensor2023includes weight matrices20231,20232,20233,20234,20235,20236,20237and20238. Output feature maps form an output data tensor206that includes three output channels and one output data matrix for each filter or weight tensor, i.e., output data matrices2061,2062and2063. Convolutional layer calculation200convolves weight tensors2021,2022and2023with input data tensor204to produce output data tensor206.

Each tensor has a height, a width and a depth. The depth of the input data tensor is equal to the number of input channels, the depth of each weight tensor is equal to the number of input channels, and the depth of the output tensor is equal to the number of output channels, i.e., the number of weight tensors in the filter. While the particular dimensions for the tensors and constituent matrices have been selected for clarity of illustration and explanation, embodiments of the present disclosure are not so limited. For example, a convolutional layer calculation may include four input channels and one output channel, a filter with one weight tensor with four weight matrices, an input data tensor with four input data matrices, and an output data tensor with one output data matrix. In this example, the weight tensor is convolved with the input data tensor to generate the output data matrix.

In this embodiment, each output data matrix2061,2062and2063is a 3×3 matrix associated with a different output channel and includes 9 output elements. For example, output data matrix2061is associated with the first output channel and includes outputs o11, o12, o13, o14, o15, o16, o17, o18and o19, output data matrix2062is associated with the second output channel and includes outputs o21, o22, o23, o24, o25, o26, o27, o28and o29, and output data matrix2063is associated with the third output channel and includes outputs o31, o32, o33, o34, o35, o36, o37, o38and o39.

For ease of explanation, each input data matrix input data matrix2041,2042,2043,2044,2045,2046,2047and2048may be divided into three quadrants. The first quadrant spans the top (first) row, second row third row and fourth row, the second quadrant spans the second row, third row, fourth row and fifth row, and the third quadrant spans the third row, fourth row, fifth row and sixth (bottom) row. The first quadrant for input data matrix2041(a1q1) and the first quadrant for input data matrix2048(a8q1) are labeled; the remaining quadrants for each input data matrix are not labeled for clarity. The elements of each quadrant for input data matrix2041are described as follows, and the quadrants of input data matrices2042,2043,2044,2045,2046,2047and2048are similarly arranged.

Output data tensor206may also be divided into three quadrants; in this case, each quadrant spans all three output data matrices2061,2062and2063. The first quadrant spans the top (first) row of each output data matrix, the second quadrant spans the second row of each output data matrix, and the third quadrant spans the fourth (bottom) row of each output data matrix. The first quadrant for output data matrices2061,2062and2063(i.e., o1q1, o2q1and o3q1) is labeled; the remaining quadrants are not labeled for clarity.

Generally, each output element within output data matrices2061,2062and2063is the sum of the dot products of one of the weight tensors2021,2022and2023and a block of activation elements within a particular quadrant of input data matrices2041,2042,2043,2044,2045,2046,2047and2048.

The calculation of the output elements in first quadrants o1q1, o2q1and o3q1follows.

More particularly, the following dot products are summed to generate output element o11: the dot product of the first weight matrix20211of weight tensor2021and the first block of quadrant a1q1of input data matrix2041(i.e., w11·a11+w12·a12+w13·a13+w14·a14+w15·a17+w16·a18+w17·a19+w18·a110+w19·a113+w110·a114+w111·a115+w112·a116+w113·a119+w114·a120+w115·a121+w116·a122), the dot product of the second weight matrix20212of weight tensor2021and the first block of quadrant a2q1of input data matrix2042(i.e., w21·a21+w22·a22+w23·a23+w24·a24+w25·a27+w26·a28+w27·a29+w28·a210+w29·a213+w210·a214+w211·a215+w212·a216+w213·a219+w214·a220+w215·a221+w216·a222), the dot product of the third weight matrix20213of weight tensor2021and the first block of quadrant a3q1of input data matrix2043(i.e., w31·a31+w32·a32+w33·a33+w34·a34+w35·a37+w36·a38+w37·a39+w38·a310+w39·a313+w310·a314+w311·a315+w312·a316+w313·a319+w314·a320+w315·a321+w316·a322), the dot product of the fourth weight matrix20214of weight tensor2021and the first block of quadrant a4q1of input data matrix2044(i.e., w41·a41+w42·a42+w43·a43+w44·a44+w45·a47+w46·a48+w47·a49+w48·a410+w49·a413+w410·a414+w411·a415+w412·a416+w413·a419+w414·a420+w415 *421+w416·a422), the dot product of the fifth weight matrix20215of weight tensor2021and the first block of quadrant a5q1of input data matrix2045(i.e., w51·a51+w52·a52+w53·a53+w54·a54+w55·a57+w56·a58+w57·a59+w58·a510+w59·a513+w510·a514+w511·a515+w512·a516+w513·a519+w514·a520+w515·a521+w516·a522), the dot product of the sixth weight matrix20216of weight tensor2021and the first block of quadrant a6q1of input data matrix2046(i.e., w61·a61+w62·a62+w63·a63+w64·a64+w65·a67+w66·a68+w67·a69+w68·a610+w69·a613+w610·a614+w611·a615+w612·a616+w613·a619+w614·a620+w615·a621+w616·a622), the dot product of the seventh weight matrix20217of weight tensor2021and the first block of quadrant a7q1of input data matrix2047(i.e., w71·a71+w72·a72+w73·a73+w74·a74+w75·a77+w76·a78+w77·a79+w78·a710+w79·a713+w710·a714+w711·a715+w712·a716+w713·a719+w714·a720+w715·a721+w716·a722), and the dot product of the eighth weight matrix20218of weight tensor2021and the first block of quadrant a8q1of input data matrix2048(i.e., w81·a81+w82·a82+w83·a83+w84·a84+w85·a87+w86·a88+w87·a89+w88·a810+w89·a813+w810·a814+w811·a815+w812·a816+w813·a819+w814·a820+w815·a821+w816·a822).

Similarly, output element o21of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the first block of activation elements within first quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

And, output element o31of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,20233,20234,20235,20236,20237and20238, and the first block of activation elements within first quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

More particularly, the following dot products are summed to generate output element o12: the dot product of the first weight matrix20211of weight tensor2021and the second block of quadrant a1q1of input data matrix2041(i.e., w11·a12+w12·a13+w13·a14+w14·a15+w15·a18+w16·a19+w17·a110+w18·a111+w19·a114+w110·a115+w111·a116+w112·a117+w113·a120+w114·a121+w115·a122+w116·a123), the dot product of the second weight matrix20212of weight tensor2021and the second block of quadrant a2q1of input data matrix2042(i.e., w21·a22+w22·a23+w23·a24+w24·a25+w25·a28+w26·a29+w27·a210+w28·a211+w29·a214+w210·a215+w211·a216+w212·a217+w213·a220+w214·a221+w215·a222+w216·a223), the dot product of the third weight matrix20213of weight tensor2021and the second block of quadrant a3q1of input data matrix2043(i.e., w31·a32+w32·a33+w33·a34+w34·a35+w35·a38+w36·a39+w37·a310+w38·a311+w39·a314+w310·a315+w311·a316+w312·a317+w313·a320+w314·a321+w315·a322+w316·a323), the dot product of the fourth weight matrix20214of weight tensor2021and the second block of quadrant a4q1of input data matrix2044(i.e., w41·a42+w42·a43+w43·a44+w44·a45+w45·a48+w46·a49+w47·a410+w48·a411+w49·a414+w410·a415+w411·a416+w412 *417+w413·a420+w414·a421+w415·a422+w416·a423), the dot product of the fifth weight matrix20215of weight tensor2021and the second block of quadrant a5q1of input data matrix2045(i.e., w51·a52+w52·a53+w53·a54+w54·a55+w55·a58+w56·a59+w57·a510+w58·a511+w59·a514+w510·a515+w511·a516+w512·a517+w513·a520+w514·a521+w515·a522+w516·a523), the dot product of the sixth weight matrix20216of weight tensor2021and the second block of quadrant a6q1of input data matrix2046(i.e., w61·a62+w62·a63+w63·a64+w64·a65+w65·a68+w66·a69+w67·a610+w68·a611+w69·a614+w610·a615+w61·a616+w612·a617+w613·a620+w614·a621+w615·a622+w616·a623), the dot product of the seventh weight matrix20217of weight tensor2021and the second block of quadrant a7q1of input data matrix2047(i.e., w71·a72+w72·a73+w73·a74+w74·a75+w75·a78+w76·a79+w77·a710+w78·a7110+w79·a714+w710·a715+w711·a716+w712·a717+w713·a720+w714·a721+w715·a722+w716·a723), and the dot product of the eighth weight matrix20218of weight tensor2021and the second block of quadrant a8q1of input data matrix2048(i.e., w81·a82+w82·a83+w83·a84+w84·a85+w85·a88+w86·a89+w87·a810+w88·a811+w89·a814+w810·a815+w811·a816+w812·a817+w813·a820+w814·a8210+w815·a822+w816·a823).

Similarly, output element o22of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the second block of activation elements within first quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

And, output element o32of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,20233,20234,20235,20236,20237and20238, and the second block of activation elements within first quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

More particularly, the following dot products are summed to generate output element o13: the dot product of the first weight matrix20211of weight tensor2021and the third block of quadrant a1q1of input data matrix2041(i.e., w11·a13+w12·a14+w13·a15+w14·a16+w15·a19+w16·a110+w17·a111+w18·a112+w19·a115+w110·a116+w111·a117+w112·a118+w113·a121+w114·a122+w115·a123+w116·a124), the dot product of the second weight matrix20212of weight tensor2021and the third block of quadrant a2q1of input data matrix2042(i.e., w21·a23+w22·a24+w23·a25+w24·a26+w25·a29+w26·a210+w27·a211+w28·a212+w29·a215+w210·a216+w211·a217+w212·a218+w213·a221+w214·a222+w215·a23+w216·a224), the dot product of the third weight matrix20213of weight tensor2021and the third block of quadrant a3q1of input data matrix2043(i.e., w31·a33+w32·a34+w33·a35+w34·a36+w35·a39+w36·a310+w37·a311+w38·a312+w39·a315+w310·a316+w311·a317+w312·a318+w313·a321+w314·a32+w315·a32+w316·a324), the dot product of the fourth weight matrix20214of weight tensor2021and the third block of quadrant a4q1of input data matrix2044(i.e., w41·a43+w42·a44+w43·a45+w44·a46+w45·a49+w46·a410+w47·a411+w48·a412+w49·a415+w410·a416+w411·a417+w412·a418+w413·a421+w414·a422+w415·a423+w416·a424), the dot product of the fifth weight matrix20215of weight tensor2021and the third block of quadrant a5q1of input data matrix2045(i.e., w51·a53+w52·a54+w53·a55+w54·a56+w55·a59+w56·a510+w57·a511+w58·a512+w59·a515+w510·a516+w511·a517+w512·a518+w513·a521+w514·a522+w515·a523+w516·a524), the dot product of the sixth weight matrix20216of weight tensor2021and the third block of quadrant a6q1of input data matrix2046(i.e., w61·a63+w62·a64+w63·a65+w64·a66+w65·a69+w66·a610+w67·a611+w68·a612+w69·a615+w610·a616+w611·a617+w612·a618+w613·a621+w614·a622+w615·a623+w616·a624), the dot product of the seventh weight matrix20217of weight tensor2021and the third block of quadrant a7q1of input data matrix2047(i.e., w71·a73+w72·a74+w73·a75+w74·a76+w75·a79+w76·a710+w77·a711+w78·a712+w79·a715+w710·a716+w711·a717+w712·a718+w713 *721+w714·a722+w715·a723+w716·a724), and the dot product of the eighth weight matrix20218of weight tensor2021and the third block of quadrant a8q1of input data matrix2048(i.e., w81·a83+w82·a84+w83·a85+w84·a86+w85·a89+w86·a810+w87·a811+w88·a812+w89·a815+w810·a816+w811·a817+w812·a818+w813·a821+w814·a822+w815·a823+w816·a824).

Similarly, output element o23of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the third block of activation elements within first quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

And, output element o3of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,2023,20234,20235,20236,20237and20238, and the third block of activation elements within first quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

The calculation of the output elements in second quadrants o1q2, o2q2and o3q2follows.

Output element o14of output data matrix2061is the sum of the dot products of weight tensor2021, i.e., weight matrices20211,20212,20213,20214,20215,20216,20217and20218, and the first block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Similarly, output element o24of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the first block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. And, output element o34of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,2023,20234,20235,20236,20237and20238, and the first block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

Output element o15of output data matrix2061is the sum of the dot products of weight tensor2021, i.e., weight matrices20211,20212,20213,20214,20215,20216,20217and20218, and the second block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Similarly, output element o25of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the second block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

And, output element o35of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,2023,20234,20235,20236,20237and20238, and the second block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

Output element o16of output data matrix2061is the sum of the dot products of weight tensor2021, i.e., weight matrices20211,20212,20213,20214,20215,20216,20217and20218, and the third block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Output element o26of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the third block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Output element o36of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices2023,20232,2023,20234,20235,20236,20237and20238, and the third block of activation elements within second quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a1q2and a8q2of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

The calculation of the output elements in third quadrants o1q3, o2q3and o3q3follows.

Output element o17of output data matrix2061is the sum of the dot products of weight tensor2021, i.e., weight matrices20211,20212,20213,20214,20215,20216,20217and20218, and the first block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Output element o27of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the first block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. And, output element o34of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,2023,20234,20235,20236,20237and20238, and the first block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

Output element o18of output data matrix2061is the sum of the dot products of weight tensor2021, i.e., weight matrices20211,20212,20213,20214,20215,20216,20217and20218, and the second block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Similarly, output element o28of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the second block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. And, output element o38of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,2023,20234,20235,20236,20237and20238, and the second block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

Output element o19of output data matrix2061is the sum of the dot products of weight tensor2021, i.e., weight matrices20211,20212,20213,20214,20215,20216,20217and20218, and the third block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Output element o29of output data matrix2062is the sum of the dot products of weight tensor2022, i.e., weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and the third block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively. Output element o39of output data matrix2063is the sum of the dot products of weight tensor2023, i.e., weight matrices20231,20232,2023,20234,20235,20236,20237and20238, and the third block of activation elements within third quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3of input data matrices2041,2042,2043,2044,2045,2046,2047and2048, respectively.

FIG.2Bdepicts converted convolutional layer calculation210for a CNN, in accordance with an embodiment of the present disclosure.

In one embodiment, the convolutional layer calculations for CNNs executing on central processor units (CPUs), GPUs, NPUs, etc. may be converted into generic matrix multiplication (GEMM) operations, which may leverage GEMM-optimized software libraries. Convolution layer calculation200is converted into a GEMM operation by converting filter202into converted weight matrix212, converting input data tensor204into converted input data matrix214, and then multiplying converted weight matrix212and converted input data matrix214to generate converted output data matrix216. Because simple matrix multiplication is performed rather than a convolution operation, each output element within converted output data matrix216is the dot product of one row of converted weight matrix212and one column of converted input data matrix214. Converted output data matrix216is then reformed into output data tensor206.

Converted weight matrix212is a 3×128 matrix, and includes converted weight tensors2121,2122and2123. Weight tensor2021is flattened to form converted weight tensor2121, i.e., the first row, weight tensor2022is flattened to form converted weight tensor2122, i.e., the second row, and weight tensor2023is flattened to form converted weight tensor2123, i.e., the third row.

More particularly, the first column of converted input data matrix214includes the first blocks from quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1, the second column of converted input data matrix214includes the second blocks from quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1, and the third column of converted input data matrix214includes the third blocks from quadrants a1q1, a2q1, a3q1, a4q1, a5q1, a6q1, a7q1and a8q1.

The remaining columns of converted input data matrix214are formed in a similar manner. The fourth column of converted input data matrix214includes the first blocks from quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2, the second column of converted input data matrix214includes the second blocks from quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2, and the third column of converted input data matrix214includes the third blocks from quadrants a1q2, a2q2, a3q2, a4q2, a5q2, a6q2, a7q2and a8q2. The seventh column of converted input data matrix214includes the first blocks from quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3, the second column of converted input data matrix214includes the second blocks from quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3, and the third column of converted input data matrix214includes the third blocks from quadrants a1q3, a2q3, a3q3, a4q3, a5q3, a6q3, a7q3and a8q3.

Converted output data matrix216is a 3×9 matrix, and includes flattened versions of output data matrices2061,2062and2063, i.e., converted output data matrices2161,2162and2163. Converted output data matrix216may also be arranged into three quadrants; in this case, each quadrant spans all three converted output data matrices2161,2162and2163. The first quadrant spans the first three columns of converted output data matrix216, the second quadrant spans the next three columns of converted output data matrix216, and the third quadrant spans the last three columns of converted output data matrix216. The first quadrant for each converted output data matrix2161,2162and2163(i.e., o1, o2q1and o3q1) is labeled; the remaining quadrants are not labeled for clarity.

The calculation of the output elements in quadrant o1q1of converted output data matrix2161follows.

Output element o11is the dot product of the first row of converted weight matrix212, i.e., converted weight tensor2121, and the first column of converted input data matrix214.

More particularly, output element o11is equal to w11·a11+w12·a12+w13·a13+w14·a14+w15·a17+w16·a18+w17·a19+w18·a110+w19·a113+w110·a114+w111·a115+w112·a116+w113·a119+w114·a120+w115·a121+w116·a122+w21·a21+w22·a22+w23·a23+w24·a24+w25·a27+w26·a28+w27·a29+w28·a210+w29·a213+w210·a214+w211·a215+w212·a216+w213·a219+w214·a220+w215·a221+w216·a222+w31·a31+w32·a32+w33·a33+w34·a34+w35·a37+w36·a38+w37·a39+w38·a310+w39·a313+w310·a314+w311·a315+w312·a316+w313·a319+w314·a320+w315·a321+w316·a322+w41·a41+w42·a42+w43·a43+w44·a44+w45·a47+w46·a48+w47·a49+w48·a410+w49·a413+w410·a414+w411·a415+w412·a416+w413·a419+w414·a420+w415·a421+w416·a422+w5·a51+w52·a52+w53·a53+w54·a54+w55·a57+w56·a58+w57·a59+w58·a510+w59·a513+w510·a514+w511·a515+w512·a516+w513·a519+w514·a520+w515·a521+w516·a522+w61·a61+w62·a62+w63·a63+w64·a64+w65·a67+w66·a68+w67·a69+w68·a610+w69·a613+w610·a614+w61·a615+w612·a616+w613·a619+w614·a620+w615·a621+w616·a622+w71·a71+w72·a72+w73·a73+w74·a74+w75·a77+w76·a78+w77·a79+w78·a710+w79·a713+w710·a714+w711·a715+w712·a716+w713·a719+w714·a720+w715·a721+w716·a722+w81·a81+w82·a82+w83·a83+w84·a84+w85·a87+w86·a88+w87·a89+w88·a810+w89·a813+w810·a814+w811·a815+w812·a816+w813·a819+w814·a820+w815·a821+w816·a822.

Output element o12is the dot product of the first row of converted weight matrix212, i.e., converted weight tensor2121, and the second column of converted input data matrix214.

More particularly, output element o12is equal to w11·a12+w12·a13+w13·a14+w14·a15+w15·a18+w16·a19+w17·a110+w18·a111+w19·a114+w110·a115+w111·a16+w112·a117+w113·a120+w114·a21+w115·a122+w116·a123+w21·a22+w22·a23+w23·a24+w24·a25+w25·a28+w26·a29+w27·a210+w28·a211+w29·a214+w210·a215+w211·a216+w212·a217+w213·a220+w214·a221+w215·a222+w216·a223+w31·a32+w32·a33+w33·a34+w34·a35+w35·a38+w36·a39+w37·a310+w38·a311+w39·a314+w310·a315+w311·a316+w312·a317+w313·a320+w314·a321+w315·a322+w316·a323+w41·a42+w42·a43+w43·a44+w44·a45+w45·a48+w46·a49+w47·a410+w48·a411+w49·a414+w410·a415+w411·a416+w412·a417+w413·a420+w414·a421+w415·a422+w416·a423+w51·a52+w52·a53+w53·a54+w54·a55+w55·a58+w56·a59+w57·a510+w58·a511+w59·a514+w510·a515+w511·a516+w512·a517+w513·a520+w514·a521+w515·a522+w516·a523+w6·a62+w62·a63+w63·a64+w64·a65+w65·a68+w66·a69+w67·a610+w68·a611+w69·a614+w610·a615+w611·a616+w612·a617+w613·a620+w614·a621+w615·a622+w616·a623+w71·a72+w72·a73+w73·a74+w74·a75+w75·a78+w76·a79+w77·a710+w78·a7110+w79·a714+w710·a715+w711·a716+w712·a717+w713·a720+w714·a721+w715·a722+w716·a723+w81·a82+w82·a83+w83·a84+w84·a85+w85·a88+w86·a89+w87·a810+w88·a811+w89·a814+w810·a815+w811·a816+w812·a817+w813·a820+w814·a8210+w815·a822+w816·a823.

Output element o13is the dot product of the first row of converted weight matrix212, i.e., converted weight tensor2121, and the third column of converted input data matrix214.

More particularly, output element o13is equal to w11·a13+w12·a14+w13·a15+w14·a16+w15·a19+w16·a110+w17·a111+w18·a112+w19·a115+w110·a116+w111·a117+w112·a118+w113·a121+w114·a122+w115·a123+w116·a124+w21·a23+w22·a24+w23·a25+w24·a26+w25·a29+w26·a210+w27·a211+w28·a212+w29·a215+w210·a216+w211·a217+w212·a218+w213·a221+w214·a222+w215·a223+w216·a224+w31·a33+w32·a34+w33·a35+w34·a36+w35·a39+w36·a310+w37·a311+w38·a312+w39·a315+w310·a316+w311·a317+w312·a318+w313·a321+w314·a322+w315·a323+w316·a324+w41·a43+w42·a44+w43·a45+w44·a46+w45·a49+w46·a410+w47·a411+w48·a412+w49·a415+w410·a416+w411·a417+w412·a418+w413·a421+w414·a422+w415·a423+w416·a424+w51·a53+w52·a54+w53·a55+w54·a56+w55·a59+w56·a510+w57·a511+w58·a512+w59·a515+w510·a516+w511·a517+w512·a518+w513·a521+w514·a522+w515·a523+w516·a524+w61·a63+w62·a64+w63·a65+w64·a66+w65·a69+w66·a610+w67·a611+w68·a612+w69·a615+w610·a616+w611·a617+w612·a618+w613·a621+w614·a622+w615·a623+w616·a624+w71·a73+w72·a74+w73·a75+w74·a76+w75·a79+w76·a710+w77·a711+w78·a712+w79·a715+w710·a716+w711·a717+w712·a718+w713·a721+w714·a722+w715·a723+w716·a724+w81·a83+w82·a84+w83·a85+w84·a86+w85·a89+w86·a810+w87·a811+w88·a812+w89·a815+w810·a816+w811·a817+w812·a818+w813·a821+w814·a822+w815·a823+w816·a824.

The calculation of the output elements in quadrant o2q1of converted output data matrix2162follows.

Output element o21is the dot product of the second row of converted weight matrix212, i.e., converted weight tensor2122, and the first column of converted input data matrix214.

Output element o22is the dot product of the second row of converted weight matrix212, i.e., converted weight tensor2122, and the second column of converted input data matrix214.

Output element o23is the dot product of the second row of converted weight matrix212, i.e., converted weight tensor2122, and the third column of converted input data matrix214.

The calculation of the output elements in quadrant o3q1of converted output data matrix2163follows.

Output element o31is the dot product of the third row of converted weight matrix212, i.e., converted weight tensor2123, and the first column of converted input data matrix214.

More particularly, output element o31is equal to y11·a11+y12·a12+y13·a13+y14+a14+y15·a17+y16·a18+y17·a19+y18·a110+y19·a113+y110·a114+y111·a115+y112·a116+y113·a119+y114·a120+y115·a121+y116·a122+a21+y22·a22+y23·a23+y24·a24+y25·a27+y26·a28+y27·a29+y28·a210+y29·a213+y210·a214+y211·a215+y212·a216+y213·a219+y214·a220+y215·a221+y216·a222+y31·a31+y32·a32+y33·a33+y34·a34+y35·a37+y36·a38+y37·a39+y38·a310+y39·a313+y310, a314+y311·a315+y312·a316+y313·a319+y314·a320+y315·a321+y316·a322+y41·a41+y42·a42+y43·a43+y44·a45+y45·a47+y46·a48+y47·a49+y48·a410+y49·a413+y410·a414+y411·a415+y412·a416+y413·a419+y414·a420+y415·a421+y416·a422+y51·a51+y52·a52+y53·a53+y54·a54+y55·a57+y56·a58+y57·a59+y58·a510+y59·a513+y510·a54+y511·a515+y512·a516+y513·a519+y514·a520+y515·a521+y516·a522+y61·a61+y62·a62+y63·a63+y64·a64+y65·a67+y66·a68+y67·a69+y68·a610+y69·a613+y610·a614+y611·a615+y612·a616+y613·a619+y614·a620+y615·a621+y616·a622+y71·a71+y72·a72+y73·a73+y74·a74+y75·a77+y76·a78+y77·a79+y78·a710+y79·a13+y710·a714+y711·a715+y712·a716+y713·a719+y714·a220+y715·a221+y716·a722+y81·a81+y82·a82+y83·a83+y84·a84+y85·a87+y86·a88+y87·a89+y88·a810+y89·a813+y810·a814+y811·a815+y812·a816+y813·a819+y814·a820+y815·a821+y816·a822.

Output element o32is the dot product of the third row of converted weight matrix212, i.e., converted weight tensor2123, and the second column of converted input data matrix214.

More particularly, output element o32is equal to y11·a12+y12·a13+y13·a14+y14·a15+y15·a18+y16·a19+y17·a110+y18·a111+y19·a114+y110·a115+y111·a116+y112·a117+y113·a120+y114·a121+y115·a122+y116·a123+a2·a22+y22·a23+y23·a24+y24·a25+y25·a28+y26·a29+y27·a210+y28·a211+y29·a214+y210·a215+y211·a216+y212·a217+y213·a220+y214·a221+y215·a222+y216·a223+y31·a32+y32·a33+y33·a34+y34·a35+y35·a38+y36·a39+y37·a310+y38·a311+y39·a314+y310·a315+y311·a316+y312·a317+y313·a320+y314·a321+y315·a322+y316·a323+y41·a42+y42·a43+y43·a44+y44·a45+y45·a48+y46·a49+y47·a410+y48·a411+y49·a414+y410·a415+y411·a416+y412·a417+y413·a420+y414·a421+y415·a422+y416·a423+y51·a52+y52·a53+y53·a54+y54·a55+y55·a58+y56·a59+y57·a510+y58·a511+y59·a514+y510·a515+y511·a516+y512·a517+y513·a520+y514·a521+y515·a522+y516·a523+y61·a62+y62·a63+y63·a64+y64·a65+y65·a68+y66·a69+y67·a610+y68·a611+y69·a614+y610·a615+y61·a616+y612·a617+y613·a620+y614·a621+y615·a622+y616·a623+y71·a72+y72·a73+y73·a74+y74·a75+y75·a78+y76·a79+y77·a710+y78·a7110+y79·a714+y710·a715+y711·a716+y712·a717+y713·a720+y714·a721+y715·a722+y716·a723+y81·a82+y82·a83+y83·a84+y84·a85+y85·a88+y86·a89+y87·a810+y88·a811+y89·a814+y810·a815+y811·a816+y812·a817+y813·a820+y814·a8210+y815·a822+y816·a823.

Output element o3is the dot product of the third row of converted weight matrix212, i.e., converted weight tensor2123, and the third column of converted input data matrix214.

More particularly, output element o33is equal to y11·a13+y12·a14+y13·a15+y14·a16+y15·a19+y16·a110+y17·a111+y18·a112+y19·a115+y110·a116+y111·a117+y112·a118+y113·a121+y114·a122+y115·a123+y116·a124+a2·a23+y22·a24+y23·a25+y24·a26+y25·a29+y26·a210+y27·a211+y28·a212+y29·a215+y210·a216+y211·a217+y212·a218+y213·a221+y214·a222+y215·a223+y216·a224+y31·a33+y32·a34+y33·a35+y34·a36+y35·a39+y36·a310+y37·a311+y38·a312+y39·a315+y310·a316+y311·a317+y312·a318+y313·a321+y314·a322+y315·a323+y316·a324+y41·a43+y42·a44+y43·a45+y45·a46+y45·a49+y46·a410+y47·a411+y48·a412+y49·a415+y410·a416+y411·a417+y412·a418+y413·a421+y414·a422+y415·a423+y416·a424+y51·a53+y52·a54+y53·a55+y54·a56+y55·a59+y56·a510+y57·a511+y58·a512+y59·a515+y510·a516+y511·a517+y512·a518+y513·a521+y514·a522+y515·a523+y516·a524+y61·a63+y62·a64+y63·a65+y64·a66+y65·a69+y66·a610+y67·a611+y68·a612+y69·a615+y610·a616+y61·a617+y612·a618+y613·a621+y614·a622+y615·a623+y616·a624+y71·a73+y72·a74+y73·a75+y74·a76+y75·a79+y76·a710+y77·a711+y78·a712+y79·a715+y710·a716+y711·a717+y712·a718+y713·a21+y714·a722+y715·a723+y716·a724+y81·a83+y82·a84+y83·a85+y84·a86+y85·a89+y86·a810+y87·a811+y88·a812+y89·a815+y810·a816+y811·a817+y812·a818+y813·a821+y814·a822+y815·a823+y816·a824.

The remaining output elements of converted output data matrix216are calculated in a similar manner.

For converted output data matrix2161, output element o14is the dot product of converted weight tensor2121and the fourth column of converted input data matrix214, output element o15is the dot product of converted weight tensor2121and the fifth column of converted input data matrix214, output element o16is the dot product of converted weight tensor2121and the sixth column of converted input data matrix214, output element o17is the dot product of converted weight tensor2121and the seventh column of converted input data matrix214, output element o18is the dot product of converted weight tensor2121and the eighth column of converted input data matrix214, and output element o19is the dot product of converted weight tensor2121and the ninth column of converted input data matrix214.

For converted output data matrix2162, output element o24is the dot product of converted weight tensor2122and the fourth column of converted input data matrix214, output element o25is the dot product of converted weight tensor2122and the fifth column of converted input data matrix214, output element o26is the dot product of converted weight tensor2122and the sixth column of converted input data matrix214, output element o27is the dot product of converted weight tensor2122and the seventh column of converted input data matrix214, output element o28is the dot product of converted weight tensor2122and the eighth column of converted input data matrix214, and output element o29is the dot product of converted weight tensor2122and the ninth column of converted input data matrix214.

For converted output data matrix2163, output element o34is the dot product of converted weight tensor2123and the fourth column of converted input data matrix214, output element o35is the dot product of converted weight tensor2123and the fifth column of converted input data matrix214, output element o36is the dot product of converted weight tensor2123and the sixth column of converted input data matrix214, output element o37is the dot product of converted weight tensor2123and the seventh column of converted input data matrix214, output element o38is the dot product of converted weight tensor2123and the eighth column of converted input data matrix214, and output element o39is the dot product of converted weight tensor2123and the ninth column of converted input data matrix214.

FIG.3depicts data flow diagram220for MAC array228, in accordance with an embodiment of the present disclosure.

As noted above, GEMM operations may be implemented in a dedicated ANN hardware accelerator using an array of MAC units. In this embodiment, MAC array228is a systolic, output stationary array that implements converted convolution operation210using a 3×3 array of MAC units m1, . . . , m9. The orientation of transposed converted weight matrix222, transposed converted input data matrix224, and transposed converted output data matrix226relative to MAC array228simplifies illustration; other orientations are also contemplated. As discussed above, each MAC unit calculates a dot product, between a row of converted weight matrix212and a column of converted input data matrix214, to generate an element of converted output data matrix216.

Generally, a MAC unit includes, inter alia, a multiplier, an adder and a storage register. Each MAC unit is reset by clearing or zeroing its storage register prior to, or at the start of, a new dot product calculation. Generally, the rows from converted weight matrix212are read from local memory, a register, etc., enter MAC array228at the first row of MAC units m1, m2and m3, and propagate one MAC unit down at the beginning of each processing cycle. Similarly, the columns from converted input data matrix214are read from local memory, a register, etc., enter MAC array228at the first column of MAC units m1, m4and m7, and propagate one MAC unit to the right at the beginning of each processing cycle. The dot product calculations performed by MAC unit m1for the blocks of the first quadrants a1q1, a2q1and a3q1of converted input data matrix214are discussed in detail below, while the dot product calculations performed by the remaining MAC units of MAC array228are summarized below.

MAC unit m1calculates the dot product of the first row of converted weight matrix212(i.e., converted weight tensor2121) and the first column of converted input data matrix214to generate element o11of converted output data matrix216. During the processing cycle1, MAC unit m1receives a11and w11from local memory, multiplies a11and w11to generate an intermediate product, adds the intermediate product to the value stored in the storage register (i.e., 0), and stores the accumulated result back in the storage register. During processing cycle2, MAC unit m1transmits a1to MAC unit m2and w11to MAC unit m4, receives a12and w12from local memory, multiplies a12and w12to generate an intermediate product, adds the intermediate product to the value stored in the storage register, and stores the accumulated result back in the storage register. During processing cycle3, MAC unit m1transmits a12to MAC unit m2and w12to MAC unit m4, receives a13and w13from local memory, multiplies a13and w13to generate an intermediate product, adds the intermediate product to the value stored in the storage register, and stores the accumulated result back in the storage register. During processing cycle4, MAC unit m1transmits a13to MAC unit m2and w13to MAC unit m4, receives a14and w14from the local memory, multiplies a14and w14to generate an intermediate product, adds the intermediate product to the value stored in the storage register, and stores the accumulated result back in the storage register.

Processing cycles5through128multiply and accumulate the remaining 124 elements of the first row of converted weight matrix212and the first column of converted input data matrix214. At the end of the processing cycle128, MAC unit m1outputs element o11. The remainder of the first row of MAC array228includes MAC units m2and m3.

After an initial delay of one processing cycle, MAC unit m2receives weights from the first delay register ff1and input data from MAC unit m1, transmits weights to MAC unit m5and input data to MAC unit m3, and calculates the dot product of the second row of converted weight matrix212(i.e., converted weight tensor2122) and the first column of converted input data matrix214to generate element o21of converted output data matrix216. The initial delay of one processing cycle allows the delay pipeline (i.e., delay register ff1) to be filled with weights transferred from memory, and the input data to become available from MAC unit m1. At the end of the processing cycle129, MAC unit m2outputs element o21.

After an initial delay of two processing cycles, MAC unit m3receives weights from the second delay register ff2and input data from MAC unit m2, transmits weights to MAC unit m6, and calculates the dot product of the third row of converted weight matrix212(i.e., converted weight tensor2123) and the first column of converted input data matrix214to generate element o31of converted output data matrix216. The initial delay of two processing cycles allows the delay pipeline (i.e., delay registers ff1and ff2) to be filled with weights transferred from memory, and the input data to become available from MAC unit m2. At the end of processing cycle130, MAC unit m3outputs element o31.

The second row of MAC array228includes MAC units m4, m5and m6. After an initial delay of one processing cycle, MAC unit m4receives weights from MAC unit m1and input data from a first delay register ff1, transmits weights to MAC unit m7and input data to MAC unit m5, and calculates the dot product of the first row of converted weight matrix212(i.e., converted weight tensor2121) and the second column of converted input data matrix214to generate element o12of converted output data matrix216. The initial delay of one processing cycle allows the delay pipeline (i.e., delay register ff1) to be filled with input data transferred from memory, and the weights to become available from MAC unit m1. At the end of processing cycle129, MAC unit m4outputs element o12.

After an initial delay of two processing cycles, MAC unit m5receives weights from MAC unit m2and input data from MAC unit m4, transmits weights to MAC unit ma and input data to MAC unit m6, and calculates the dot product of the second row of converted weight matrix212(i.e., converted weight tensor2122) and the second column of converted input data matrix214to generate element o22of converted output data matrix216. The initial delay of two processing cycles allows the weights to become available from MAC unit m2, and the input data to become available from MAC unit m4. At the end of processing cycle130, MAC unit m5outputs element o22.

After an initial delay of three processing cycles, MAC unit m6receives weights from MAC unit m3and input data from MAC unit m5, transmits weights to MAC unit m9, and calculates the dot product of the third row of converted weight matrix212(i.e., converted weight tensor2123) and the second column of converted input data matrix214to generate element o32of converted output data matrix216. The initial delay of three processing cycles allows the weights to become available from MAC unit m3, and the input data to become available from MAC unit m5. At the end of processing cycle131, MAC unit m6outputs element o32.

The third row of MAC array228includes MAC units m7, m8and m9.

After an initial delay of two processing cycles, MAC unit m7receives weights from MAC unit m4and input data from a second delay register ff2, transmits input data to MAC unit m8, and calculates the dot product of the first row of converted weight matrix212(i.e., converted weight tensor2121) and the third column of converted input data matrix214to generate element o13of converted output data matrix216. The initial delay of two processing cycles allows the delay pipeline (i.e., delay registers ff1and ff2) to be filled with input data transferred from memory, and the weights to become available from MAC unit m4. At the end of processing cycle130, MAC unit m7outputs element o13.

After an initial delay of three processing cycles, MAC unit ma receives weights from MAC unit m5and input data from MAC unit m7, transmits input data to MAC unit m8, and calculates the dot product of the second row of converted weight matrix212(i.e., converted weight tensor2122) and the third column of converted input data matrix214to generate element o23of converted output data matrix216. The initial delay of three processing cycles allows the weights to become available from MAC unit m5, and the input data to become available from MAC unit m7. At the end of processing cycle131, MAC unit ma outputs element o23.

After an initial delay of four processing cycles, MAC unit me receives weights from MAC unit m6and input data from MAC unit m8, and calculates the dot product of the third row of converted weight matrix212(i.e., converted weight tensor2123) and the third column of converted input data matrix214to generate element o33of converted output data matrix216. The initial delay of four processing cycles allows the weights to become available from MAC unit m6, and the input data to become available from MAC unit me. At the end of processing cycle132, MAC unit me outputs element o33.

After the blocks of the first quadrants a1q1, a2q1, and a3q1of converted input data matrix214have been processed, the next sequence of operations processes the blocks of the second quadrants a1q2, a2q2, and a3q2. After the blocks of the second quadrants a1q2, a2q2, and a3q2have been processed, the next sequence of operations processes the blocks of the third quadrants a1q3, a2q3, and a3q3. Converted weight matrix212is accessed for each sequence of operations.

Unfortunately, for CNNs executing on CPUs, GPUs, NPUs, etc., GEMM operations consume a significant number of processor cycles due to the large number of multiplications that are required. For example, one known image recognition CNN requires 3 giga operations per second (GOPS) per input data frame. Compounding this problem, many of the ANN matrices upon which GEMM operations are performed are sparse, which produces a very inefficient use of storage resources. More particularly, CNN weight tensors are stored in a dense or uncompressed form, even though the weights typically contain a significant amount of zero values.

Embodiments of the present disclosure advantageously provide a matrix encoding process that reduces storage requirements and provides flexibility in both quantization and pruning within a fixed block size format. More particularly, embodiments of the present disclosure advantageously provide a block-based encoding process for ANN matrices, such as weight tensors, that is of fixed storage size, but allows trade-off in the matrix elements between zero values, smaller magnitude values and larger magnitude values. Many embodiments of the present disclosure also provide a fixed computation size per block, which is advantageous in many situations

FIGS.4A,4B and4Cdepict weight tensors2021,2022and2023respectively, in accordance with an embodiment of the present disclosure.

As discussed above, each weight tensor202iincludes one 4×4 weight matrix for each input channel, i.e., weight matrices202i1,202i2,202i3,202i4,202i5,202i6,202i7and202i8, so weight tensor2021includes weight matrices20211,20212,20213,20214,20215,20216,20217and20218, weight tensor2022includes weight matrices20221,20222,20223,20224,20225,20226,20227and20228, and weight tensor2023includes weight matrices20231,20232,20233,20234,20235,20236,20237and20238.

FIGS.5A,5B and5Cdepict basic block sets3021,3022and3023, respectively, in accordance with an embodiment of the present disclosure.

In one embodiments, each weight tensor202′ may be decomposed into a basic block set302ithat includes 16 basic blocks302ijalong the depth or channel dimension. Each basic block is a 1×1×b tensor, and includes b weight values. The depth, b, is a hyperparameter having a value of 4, 8, 16, etc. In this embodiment, b equals 8, i.e., the number of channels.

More particularly, basic block set3021includes basic blocks30211,30212,30213,30214,30215,30216,30217,30218,30219,302110,302111,302112,302113,302114,302115and302116, basic block set3022includes basic blocks30221,30222,30223,30224,30225,30226,30227,30228,30229,302210,302211,302212,302213,302214,302215and302216, and basic block set3023includes basic blocks30231,30232,3023,30234,30235,30236,30237,30238,30239,302310,302311,302312,302313,302314,302315and302316.

FIGS.6A,6B and6Cdepict basic block matrix sets3121,3122and3123respectively, in accordance with an embodiment of the present disclosure.

Basic block set302imay be reformed into a basic block matrix set312ithat includes 16 respective basic block matrices312i1, i.e., basic block matrices312i1,312i2,312i3,312i4,312's,312i6,312i7,312i8,312i9,312i10,312i11,312i12,312i13,312i14,312i15and312i16. Each basic block matrix312ijhas 8 rows and a single column (8×1), and the same weights as the respective basic block3041j.

More particularly, basic block matrix set3121includes basic block matrices31211,31212,31213,31214,31215,31216,31217,31218,31219,312111,312111,312112,312113,312114,312115and312116, basic block matrix set3122includes basic block matrices31221,31222,31223,31224,31225,31226,31227,31228,31229,312211,312211,312212,312213,312214,312215and312216, and basic block matrix set3123includes basic block matrices31231,31232,31233,31234,31235,31236,31237,31238,31239,312311,312311,312312,312313,312314,312315and312316.

Because weight tensors2021,2022and2023have been reformed into basic block matrix sets3121,3122and3123across the channel dimension rather than the height and width dimensions, encoding the weights of each basic block matrix advantageously avoids adverse effects on the local data within any particular weight matrix.

FIG.7Adepicts matrix element encoding process350, according to an embodiment of the present disclosure.

In this embodiment, the matrix element is an 8-bit unsigned integer weight322. The principles discussed below are applicable to other types of matrix elements, such as, for example, 8-bit unsigned integer activations, an 8-bit signed integer weights or activations, a 16-bit signed or unsigned integer weights or activations, a 32-bit signed or unsigned integer weights or activations, certain floating point formats, etc.

In this embodiment, the encoding process for the 8-bit unsigned integer matrix element advantageously includes both quantization, to reduce the number of bits, and pruning to remove small values at or close to zero. Weight322may be encoded as a 4-bit “zero magnitude” unsigned integer value, i.e., encoded weight3221, a 4-bit “small magnitude” unsigned integer value, i.e., encoded weight3222, a 4-bit “large magnitude” unsigned integer value, i.e., encoded weight3223, or an 8-bit “full magnitude” unsigned integer value, i.e., encoded weight3224. In another embodiment, the encoding process for the 8-bit signed integer matrix element uses 4-bit “zero magnitude”, “small magnitude” and “large magnitude” signed integer values and an 8-bit “full magnitude” signed integer value.

The 4-bit “large magnitude” unsigned integer value is similar to an 8-bit unsigned integer value with a zero-valued least significant bit (LSB) nibble, while the 4-bit “small magnitude” unsigned integer value is similar to an 8-bit unsigned integer value with a zero-valued most significant bit (MSB) nibble. The 4-bit “large magnitude” unsigned integer value is created by shifting the matrix element 4 bits to the right, and the matrix element is reconstructed by shifting the 4-bit “large magnitude” unsigned integer value 4 bits to the left. The information contained in the lower 4 bits (i.e., the LSB nibble) of the matrix element is lost during the encoding and recreation processes.

Additional encoding types are also contemplated, such as, for example, an 8-bit “medium magnitude” integer for a16-bit integer matrix element, an 8-bit “small magnitude” integer for a32-bit integer matrix element, etc.

Each type of encoding has an associated 2-bit index324, represented as “i:1, i:0”, that identifies or describes the encoding type. Weight3221has an associated 2-bit index3241to identify the “zero magnitude” type, and has a bit pattern of “00”. Weight3222has an associated 2-bit index3242to identify the “small magnitude” type, and has a bit pattern of “10”. Weight3223has an associated 2-bit index3243to identify the “large magnitude” type, and has a bit pattern of “11”. Weight3224has an associated 2-bit index3244to identify the “full magnitude” type, and has a bit pattern of “01”.

Other index values and numbers of bits may also be used, such as, for example, a 3-bit index with one value (e.g., “100”) indicating an 8-bit “medium magnitude” integer for a 16-bit integer matrix element, a 3-bit index with one value (e.g., “110”) indicating an 8-bit “small magnitude” integer for a 32-bit integer matrix element, etc.

Weight322includes eight bits represented as w:0, w:1, w:2, w:3, w:4, w:5, w:6, w:7 (LSB to MSB). Generally, weight322has a value between 0 to 255 (decimal). When the value of weight322is zero or less than a lower threshold value, such as, for example, 1, 2, etc., then weight322may be encoded as a 0-bit “zero magnitude” value, i.e., weight3221, with an associated 2-bit index3241(i.e., “00”). When the value of weight322is greater than the lower threshold value but less than or equal to an upper threshold value, such as, for example, 15, then weight322may be encoded as a “small magnitude” unsigned integer value, i.e., weight3222, with an associated 2-bit index3242(i.e., “10”). When the value of weight322is greater than the upper threshold value, then weight322may be encoded as a “large magnitude” unsigned integer value, i.e., weight3223, with an associated 2-bit index3243(i.e., “11”). In one embodiment, when the value of weight322is greater than the upper threshold value and the LSB nibble is desired to be retained (for accuracy, etc.), then weight322may be encoded as a “full magnitude” unsigned integer value, i.e., weight3223, with an associated 2-bit index3243(i.e., “01”).

In another embodiment, the matrix element encoding process may be hierarchical, which advantageously reduces the index overhead when the data has high sparsity, i.e., when most of the matrix elements are zero. In this embodiment, each matrix element has an associated index with one or two bits. The first bit indicates whether the matrix element has a zero value or a non-zero value. If the matrix element has a non-zero value, then the second bit indicates whether the matrix element has been encoded as a “small magnitude” value or a “large magnitude” value.

FIG.7Bdepicts basic block encoding process360, according to an embodiment of the present disclosure.

Generally, each basic block matrix312ijis encoded into a fixed-size encoded block340ijthat includes a fixed-size data field332ijand a fixed-size index field334ij. The size of data field332ijis based on the amount of compression desired and the sparsity of the data within basic block matrices312ij, while the size of index field334ijdepends upon the number of elements within each basic block matrix312ij.

In one embodiment, the sparsity of the data is low and each basic block matrix312ijincludes eight, 8-bit elements with a total size of 64 bits (8B). The size of index field334ijwill be 16 bits (2B), and the size of data field332ijdepends on the amount of compression desired. For example, if a data compression ratio of about 0.5 is desired, then the size of data field332ijmay be set to 32 bits (4B), which accommodates a number of different encoding combinations, such as four “full magnitude” elements and four “zero magnitude” elements (4·8 bits or 4B), eight “small magnitude” elements (8·4 bits or 4B), eight “large magnitude” elements (8.4 bits or 4B), four “small magnitude” element and four “large magnitude” elements (4·4+4·4 bits or 4B), two “full magnitude” elements, four “small magnitude” elements and two “zero magnitude” elements (2·8+4·4 bits or 4B), etc. In this example, the overall compression ratio is 0.75 due to the overhead incurred by index field334ij(i.e., 4B+2B/8B).

In another embodiment, the sparsity of the data is 50%, and each basic block matrix312ijincludes eight, 8-bit elements with a total size of 64 bits (8B). The size of index field334ijwill be 16 bits (2B), and the size of data field332ijdepends on the amount of compression. In this embodiment, four elements have zero values and four elements have non-zero values. If a data compression ratio of about 0.5 is desired, then the size of data field332ijmay be set to 32 bits (4B), which accommodates four “full magnitude” elements, as described above, without any loss of accuracy. However, the overall compression ratio is still 0.75 due to the overhead incurred by index field334ij(i.e., 4B+2B/8B).

Advantageously, if an overall compression ratio of 0.5 is desired, then the size of data field332ijmay be set to 16 bits (2B) and each non-zero element may be encoded as a “small magnitude” element or a “large magnitude” element. The overall compression ratio is now 0.5 (i.e., 2B+2B/8B) or 2:1.

In other embodiments, the size of data field332ijmay be set to 16 bits (2B) and the four “highest-valued” non-zero elements may be encoded as “small magnitude” or “large magnitude” elements, while the remaining elements are encoded as “zero magnitude” elements. In embodiments with very sparse data, less than four elements may have non-zero values, in which case one or more elements may be encoded as a “small magnitude” element with a zero value and the proper index (i.e., index3242) to ensure that four elements are encoded as “small magnitude” or “large magnitude” elements. While this accommodation introduces multiply-by-zero situations during processing, the advantages associated with reducing the memory footprint outweigh the disadvantages of the occasionally multiply-by-zero situation.

As illustrated in basic block encoding process360, basic block matrix31211may be encoded into a fixed-size encoded block34011that includes a fixed-size data field33211(2B) and a fixed-size index field33411(2B). Each weight is encoded as a “zero magnitude” element (i.e., weight3221), a “small magnitude” element (i.e., weight3222), or a “large magnitude” element (i.e., weight3223), and the associated index3241,3242, or3243is generated. Importantly, while all of the associated indices are added to index field334ij, only those weights that are encoded as “small magnitude” or “large magnitude” elements are added to data field332ij. In other words, “zero magnitude” elements are not present within data field332ijunless the data is very sparse, as discussed above.

More particularly, weight w11is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:0, i:1. Weight w21is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:2, i:3. Weight w31is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:4, i:5. Weight w41is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:6, i:7. Weight w51is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:8, i:9. Weight w61is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:10, i:11. Weight w71is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:12, i:13. Weight w81is encoded into weight3221, weight3222or weight3223and added to data field33211as appropriate, and the associated index is added to index33411at bits i:14, i:15.

The result of basic block encoding process360is a transformation of a basic block matrix312into an encoded block set340, such as, for example, basic block matrix3121into encoded block set3401.

FIGS.8A,8B,8C and8Ddepict basic block encoding process360for basic block matrix set3121, according to an embodiment of the present invention.

In this embodiment, basic block matrix set3121has a sparsity of 50%, which is randomly distributed throughout basic block matrices3121j.

In this embodiment, each 64-bit (8B) basic block matrix3121jis encoded into a16bit (2B) data field3321j, and each non-zero element is encoded as a 4-bit “small magnitude” element (i.e., weight3222) or a 4-bit “large magnitude” element (i.e., weight3223). The overall compression ratio for this embodiment is 0.5 (i.e., 2B+2B/8B) or 2:1.

As depicted inFIG.8C, the non-zero encoded weights of each basic block matrix3121jhave been formed into respective data fields3321j, and the associated index fields3341jhave been created. Each index field3341jincludes eight, 2-bit index values associated with the eight weights of the respective basic block matrix3121j, i.e., i1, i2, i3, i4, i5, i6, i7and i8. Index i1is located in the LSB position, while index i8is located in the MSB position.

Data field33219includes weights w39, w49, w79and w89with non-zero values (weights w19, w29, w59and w69have zero values). Weight w39has an associated index i3of “10” within index field33419, weight w49has an associated index i4of “10” within index field33419, weight w79has an associated index i7of “11” within index field33419, and weight w89has an associated index is of “11” within index field33419. Weights w19, w29, w59and w69have associated indices i1, i2, i and i6(respectively) of “00” within index field33419. The hexadecimal value for index field33419is 0xF0A0.

FIG.8Ddepicts encoded block set3401, which includes encoded blocks34011,34012,34013,34014,34015,34016,34017,34018,34019,340110,340111,340112,340113,340114,340115and340116. Each encoded block3401jincludes data field djand index field ij.

More particularly, encoded block34011includes data field d1(i.e., data field33211) and index field i1(i.e., index field33411), and encoded block34012includes data field d2(i.e., data field33212) and index field i2(i.e., index field33412), encoded block34013includes data field d3(i.e., data field33213) and index field i3(i.e., index field33413), encoded block34014includes data field d4(i.e., data field33214) and index field i4(i.e., index field33414), encoded block34015includes data field d5(i.e., data field33215) and index field i5(i.e., index field3341), encoded block34016includes data field d6(i.e., data field33216) and index field i6(i.e., index field33416), encoded block34017includes data field d7(i.e., data field33217) and index field i7(i.e., index field33417), encoded block34018includes data field d8(i.e., data field33218) and index field is (i.e., index field33418), encoded block34019includes data field d9(i.e., data field33219) and index field i9(i.e., index field33419), encoded block340110includes data field d10(i.e., data field332110) and index field i10(i.e., index field334110), encoded block340111includes data field d11(i.e., data field332111) and index field i11(i.e., index field334111), encoded block340112includes data field d12(i.e., data field332112) and index field i12(i.e., index field334112), encoded block340113includes data field d13(i.e., data field332113) and index field i13(i.e., index field334113), encoded block340114includes data field d14(i.e., data field332114) and index field i14(i.e., index field334114), encoded block340115includes data field d15(i.e., data field332115) and index field i15(i.e., index field334115), encoded block340116includes data field d16(i.e., data field332116) and index field i16(i.e., index field334116).

Basic block matrix sets3122and3123are processed in the same manner.

FIG.9depicts a data flow diagram380for a portion of a training process for CNN15, according to an embodiment of the present disclosure.

In order to encode weight tensors2021,2022and2023of filter202for inference, CNN15is first trained using basic block creation process355, basic block encoding process360and encoded block conversion process365in the forward path of the convolutional layer calculations. For example, data flow diagram380depicts a portion of the training process for CNN15that includes converted convolutional layer calculation210.

During training, basic block creation process355, basic block encoding process360and encoded block conversion process365may be implemented by the processor that is hosting the training process for CNN15, such as, for example, a central processing unit (CPU), graphics processing unit (GPU), neural processing unit (NPU), etc.

During this portion of the forward phase, input data tensor204is provided to converted convolutional layer calculation210. Generally, filter202, including weight tensors202i, is provided to basic block creation process355, which decomposes each weight tensor202iinto a basic block set302iand then reforms each basic block set302iinto a basic block matrix set312i, as described above. Each basic block matrix set312iis then provided to basic block encoding process360, which encodes each basic block matrix set312iinto an encoded block set340ithat includes encoded blocks340ij, as described above. Each encoded block set340iis then provided to encoded block conversion process365which converts the encoded block set340iinto a reconstructed weight tensor202iby simply performing the steps described above in reverse order.

The reconstructed weight tensors202iare then provided to converted convolutional layer calculation210, which convolves the reconstructed weight tensors202iand the input data tensor204to generate output data tensor206, which is provided to the next layer of CNN15. Each reconstructed weight tensor202imay include weights with different values than the weights of the respective weight tensor202idue to potential losses introduced by basic block encoding process360.

During the backward phase, the gradients are backpropagated and weight tensors202iwithin filter202are updated.FIG.9depicts the embodiment described in detail above, in which “i” is equal to 3.

During inference, input data tensor204and each encoded block set340iare read from memory and provided to an MMA, which performs encoded block conversion process365to convert each encoded block set340iinto a reconstructed weight tensor202i, and then executes the converted convolutional layer calculation210. For certain layers of CNN15, the output data tensor206may be further processed by the MMA and then provided as the input data tensor204to the next convolution layer. Each encoded block set340ifor the next convolution layer is read from memory, the MMA performs encoded block conversion process365to convert each encoded block set340iinto a reconstructed weight tensor202i, and then executes the converted convolutional layer calculation210for this layer.

In many embodiments, the weight tensors are sufficiently sparse, or many elements have sufficiently small magnitude values, such that transforming each basic block set into an encoded block set is essentially lossless. The encoding described above is very well suited to ANN weights, because ANN weights often have very sparse data but with an occasional large weight, which is important.

In other embodiments, transforming each basic block set to an encoded block set is lossy, and, to minimize the loss, a simple search or optimization technique may be employed during training to optimally assign the type to each element, such as, for example, a neural architecture search (NAS), a differential NAS (DNAS), Bayesian optimization, etc. In these embodiments, a small extra “fine tuning” training phase after a lossy encoding (typically quantization) may be used to recover any loss in accuracy due to the error introduced.

FIG.10depicts a block diagram of system100, in accordance with an embodiment of the present disclosure.

Computer102includes bus110coupled to one or more processors120, memory130, I/O interfaces140, display interface150, one or more communication interfaces160and one or more MMAs400. Generally, I/O interfaces140are coupled to I/O devices142using a wired or wireless connection, display interface150is coupled to display152, and communication interface160is connected to network162using a wired or wireless connection.

Bus110is a communication system that transfers data between processor120, memory130, I/O interfaces140, display interface150, communication interface160, MMA400, as well as other components not depicted inFIG.1. Power connector112is coupled to bus110and a power supply (not shown).

Processor120includes one or more general-purpose or application-specific microprocessors that executes instructions to perform control, computation, input/output, etc. functions for computer102. Processor120may include a single integrated circuit, such as a micro-processing device, or multiple integrated circuit devices and/or circuit boards working in cooperation to accomplish the functions of processor120. In addition, processor120may execute computer programs or modules, such as operating system132, software modules134, etc., stored within memory130. For example, software modules134may include an ML application, an ANN application, a CNN application, etc.

Generally, storage element or memory130stores instructions for execution by processor120and data. Memory130may include a variety of non-transitory computer-readable medium that may be accessed by processor120. In various embodiments, memory130may include volatile and nonvolatile medium, non-removable medium and/or removable medium. For example, memory130may include any combination of random access memory (RAM), dynamic RAM (DRAM), static RAM (SRAM), read only memory (ROM), flash memory, cache memory, and/or any other type of non-transitory computer-readable medium.

Memory130contains various components for retrieving, presenting, modifying, and storing data. For example, memory130stores software modules that provide functionality when executed by processor120. The software modules include operating system132that provides operating system functionality for computer102. Software modules134provide various functionality, such as image classification using convolutional neural networks, etc. Data136may include data associated with operating system132, software modules134, etc.

I/O interfaces140are configured to transmit and/or receive data from I/O devices142. I/O interfaces140enable connectivity between processor120and I/O devices142by encoding data to be sent from processor120to I/O devices142, and decoding data received from I/O devices142for processor120. Generally, data may be sent over wired and/or wireless connections. For example, I/O interfaces140may include one or more wired communications interfaces, such as USB, Ethernet, etc., and/or one or more wireless communications interfaces, coupled to one or more antennas, such as WiFi, Bluetooth, cellular, etc.

Generally, I/O devices142provide input to computer102and/or output from computer102. As discussed above, I/O devices142are operably connected to computer102using a wired and/or wireless connection. I/O devices142may include a local processor coupled to a communication interface that is configured to communicate with computer102using the wired and/or wireless connection. For example, I/O devices142may include a keyboard, mouse, touch pad, joystick, etc.

Display interface150is configured to transmit image data from computer102to monitor or display152.

Communication interface160is configured to transmit data to and from network162using one or more wired and/or wireless connections. Network162may include one or more local area networks, wide area networks, the Internet, etc., which may execute various network protocols, such as, for example, wired and/or wireless Ethernet, Bluetooth, etc. Network162may also include various combinations of wired and/or wireless physical layers, such as, for example, copper wire or coaxial cable networks, fiber optic networks, Bluetooth wireless networks, WiFi wireless networks, CDMA, FDMA and TDMA cellular wireless networks, etc.

MMA400is configured to multiply matrices and generate output matrices to support various applications implemented by software modules134.

FIG.11depicts a block diagram of MMA400, in accordance with embodiments of the present disclosure.

Memory415may include volatile and/or nonvolatile memory. For example, memory415may include any combination of random access memory (RAM), dynamic RAM (DRAM), static RAM (SRAM), read only memory (ROM), flash memory, cache memory, and/or any other type of non-transitory computer-readable medium.

Generally, input data tensors and encoded block sets are received from memory130, over bus110via I/O interface405, and stored in memory415, while output data tensors stored in memory415and then transmitted, over bus110via I/O interface405, to memory130.

Controller410may be a processor, microprocessor, microcontroller, field programmable gate array (FPGA), etc., that controls the data flow and operation of MMA400. For example, in response to commands received from one or more software modules134executing on processor120, controller410performs load/store (L/S) instructions, memory mapped I/O (MMIO) operations, direct memory access (DMA) operations, etc., to convert each encoded block set into a reconstructed weight tensor, and then convolve each reconstructed weight tensor and an input data tensor to generate an output data matrix, in cooperation with memory415, registers420,430,440and PE array450.

More particularly, controller410converts each encoded block set into a reconstructed weight tensor by generating the basic block matrix set based on the encoded block set, and then generating the reconstructed weight tensor based on the basic block matrix set. Controller410then convolves each reconstructed weight tensor and the input data tensor to generate the output data matrix by converting the reconstructed weight tensor to a converted weight matrix based on a convolution operation, converting the input data tensor to a converted input data matrix based on the convolution operation, and then multiplying the converted weight matrix and the converted input data matrix to generate the output data matrix.

Register420provides activation elements to the PEs452in the first column of PE array450, while register430provides weight elements to the first row of PEs452of PE array450. Registers420and430may be n elements wide and m elements deep, each element being the same size as the data contained within converted output data matrix216, such as, for example, 8 bit integer data, 16 bit integer data, 32 bit integer data, 16 bit floating point data, 16 bit Bfloat data, 32 bit floating point data, etc. In one embodiment, registers420and430are 3 elements wide and 128 elements deep, with each element storing 8-bit integer data, and each PE452includes an 8-bit MAC unit to comport with the embodiments discussed above.

For example, PE1452is located in the first row and the first column of PE array450, and calculates the dot products of the 1strow of converted weight matrix212(i.e., W1) and the 1st, 4thand 7thcolumns of converted input data matrix214(i.e., A1) to generate the o11, o14, and o17elements of converted output data matrix2161, as discussed above with respect to MAC unit m1.

PE2452is located in the first row and the second column of PE array450, and calculates the dot products of the 2ndrow of converted weight matrix212(i.e., W2) and the 1st, 4thand 7thcolumns of converted input data matrix214(i.e., A1) to generate the o21, o24, and o27elements of converted output data matrix2162, as discussed above with respect to MAC unit m2.

PE3452is located in the first row and the third column of PE array450, and calculates the dot products of the 3rdrow of converted weight matrix212(i.e., W3) and the 1st, 4thand 7thcolumns of converted input data matrix214(i.e., A1) to generate the o31, o34, and o37elements of converted output data matrix2163, as discussed above with respect to MAC unit m3.

PE4452is located in the second row and the first column of PE array450, and calculates the dot products of the 1strow of converted weight matrix212(i.e., W1) and the 2nd, 5thand 8thcolumns of converted input data matrix214(i.e., A2) to generate the o12, o15, and o18elements of converted output data matrix2161, as discussed above with respect to MAC unit m4.

PE5452is located in the second row and the second column of PE array450, and calculates the dot products of the 2ndrow of converted weight matrix212(i.e., W2) and the 2nd, 5thand 8thcolumns of converted input data matrix214(i.e., A2) to generate the o22, o25, and o28elements of converted output data matrix2162, as discussed above with respect to MAC unit m5.

PE6452is located in the second row and the third column of PE array450, and calculates the dot products of the 3rdrow of converted weight matrix212(i.e., W3) and the 2nd, 5thand 8thcolumns of converted input data matrix214(i.e., A2) to generate the o32, o35, and o38elements of converted output data matrix2163, as discussed above with respect to MAC unit m6.

PE7452is located in the third row and the first column of PE array450, and calculates the dot products of the 1strow of converted weight matrix212(i.e., W1) and the 3rd, 6thand 9thcolumns of converted input data matrix214(i.e., A3) to generate the o13, o16, and o19elements of converted output data matrix2161, as discussed above with respect to MAC unit m7.

PE8452is located in the third row and the second column of PE array450, and calculates the dot products of the 2ndrow of converted weight matrix212(i.e., W2) and the 3rd, 6thand 9thcolumns of converted input data matrix214(i.e., A3) to generate the o23, o26, and o29elements of converted output data matrix2162, as discussed above with respect to MAC unit me.

PE9452is located in the third row and the third column of PE array450, and calculates the dot products of the 3rdrow of converted weight matrix212(i.e., W3) and the 3rd, 6thand 9thcolumns of converted input data matrix214(i.e., A3) to generate the o3, o36, and o39elements of converted output data matrix2163, as discussed above with respect to MAC unit m7.

Generally, basic block encoding process360results in a fixed encoded block size and a fixed number of MAC operations per block, especially when the datapath is implemented with some flexibility. Advantageously, a datapath based on 8-bit MAC units can be split into two 4-bit MAC processing paths per 8-bit MAC unit to leverage a 4-bit encoding scheme.

The embodiments described herein are combinable.

In one embodiment, a system includes a memory, a processor coupled to the memory and a matrix multiply accelerator (MMA) coupled to the processor and the memory. The memory is configured to store one or more weight tensors, each weight tensor including a number of weights. The processor is configured, for each weight tensor, to generate, based on the weight tensor, a basic block matrix set including a number of basic block matrices, each basic block matrix including a number of weights; to generate, based on the basic block matrix set, an encoded block set, the encoded block set including a number of encoded blocks, each encoded block including a data field and an index field, the data field including a number of encoded weights, the index field including an index associated with each weight in the basic block matrix, the number of encoded weights being less than the number of weights in the basic block matrix, each encoded block having a same size; and to store the encoded block set in the memory. The MMA is configured to convert each encoded block set into a reconstructed weight tensor having a number of weights equal to the number of weights of the respective weight tensor, and convolve each reconstructed weight tensor and an input data tensor to generate an output data matrix.

In another embodiment of the system, each weight tensor has a height, a width and a depth equal to a number of input channels; each basic block matrix has a width of 1 and a height equal to the number of input channels; and each basic block matrix includes one weight from each input channel.

In another embodiment of the system, the index indicates an encoding type of the associated weight, the encoding type including a zero magnitude type, a small magnitude type and a large magnitude type.

In another embodiment of the system, each weight tensor includes n-bit integer elements; the zero magnitude type is an n/2-bit integer element; the small magnitude type is an n/2-bit integer element; and the large magnitude type is an n/2-bit integer element.

In another embodiment of the system, the encoding type includes a full magnitude weight type that is an n-bit integer element.

In another embodiment of the system, generate the encoded block set includes, for each weight in the basic block matrix, determine an encoding type for the weight; generate an index for the weight based on the encoding type; generate an encoded weight based on the encoding type and the weight; add the index to the index field of the encoded block; and, when the encoding type is not a zero magnitude weight type, add the encoded weight to the data field of the encoded block

In another embodiment of the system, determine an encoding type for the weight is based on a lower threshold value and an upper threshold value.

In another embodiment of the system, determine an encoding type for the weight includes select the zero magnitude weight type when the weight has a zero value or the weight has a non-zero value that is less than or equal to the lower threshold value; select the small magnitude weight type when the weight has a non-zero value that is greater than the lower threshold value and less than or equal to the upper threshold value; and select the large magnitude weight type when the weight has a non-zero value that is greater than the upper threshold value.

In another embodiment of the system, each weight in the reconstructed weight tensor has a corresponding weight in the respective weight tensor that has a same value; convert each encoded block set into a reconstructed weight tensor includes generate, based on the encoded block set, the basic block matrix set, and generate, based on the basic block matrix set, the reconstructed weight tensor; convolve each reconstructed weight tensor and an input data tensor includes convert the reconstructed weight tensor, based on a convolution operation, to a converted weight matrix, convert the input data tensor, based on the convolution operation, to a converted input data matrix, and multiply the converted weight matrix and the converted input data matrix to generate the output data matrix.

In another embodiment of the system, the MMA includes a memory; a controller configured to convert the reconstructed weight tensor to the converted weight matrix, and convert the input data tensor to the converted input data matrix; a first register configured to store at least a portion of the converted input data matrix; a second register configured to store at least a portion of the converted weight matrix; a third register configured to store at least a portion of the output data matrix; and an array of processing elements (PEs), coupled to the controller and the first, second and third registers, configured to multiply the converted weight matrix and the converted input data matrix, each PE including a multiply-and-accumulate (MAC) circuit configured to generate a dot product between one row of the converted weight matrix and one column of the converted input data matrix.

In one embodiment, a computer-based method includes, at a processor coupled to a memory storing one or more weight tensors, for each weight tensor, generating, based on the weight tensor, a basic block matrix set including a number of basic block matrices, each basic block matrix including a number of weights; generating, based on the basic block matrix set, an encoded block set, the encoded block set including a number of encoded blocks, each encoded block including a data field and an index field, the data field including a number of encoded weights, the index field including an index associated with each weight in the basic block matrix, the number of encoded weights being less than the number of weights in the basic block matrix, each encoded block having a same size; and storing the encoded block set in the memory. The method also includes, at a matrix multiply accelerator (MMA) coupled to the processor and the memory, converting each encoded block set into a reconstructed weight tensor having a number of weights equal to the number of weights of the respective weight tensor; and convolving each reconstructed weight tensor and an input data tensor to generate an output data matrix.

In another embodiment of the method, each weight tensor has a height, a width and a depth equal to a number of input channels; each basic block matrix has a width of 1 and a height equal to the number of input channels; and each basic block matrix includes one weight from each input channel.

In another embodiment of the method, the index indicates an encoding type of the associated weight, the encoding type including a zero magnitude type, a small magnitude type and a large magnitude type.

In another embodiment of the method, each weight tensor includes n-bit integer elements; the zero magnitude type is an n/2-bit integer element; the small magnitude type is an n/2-bit integer element; and the large magnitude type is an n/2-bit integer element.

In another embodiment of the method, the encoding type includes a full magnitude weight type that is an n-bit integer element.

In another embodiment of the method, generating the encoded block set includes, for each weight in the basic block matrix, determining an encoding type for the weight; generating an index for the weight based on the encoding type; generating an encoded weight based on the encoding type and the weight; adding the index to the index field of the encoded block; and when the encoding type is not a zero magnitude weight type, adding the encoded weight to the data field of the encoded block.

In another embodiment of the method, determining an encoding type for the weight is based on a lower threshold value and an upper threshold value.

In another embodiment of the method, determining an encoding type for the weight includes selecting the zero magnitude weight type when the weight has a zero value or the weight has a non-zero value that is less than or equal to the lower threshold value; selecting the small magnitude weight type when the weight has a non-zero value that is greater than the lower threshold value and less than or equal to the upper threshold value; and selecting the large magnitude weight type when the weight has a non-zero value that is greater than the upper threshold value.

In another embodiment of the method, each weight in the reconstructed weight tensor has a corresponding weight in the respective weight tensor that has a same value.

In another embodiment of the method, converting each encoded block set into a reconstructed weight tensor includes generating, based on the encoded block set, the basic block matrix set, and generating, based on the basic block matrix set, the reconstructed weight tensor; convolving each reconstructed weight tensor and the input data tensor includes converting the reconstructed weight tensor, based on a convolution operation, to a converted weight matrix, converting the input data tensor, based on the convolution operation, to a converted input data matrix, and multiplying the converted weight matrix and the converted input data matrix to generate the output data matrix.

While implementations of the disclosure are susceptible to embodiment in many different forms, there is shown in the drawings and will herein be described in detail specific embodiments, with the understanding that the present disclosure is to be considered as an example of the principles of the disclosure and not intended to limit the disclosure to the specific embodiments shown and described. In the description above, like reference numerals may be used to describe the same, similar or corresponding parts in the several views of the drawings.

The term “or” as used herein is to be interpreted as an inclusive or meaning any one or any combination. Therefore, “A, B or C” means “any of the following: A; B; C; A and B; A and C; B and C; A, B and C.” An exception to this definition will occur only when a combination of elements, functions, steps or acts are in some way inherently mutually exclusive. Also, grammatical conjunctions are intended to express any and all disjunctive and conjunctive combinations of conjoined clauses, sentences, words, and the like, unless otherwise stated or clear from the context. Thus, the term “or” should generally be understood to mean “and/or” and so forth. References to items in the singular should be understood to include items in the plural, and vice versa, unless explicitly stated otherwise or clear from the text.

In the following description, it is understood that terms such as “first,” “second,” “top,” “bottom,” “up,” “down,” “above,” “below,” and the like, are words of convenience and are not to be construed as limiting terms. Also, the terms apparatus, device, system, etc. may be used interchangeably in this text.