Matrix multiplication system and method

The present disclosure advantageously provides a system method for efficiently multiplying matrices with elements that have a value of 0. A bitmap is generated for each matrix. Each bitmap includes a bit position for each matrix element. The value of each bit is set to 0 when the value of the corresponding matrix element is 0, and to 1 when the value of the corresponding matrix element is not 0. Each matrix is compressed into a compressed matrix, which will have fewer elements with a value of 0 than the original matrix. Each bitmap is then adjusted based on the corresponding compressed matrix. The compressed matrices are then multiplied to generate an output matrix. For each element i,j in the output matrix, a dot product of the ith row of the first compressed matrix and the jth column of the second compressed matrix is calculated based on the bitmaps.

BACKGROUND

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

Matrix multiplication is a fundamental component for many important applications, including machine learning (ML), artificial neural networks (ANNs), convolutional neural networks (CNNs), etc. 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.

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.

Embodiments of the present disclosure advantageously provide a system and method for efficiently multiplying matrices with elements that have a value of zero.

In one embodiment, a bitmap is generated for each matrix. Each bitmap includes a bit position for each matrix element. The value of each bit is set to 0 when the value of the corresponding matrix element is 0, and to 1 when the value of the corresponding matrix element is not 0. Each matrix is compressed into a compressed matrix, which will have fewer elements with a value of 0 than the original matrix. Each bitmap is then adjusted based on the corresponding compressed matrix.

The compressed matrices are then multiplied, using a computer-based method, coprocessor, hardware accelerator, etc., to generate an output matrix. For each element i,j in the output matrix, a dot product of the ithrow of the first compressed matrix and the jthcolumn of the second compressed matrix is calculated based on the bitmaps.

More particularly, when the bit position in the bitmap corresponding to an element i,k of the ithrow of the first compressed matrix has the value of 1 and when the bit position in the bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix has the value of 1, the element i,k and the element k,j are multiplied to generate an intermediate product. When the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix has a value of 0 or when the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix has the value of 0, the element i,k and the element k,j are not multiplied, thereby reducing processor load, power consumption, etc. The intermediate products are then accumulated to generate the element i,j of the output matrix. The upper limit for the index k is determined by the amount of compression applied to the matrices.

In some embodiments, the compressed matrices will only include elements that have non-zero values. In other embodiments, the compressed matrices will include one or more elements that have a value of 0 in order to maintain compatible dimensions for the multiplication operation. Any elements within the compressed matrices that have a value of 0 are treated as non-zero elements, and will have their respective bit values adjusted to 1 in the corresponding bitmaps. Even though the compressed matrices may include elements that have a value of 0, these elements only minimally effect the overall advantages provided by the present disclosure.

Matrix multiplication is used extensively by ANNs. 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 deep neural network (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 signal 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 signal 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.

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, and uses a non-linear activation function to classify data that is not linearly separable. MLPs may be used for natural language processing applications, such as machine translation, speech recognition, etc. A CNN is a variation of an MLP that has an input layer, an output layer and multiple hidden layers, including a series of convolutional layers, followed by pooling layers, fully-connected layers, and normalization layers. Each convolutional layer applies a sliding dot product or cross-correlation to the input data, and then passes the results to the next layer. CNNs may be used for classification or recognition applications, such as image recognition, speech recognition, etc. Other ANNs include recursive 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.

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

More particularly, the dot product of filter3.1(w1) and the upper left quadrant of input data matrix2.1(a1q1) is equal to a11×w11+a12×w12+a13×w13+a17×w14+a18×w15+a19×w16+a113×w17+a114×w18+a115×w19. The dot products of filter3.2(w2) and the upper left quadrant of input data matrix2.2(a2q1), and filter3.3(w3) and the upper left quadrant of input data matrix2.3(a3q1) are calculated in the same manner, i.e., the dot product of filter3.2(w2) and the upper left quadrant of input data matrix2.2(a2q1) is equal to a21×w21+a22×w22+a23×w23+a27×w24+a28×w25+a29×w26+a213×w27+a214×w28+a215×w29, and the dot product of filter3.3(w3) and the upper left quadrant of input data matrix2.3(a3q1) is equal to a31×w31+a32×w32+a33×w33+a37×w34+a38×w35+a39×w36+a313×w37+a314×w38+a315×w39.

Output data matrix element 02 is the sum of the dot products of filter3.1(w1) and the next upper quadrant of input data matrix2.1, filter3.2(w2) and the next upper quadrant of input data matrix2.2, and filter3.3(w3) and the next upper quadrant of input data matrix2.3. The “next” upper quadrant in each input data matrix2.1,2.2and2.3has been shifted one column to the right relative to the first upper quadrant. More particularly, the dot product of filter3.1(w1) and the next upper quadrant of input data matrix2.1is equal to a12×w11+a13×w12+a14×w13+a18×w14+a19×w15+a110×w16+a114×w17+a115×w18+a116×w19. The dot products of filter3.2(w2) and the next upper quadrant of input data matrix2.2, and filter3.3(w3) and the next upper quadrant of input data matrix2.3are calculated in the same manner, i.e., the dot product of filter3.2(w2) and the next upper quadrant of input data matrix2.2is equal to a22×w21+a23×w22+a24×w23+a28×w24+a29×w25+a210×w26+a214×w27+a215×w28+a216×w29, and the dot product of filter3.3(w3) and the next upper quadrant of input data matrix2.3is equal to a32×w31+a33×w32+a34×w33+a38×w34+a39×w35+a310×w36+a314×w37+a315×w38+a316×w39.

FIG. 1Bdepicts a converted convolutional layer calculation for 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) may be converted into generic matrix multiplication (GEMM) operations, which may leverage GEMM-optimized software libraries. Convolution layer calculation1is converted into a GEMM operation by converting input feature maps2into converted input data matrix5(16×27) and filter3into converted weight matrix6(27×1). After multiplying converted input data matrix5and converted weight matrix6, converted output data matrix7(16×1) is then reformed into output feature map4(4×4). For ease of illustration, converted weight matrix6(27×1) is depicted in a transposed orientation (1×27) inFIG. 1B.

In this example, converted output data matrix element o1is the sum of the dot products of the first row of converted input data matrix5and the first (i.e., only) column of converted weight matrix6. As shown inFIG. 1B, the first row of converted input data matrix5includes the elements of the upper left quadrant of input data matrix2.1(a1q1), the upper left quadrant of input data matrix2.2(a2q1), and the upper left quadrant of input data matrix2.3(a3q1), while the converted weight matrix6includes filter3.1(w1), filter3.2(w2), and filter3.3(w3).

Unfortunately, for CNNs executing on CPUs or other coprocessors, 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 matrices upon which the GEMM operations are performed are sparse, which produces a very inefficient use of processing resources. Conversely, if GEMM operations could significantly reduce “multiply by zero” conditions, processing and power requirements could be significantly reduced. Known approaches that attempt to reduce “multiply by zero” conditions complicate the GEMM operations and introduce significant processing overhead on the CPU.

FIG. 2depicts multiplication of two matrices to generate an output matrix, in accordance with an embodiment of the present disclosure.

In this embodiment, matrix20(4×8), labeled “a′,” is multiplied with matrix30(8×4), labeled “w′,” to produce output matrix40(4×4), labeled “o′.” With respect toFIG. 1B, matrix20may represent a version of a converted input data matrix, matrix30may represent a version of a converted weight matrix, and output matrix40may represent a version of a converted output data matrix. For the purpose of illustration, 50% of the elements of matrix20have a value of zero (white blocks), while 50% of the elements of matrix20have a value that is not zero (shaded blocks). Similarly, 50% of the elements of matrix30have a value of zero (white blocks), while 50% of the elements of matrix30have a value that is not zero (shaded blocks). Due to the arrangement of the zero elements in matrices20and30, 100% of the elements of output matrix40have a value that is not zero. Matrices20and30may be considered to be either sparse matrices or dense matrices, depending on convention.

Embodiments of the present disclosure advantageously provide a system and method for multiplying matrices that significantly reduce “multiply by zero” conditions. Importantly, while the principles and advantages provided by the present disclosure are most applicable to the multiplication of sparse matrices, the principles and advantages provided by the present disclosure remain very applicable to the multiplication of a sparse matrix with a dense matrix, as well as to the multiplication of two dense matrices.

For example, multiplication of a “sparse” matrix with 51% of its elements having a value of zero with a “dense” matrix with 49% of its elements having a value of zero derive nearly as much benefit from the principles and advantages provided by the present disclosure as two “sparse” matrices with 51% of their respective elements having a value that is zero. Similarly, two matrices with 49% of their respective elements having a value that is zero are considered “dense” matrices, but derive nearly as much benefit from the principles and advantages provided by the present disclosure as two “sparse” matrices with 51% of their respective elements having a value that is zero.

FIG. 3depicts a matrix bitmap generation process, in accordance with an embodiment of the present disclosure.

The bit values for each element of matrix20are depicted above each row, in binary and hexadecimal formats. The bit values for each row are formed into nibbles, with the least significant bit (lsb) being the left-most bit, and the most significant bit (msb) being the right-most bit. The first nibble (i.e., 4 bits) for row21has a value of “1011” or 0x5, and the second nibble for row21has a value of “1001” or 0x9; the byte value for row21is “10111001” or 0x59. The first nibble for row22has a value of “1101” or p0xb, and the second nibble for row22has a value of “0100” or 0x2; the byte value for row22is “11010100” or 0xb2. The first nibble for row23has a value of “1001” or 0x9, and the second nibble for row23has a value of “1010” or 0x5; the byte value for row23is “10011010” or 0x95. The first nibble for row24has a value of “0100” or 0x2, and the second nibble for row24has a value of “1101” or 0xb; the byte value for row24is “01001101” or 0x2b. The value for bitmap20b is0x59b2952b, which includes 32 bits (4 bytes, 8 nibbles).

The bit values for each element of matrix30are depicted beside each column, in binary and hexadecimal formats. The bit values for each column are formed into nibbles, with the least significant bit (lsb) being the top-most bit, and the most significant bit (msb) being the bottom-most bit. The first nibble (i.e., 4 bits) for column31has a value of “0101” or 0a, and the second nibble for column31has a value of “0101” or 0a; the byte value for column31is “01010101” or 0xaa. The first nibble for column32has a value of “1010” or 0x5, and the second nibble for column32has a value of “0110” or 0x6; the byte value for column32is “10100110” or 0x56. The first nibble for column33has a value of “1010” or 0x5, and the second nibble for column33has a value of “1001” or 0x9; the byte value for column33is “10101001” or 0x59. The first nibble for column34has a value of “0101” or 0xaa, and the second nibble for column34has a value of “0101” or 0xaa; the byte value for column34is “01010101” or 0xaa. The value for bitmap30b is0xaa5659aa, which includes 32 bits (4 bytes, 8 nibbles).

FIG. 4depicts a matrix compression process, in accordance with an embodiment of the present disclosure.

The dimensions of matrices25and35are determined based on the minimum number of zero-valued elements in each row of matrix20and the minimum number of zero-valued elements in each column of matrix30. Generally, the row of matrix20or the column of matrix30with the least number of zero-valued elements determines the maximum amount of compression available for matrices20and30. In alternative embodiments, elements of matrices20and30having a value above or below a predetermined threshold, outside a predetermined value range, etc., may be set to zero in order to increase the maximum amount of compression.

In this embodiment, rows21,22,23and24each have four zero-valued elements, and columns31,32,33and34each have four zero-valued elements, so the maximum amount of compression is 4 elements per row or column. Matrix20may be compressed from a 4×8 matrix to a 4×4 matrix, and matrix30may be compressed from an 8×4 matrix to a 4×4 matrix, as depicted inFIG. 4.

In another embodiment, row21has two zero-valued elements, column31has three zero-valued elements, rows22,23and24have four zero-valued elements, and columns32,33and34have four zero-valued elements. In this embodiment, the maximum amount of compression is 2 elements. Matrix20may be compressed from a 4×8 matrix to a 4×6 matrix, and matrix30may be compressed from an 8×4 matrix to a 6×4 matrix. Compressed matrix25will include zero-valued elements in rows27,28and29, and compressed matrix35will include at least one zero-valued element in all four columns, resulting in some degree of inefficiency. For extremely sparse matrices, matrix20may be compressed to a 4×1 matrix, and matrix30may be compressed to a 1×4 matrix, resulting in at least an eight-fold reduction of multiplication and accumulation operations. In all these embodiments, the output matrix will always be a 4×4 matrix. Other matrix dimensions are also contemplated.

FIGS. 5A and 5Bdepict compressed matrix flattening processes, in accordance with an embodiment of the present disclosure.

In anticipation of the discussion below, matrices25and35may be flattened from a matrix representation that is stored in a memory (i.e., e.g., row-major order or column-major order) to a vector representation that is stored in a register. In this embodiment, matrix25is flattened by sequentially storing rows26,27,28and29in vector register54, as depicted inFIG. 5A. Bitmap20bis stored in scalar register52. Similarly, matrix35is flattened by sequentially storing columns36,37,38and39in vector register64, as depicted inFIG. 5B. Bitmap30bis stored in scalar register62.

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

Computer100includes bus110coupled to one or more processors120, memory130, I/O interfaces140, display interface150, one or more communication interfaces160and one or more MMAs200. 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, MMA200, 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 computer100. 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 computer100. 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 computer100and/or output from computer100. As discussed above, I/O devices142are operably connected to computer100using a wired and/or wireless connection. I/O devices142may include a local processor coupled to a communication interface that is configured to communicate with computer100using 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 computer100to 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.

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

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

In this embodiment, CE array202includes 16 CEs250arranged in a 4×4 array; other numbers of CEs250and arrangements are also contemplated, such as, for example, four CEs250arranged in a 2×2 array, nine CEs250arranged in a 3×3 array, 25 CEs250arranged in a 5×5 array, 36 CEs250arranged in a 6×6 array, 49 CEs250arranged in a 7×7 array, 64 CEs250arranged in a 8×8 array, etc. Non-symmetric arrangements, such as a 2×3 array, a 3×4 array, a 4×5 array, a 4×6 array, etc., may be advantageous for certain applications. Each CE250is coupled to register220, register230and register240, and calculates a dot product for one element of output matrix40.

For example, CE250located in the first row and the first column (i.e., upper left corner) of CE array202calculates the dot product of the 1strow of matrix25and the 1stcolumn of matrix35, based on bitmap20band bitmap30b, to generate the element for the first row and the first column (i.e., the upper left corner) of output matrix40. Generally, the first row of CEs250receives the first row of data from matrix25, the second row of CEs250receives the second row of data from matrix25, and so on. Similarly, the first column of CEs250receives the first column of data from matrix35, the second column of CEs250receives the second column of data from matrix35, and so on. A more detailed description of the operation of CE250is provided below.

I/O interface210is coupled to bus110, register220, register230and register240. I/O interface210includes a microcontroller that sends data to, and receives data and commands from, processor120, memory130, etc. The microcontroller implements set of instructions that control the data flow and the operation of CEs250.

In some embodiments, a dedicated controller, microcontroller, field programmable gate array (FPGA), etc., may control the data flow and the operation of MMA200. For example, the controller may implement load/store (L/S) instructions, memory mapped I/O (MMIO), direct memory access (DMA), etc., to load the compressed matrices and corresponding bitmaps into registers220and230, start the matrix multiply operation, read back the output matrix from register240, etc. More particularly, one or more software modules134, executing on processor120, may calculate the bitmaps and compress the matrices, send these data and the appropriate commands to MMA200to upload registers220and230, start the matrix multiply operation, read back the results from register240, etc.

Register220includes vector register222and scalar register224. Vector register222stores the flattened elements of the first compressed matrix in the multiplication operation, such as matrix25. Scalar register224stores the bitmap associated with the first matrix in the multiplication operation, such as bitmap20b. In this embodiment, scalar register224is 32 bits wide, and vector register222is 16 elements wide, each element being the same size as the data contained within matrix25, 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 certain embodiments, vector register222and scalar register224have a depth of one register, which allows a single compressed matrix and bitmap to be stored at one time. In other embodiments, vector register222and scalar register224have a depth of two or more registers, which allows multiple compressed matrices and bitmaps to be stored in a pipeline.

Register230includes vector register232and scalar register234. Vector register232stores the flattened elements of the second compressed matrix in the multiplication operation, such as matrix35. Scalar register234stores the bitmap associated with the second matrix in the multiplication operation, such as bitmap30b. In this embodiment, scalar register234is 32 bits wide, and vector register232is 16 elements wide, each element being the same size as the data contained within matrix35, 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 certain embodiments, vector register232and scalar register234have a depth of one register, which allows a single bitmap and compressed matrix to be stored at one time. In other embodiments, vector register232and scalar register234have a depth of two or more registers, which allows multiple bitmaps and compressed matrices to be stored in a pipeline. Generally, scalar register224and234have the same width and depth, and vector registers222and232have the same width and depth. Alternatively, different register dimensions may be advantageous for certain applications.

Register240includes vector register242, which stores the elements of the output matrix in the multiplication operation, such as output matrix40. In this embodiment, vector register242is 16 elements wide, each element being the same size as the data contained within output matrix40, 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 certain embodiments, vector register242has a depth of one register, which allows a single output matrix to be stored at one time. In other embodiments, vector register242has a depth of two or more registers, which allows multiple output matrices to be stored in a pipeline. Vector registers222,232and242all have the same size, such as, for example, 8 bit integer data, etc.

FIG. 8depicts a block diagram of a CE for an MMA, in accordance with an embodiment of the present disclosure.

Multiplexer251is coupled to vector register222via n sets of m parallel data lines. The number of parallel data line sets, n, is equal to the number of columns in the first compressed matrix in the multiplication operation, such as matrix25. In the embodiment depicted inFIG. 7, n equals 4; other matrix dimensions are also contemplated, as discussed above. Each parallel data line set transfers one element of one row of the first compressed matrix from vector register222to multiplexer251. The number of parallel data lines, m, in each set is equal to the size of the element in vector register222, such as 8 for 8 bit integer data, 16 for 16-bit integer data, etc., as discussed above. In other words, the n sets of m parallel data lines transfer one row of data from the first compressed matrix, such as matrix25. For example, for all of the CEs250located in the first row of CE array202, the elements of the first row of data from matrix25that are transferred from vector register222are a1,1, a1,3, a1,5and a1,8.

Multiplexer251is coupled to data selection circuit253via n selection signal lines. Each selection signal line transmits a selection signal that commands multiplexer251to select a respective set of parallel data lines to output to multiplier circuit254. Only a single selection signal is active at one time. Typically, the selection signal is a digital, active high signal; in other embodiments, the selection signal may be a digital, active low signal. And, multiplexer251is coupled to multiplier circuit254via m parallel data lines.

Multiplexer252is coupled to vector register232via n sets of m parallel data lines. The number of parallel data line sets, n, is equal to the number of rows in the second compressed matrix in the multiplication operation, such as matrix35. In the embodiment depicted inFIG. 7, n equals 4; other matrix dimensions are also contemplated, as discussed above. Each parallel data line set transfers one element of one column of the first compressed matrix from vector register232to multiplexer252. The number of parallel data lines, m, in each set is equal to the size of the element in vector register232, such as 8 for 8 bit integer data, 16 for 16-bit integer data, etc., as discussed above. In other words, the n sets of m parallel data lines transfer one column of data from the second compressed matrix, such as matrix35. For example, for all of the CEs250located in the first column of CE array202, the elements of the first column of data from matrix35that are transferred from vector register232are w2,1, w4,1, w6,1and w7,1.

Multiplexer252is coupled to data selection circuit253via n selection signal lines. Each selection signal line transmits a selection signal that commands multiplexer252to select a respective set of parallel data lines to output to multiplier circuit254. Only a single selection signal is active at one time. Typically, the selection signal is a digital, active high signal; in other embodiments, the selection signal may be a digital, active low signal. And, multiplexer252is coupled to multiplier circuit254via m parallel data lines.

Data selection circuit253is coupled to scalar register224via a number data lines, q, equal to the number of columns in the original, uncompressed first matrix, such as matrix20. In the embodiment depicted inFIGS. 3 and 7, q equals 8. These data lines transfer a portion, Ba, of the bitmap corresponding to the original, uncompressed first matrix, such as bitmap20b, from scalar register224to data selection circuit253. The portion of the bitmap that is transferred from scalar register224corresponds to the row data for first compressed matrix that are transferred from vector register222to multiplexer251. For example, for CE250located in the first row and the first column (i.e., upper left corner) of CE array202, the portion of bitmap20bthat is transferred from scalar register224is “10101001” or 0x59.

Data selection circuit253is also coupled to scalar register234via a number data lines, q, equal to the number of rows in the original, uncompressed second matrix, such as matrix30. In the embodiment depicted inFIGS. 3 and 7, q equals 8. These data lines transfer a portion, Bw, of the bitmap corresponding to the original, uncompressed second matrix, such as bitmap30b, from scalar register234to data selection circuit253. The portion of the bitmap that is transferred from scalar register234corresponds to the column data for second compressed matrix that are transferred from vector register232to multiplexer252. For example, for CE250located in the first row and the first column (i.e., upper left corner) of CE array202, the portion of bitmap30bthat is transferred from scalar register234is “01010101” or 0xaa.

In alternative embodiments, data selection circuit253may receive the entire bitmap corresponding to the original, uncompressed first matrix, such as bitmap20b, from scalar register224, as well as the entire bitmap corresponding to the original, uncompressed second matrix, such as bitmap30b, from scalar register234. In these embodiments, data selection circuit253may be configured to extract the appropriate portions from the bitmaps by applying a bitmask, performing a bit shift operation, etc.

Multiplier circuit254is coupled to multiplexer251via m parallel data lines, multiplexer252via m parallel data lines, and accumulator circuit255via m parallel data lines. Multiplier circuit254multiplies the data value, ma, provided by multiplexer251and the data value, mw, provided by multiplexer252, and outputs the resulting data value or intermediate product, ip, to accumulator circuit255. The data values ma, mw and ip have the same size, such as, for example, 8 bit integer, etc.

Accumulator circuit255is coupled to multiplier254via m parallel data lines, and to one element of vector register242via m parallel data lines. Accumulator circuit255includes adder circuit256and accumulator register257. Adder circuit256adds the intermediate product from multiplier circuit254with the current data value stored in accumulator register257, and outputs the resulting data value to accumulator register257. At the end of each dot product calculation cycle, described in more detail below, accumulator register257outputs a final accumulated data value to the corresponding element of vector register242as an ACC_OUT signal. In other words, accumulator circuit255receives the respective intermediate products from multiplier circuit254, and accumulates the respective intermediate products into a value for one element of output matrix40. In alternative embodiments, accumulator register257simply outputs the current data value to the corresponding element of vector register242each time a new data value is received from adder circuit256. In certain embodiments, accumulator circuit255may include multiplexer258that is configured to daisy-chain the accumulator outputs of each CE250in a single row or a single column of CE array202using the ACC_IN and ACC_OUT signals.

During a dot product calculation cycle, data selection circuit253performs q selection cycles, and multiplier circuit254and accumulator circuit255perform between 0 and n multiply and add (MAC) cycles. Generally, during each selection cycle, data selection circuit253determines whether a bit from the bit portion Ba has a value of 1. If so, data selection circuit253sends a selection signal to multiplexer251to select a set of m parallel data lines that correspond to the bit. This causes multiplexer251to output the data value, ma, to multiplier circuit254. Data selection circuit253also determines whether a bit from the bit portion Bw has a value of 1. If so, data selection circuit253sends a selection signal to multiplexer252to select a set of m parallel data lines that correspond to the bit. This causes multiplexer252to output the data value, mw, to multiplier circuit254. When multiplier circuit254receives two non-zero data values, ma and mw, multiplier circuit254and accumulator circuit255begin a MAC cycle, during which time the data value ma and the data value mw are multiplied to form an intermediate product ip, and then the ip is accumulated in accumulator register257.

More particularly, with respect to the embodiments depicted inFIGS. 3, 4, 5A, 5B and 7, q is equal to 8, and n is equal to 4. In the interests of brevity, a single example dot product calculation will be described using CE250located in the first row and the first column (i.e., upper left corner) of CE array202. For this particular CE250, the bit portion Ba is “10101001” or 0x59, the elements of the first row of data from matrix25are a1,1, a1,3, a1,5and a1,8, the bit portion Bw is “01010101” or 0xaa, and the elements of the first column of data from matrix35are w2,1, w4,1, w6,1and w7,1.

During the 1st selection cycle, data selection circuit253determines that the 1st bit in Ba is equal to 1, and outputs a 1st selection signal (e.g., a digital active high signal) to multiplexer251. In response to the 1st selection signal, multiplexer251selects and outputs the 1st element of the first row of matrix25, i.e., a1,1, to multiplier circuit254. Data selection circuit253also determines that the 1st bit in Bw is equal to 0, and does not output a selection signal (e.g., digital low signal). In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Because multiplier circuit254did not receive a data value from multiplexer252, a MAC cycle is not initiated.

During the 2ndselection cycle, data selection circuit253determines that the 2ndbit in Ba is equal to 0, and does not output a selection signal (e.g., digital low signal). In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Data selection circuit253also determines that the 2ndbit in Bw is equal to 1, and outputs a 1st selection signal (e.g., a digital active high signal) to multiplexer252. In response to the 1st selection signal, multiplexer252selects and outputs the 1st element of the first column of matrix25, i.e., w2,1, to multiplier circuit254. Because multiplier circuit254did not receive a data value from multiplexer251, a MAC cycle is not initiated.

During the 3rdselection cycle, data selection circuit253determines that the 3rdbit in Ba is equal to 1, and outputs a 2ndselection signal to multiplexer251. In response to the 2ndselection signal, multiplexer251selects and outputs the 2ndelement of the first row of matrix25, i.e., a1,3, to multiplier circuit254. Data selection circuit253also determines that the 3rdbit in Bw is equal to 0, and does not output a selection signal. In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Because multiplier circuit254did not receive a data value from multiplexer252, a MAC cycle is not initiated.

During the 4th selection cycle, data selection circuit253determines that the 4th bit in Ba is equal to 0, and does not output a selection signal. In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Data selection circuit253also determines that the 4th bit in Bw is equal to 1, and outputs a 2ndselection signal to multiplexer252. In response to the 2ndselection signal, multiplexer252selects and outputs the 2ndelement of the first column of matrix25, i.e., w4,1, to multiplier circuit254. Because multiplier circuit254did not receive a data value from multiplexer251, a MAC cycle is not initiated.

During the 5th selection cycle, data selection circuit253determines that the 5th bit in Ba is equal to 1, and outputs a 3rdselection signal to multiplexer251. In response to the 3rdselection signal, multiplexer251selects and outputs the 3rdelement of the first row of matrix25, i.e., a1,5, to multiplier circuit254. Data selection circuit253also determines that the 5th bit in Bw is equal to 0, and does not output a selection signal. In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Because multiplier circuit254did not receive a data value from multiplexer252, a MAC cycle is not initiated.

During the 6thselection cycle, data selection circuit253determines that the 6thbit in Ba is equal to 0, and does not output a selection signal. In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Data selection circuit253also determines that the 6thbit in Bw is equal to 1, and outputs a 3rdselection signal to multiplexer252. In response to the 3rdselection signal, multiplexer252selects and outputs the 3rdelement of the first column of matrix25, i.e., w6,1, to multiplier circuit254. Because multiplier circuit254did not receive a data value from multiplexer251, a MAC cycle is not initiated.

During the 7thselection cycle, data selection circuit253determines that the 7thbit in Ba is equal to 0, and does not output a selection signal. In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Data selection circuit253also determines that the 7thbit in Bw is equal to 0, and does not output a selection signal. In response to the digital low signal, multiplexer251does not output a data value to multiplier circuit254. Because multiplier circuit254did not receive data values from multiplexers251and252, a MAC cycle is not initiated.

During the 8thselection cycle, data selection circuit253determines that the 8thbit in Ba is equal to 1, and outputs a 4thselection signal to multiplexer251. In response to the 4thselection signal, multiplexer251selects and outputs the 4thelement of the first row of matrix25, i.e., a1,8, to multiplier circuit254. Data selection circuit253also determines that the 8thbit in Bw is equal to 1, and outputs a 4thselection signal to multiplexer252. In response to the 4thselection signal, multiplexer252selects and outputs the 4thelement of the first column of matrix25, i.e., w8,1, to multiplier circuit254. Because multiplier circuit254received data values from multiplexers251and252, a MAC cycle is initiated. Multiplier circuit254multiplies the elements a1,8, and w8,1, and then outputs the intermediate product ip to accumulator circuit255. Adder circuit256adds the value of the intermediate product ip to the current value of accumulator register257, which is 0, and then stores the result in accumulator register257.

At the conclusion of the 8thselection cycle, the current value stored in accumulator register257is output to vector register242, and data selection circuit253outputs a “done” signal to the microcontroller for CE250, such as I/O interface210or a dedicated microcontroller, that the dot product calculation for this particular CE250is complete. Data selection circuit253now waits until new bit portions, Ba and Bw, are respectively received from scalar registers224and234before initiating a new dot product calculation.

In this example, CE250performed 8 selection cycles and one MAC cycle. Because each CE250performs 8 selection cycles and up to 4 MAC cycles per dot product calculation, coordination of the CEs250is necessary. In one embodiment, this coordination is facilitated by the “done” signal. For example, CE250located in the first row and the second column of CE array202will perform 8 selection cycles and two MAC cycles, CE250located in the first row and the third column of CE array202will perform 8 selection cycles and four MAC cycles, and CE250located in the first row and the fourth column of CE array202will perform 8 selection cycles and one MAC cycle. And so forth.

FIG. 9depicts a dataflow diagram for a system with an MMA, in accordance with another embodiment of the present disclosure.

In this embodiment, I/O interface210includes direct memory access (DMA) controller212and device memory214, such as, for example, SRAM. Under the control of processor120and DMA controller212, compressed matrix310and bitmap316are transferred from memory130to device memory214, and compressed matrix320and bitmap326are transferred from memory130to device memory214. Under control of DMA controller212, compressed matrix310is transferred from device memory214to vector register222, bitmap316is transferred from device memory214to scalar register224, compressed matrix320is transferred from device memory214to vector register232, and bitmap326is transferred from device memory214to scalar register234. After the completion of the matrix multiply operation and under the control of DMA controller212, output matrix330is transferred from vector register242to device memory214, and then, under the control of DMA controller212and processor120, output matrix330is transferred from device memory214to memory130.

Table 1 presents the number of MAC operations or cycles for system10for different operand sparsity levels, in accordance with the embodiments depicted inFIGS. 3, 4, 5A, 5B and 7.

Due to the randomness of the input data, each CE250may have a different number MAC cycles, from 0 to 4 cycles, for any given operand vectors, even though the average could be less than 1.0. At the border between a sparse matrix and a dense matrix, i.e., operand 1 at 50% and operand 2 at 50%, any given CE250only requires 2.0 MAC cycles to compute the dot product for one element of output matrix40. A standard MAC configuration requires 8 MAC operations to compute the dot product for one element of output matrix40, due to the necessity of multiplying an 8 element row vector from matrix20(4×8) with an 8 element column vector from matrix30(8×4). The advantages of the present disclosure provide a fourfold (×4) improvement over a standard MAC configuration for 50% sparsity levels, which increases to an elevenfold (×11) improvement for 70% sparsity levels, and a hundredfold (×100) improvement for 90% sparsity levels.

To increase the utilization of each CE250, in one embodiment, buffers maybe added to CE array202to compensate for the randomness of the input data.

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

CE array202has been partitioned into CE zones204,205,206and207, each including 4 CEs250. Buffers270are disposed between each CE zone204,205,206and207and register220, and buffers272are disposed between each CE zone204,205,206and207and register230. The CEs250within each CE zone204,205,206and207process the vector operands and related bitmaps queued within buffers270and272. In this embodiment, buffers270and272have a depth of 2 vector operands and related bitmaps.

FIGS. 11A and 11Bdepict flow diagrams presenting functionality for multiplying matrices, in accordance with embodiments of the present disclosure.

FIG. 11Adepicts flow diagram400, in accordance with an embodiment of the present disclosure.

At410, a first bitmap is generated based on a first matrix, such as, for example, generating bitmap20bbased on matrix20, as discussed above. Each bit position in the first bitmap corresponds to a different element of the first matrix, and has a value of 1 when the value of the corresponding element of the first matrix is not 0, and a value of 0 when the value of the corresponding element of the first matrix is 0.

At420, the first matrix is compressed into a first compressed matrix that has fewer elements with a value of 0 than the first matrix, such as, for example, compressing matrix20into matrix25, as discussed above. In some embodiments, the first compressed matrix will only include elements that have non-zero values. In other embodiments, the first compressed matrix will include one or more elements that have a value of 0 in order to maintain compatible dimensions for the multiplication operation.

At430, the first bitmap is adjusted based on the first compressed matrix. Elements within the first compressed matrix that have a value of 0 are treated as non-zero elements, and their respective bit values are adjusted to 1 in the first bitmap. Even though the first compressed matrix may include elements that have a value of 0, these elements only minimally effect the overall advantages provided by the present disclosure. In the embodiment discussed above, bitmap20bdoes not need to be adjected because matrix25does not have non-zero value elements.

At440, a second bitmap is generated based on a second matrix, such as, for example, generating bitmap30bbased on matrix30, as discussed above. Each bit position in the second bitmap corresponds to a different element of the second matrix, and has a value of 1 when the value of the corresponding element of the second matrix is not 0, and a value of 0 when the value of the corresponding element of the second matrix is 0.

At450, the second matrix is compressed into a second compressed matrix that has fewer elements with a value of 0 than the second matrix, such as, for example, compressing matrix30into matrix35, as discussed above. In some embodiments, the second compressed matrix will only include elements that have non-zero values. In other embodiments, the second compressed matrix will include one or more elements that have a value of 0 in order to maintain compatible dimensions for the multiplication operation.

At460, the second bitmap is adjusted based on the second compressed matrix. Elements within the second compressed matrix that have a value of 0 are treated as non-zero elements, and their respective bit values are adjusted to 1 in the second bitmap. Even though the second compressed matrix may include elements that have a value of 0, these elements only minimally effect the overall advantages provided by the present disclosure. In the embodiment discussed above, bitmap30bdoes not need to be adjected because matrix35does not have non-zero value elements.

At470, the first compressed matrix and the second compressed matrix are multiplied together, based on the first bitmap and the second bitmap, to generate an output matrix, such as, for example, multiplying matrix25with matrix35based on bitmaps20band30b, as discussed above. More particularly, for each element i,j in the output matrix, a dot product of the ithrow of the first compressed matrix and the jthcolumn of the second compressed matrix is calculated based on the first bitmap and the second bitmap.

FIG. 11Bdepicts a flow diagram for functional block470, in accordance with an embodiment of the present disclosure.

In this embodiment, the first matrix has m rows and n columns, the first compressed matrix has m rows and c columns, n is a multiple of c, and the number of non-zero elements in the first matrix is equal to or less than c times m. The second matrix has n rows and p columns, the second compressed matrix has c rows and p columns, and the number of non-zero elements in the second matrix is equal to or less than c times p. The output matrix has m rows and p columns, the row index i for the output matrix goes from 1 to m, and the column index j for the output matrix goes from 1 to p. In the embodiments discussed above, m is 4, n is 8, p is 4 and c is 4 for matrices20,25,30and35.

Functional block470includes process loop471, process loop472and process loop473. Process loop471iterates output matrix row index i from 1 to m, process loop472iterates output matrix column index j from 1 to p, and process loop473iterates output matrix element i,j dot product index k from 1 to c. Within process loop473, the functionality for calculating the dot product for output matrix element i,j includes functional blocks474,475,476and477. Functional block478generates each output matrix element i,j based on the accumulated intermediate products determined by process loop473.

Generally, when the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix has the value of 1 and when the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix has the value of 1, the element i,k and the element k,j are multiplied to generate an intermediate product.

More particularly, at474, the value of the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix is determined. If the value of this bit position is 1, flow proceeds to475. At475, the value of the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix is determined. If the value of this bit position is 1, flow proceeds to476. At476, the element i,k and the element k,j are multiplied to generate an intermediate product, and flow proceeds to477.

Generally, when the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix has the a value of 0 or when the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix has the value of 0, the element i,k and the element k,j are not multiplied.

As discussed above, at474, the value of the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix is determined. If the value of this bit position is 0, no intermediate product is calculated and flow proceeds to477. At475, the value of the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix is determined. If the value of this bit position is 0, no intermediate product is calculated and flow proceeds to477.

Generally, the intermediate products are accumulated to generate the element i,j, More particularly, at477, the intermediate products are accumulated, i.e., added to a running total of the previous intermediate values determined by process loop473. At478, output matrix element i,j is generated based on the accumulated intermediate products determined by process loop473.

Embodiments of the present disclosure advantageously provide a system and a computer-based method for multiplying matrices. The embodiments described above and summarized below are combinable.

In one embodiment, a computer-based method for multiplying matrices includes generating a first bitmap based on a first matrix, the first bitmap having a plurality of bit positions, each bit position corresponding to a different element of the first matrix, each bit position having a value of 1 when a value of the corresponding element of the first matrix is not 0, and a value of 0 when the value of the corresponding element of the first matrix is 0; compressing the first matrix into a first compressed matrix, the first compressed matrix including fewer elements having a value of 0 than the first matrix; adjusting the first bitmap based on the first compressed matrix; generating a second bitmap based on a second matrix, the second bitmap having a plurality of bit positions, each bit position corresponding to a different element of the second matrix, each bit position having the value of 1 when a value of the corresponding element of the second matrix is not 0, and the value of 0 when the value of the corresponding element of the second matrix is 0; compressing the second matrix into a second compressed matrix, the second compressed matrix including fewer elements having a value of 0 than the second matrix; adjusting the second bitmap based on the second compressed matrix; multiplying the first compressed matrix and the second compressed matrix, based on the first bitmap and the second bitmap, to generate an output matrix, including for each element i,j in the output matrix, calculating a dot product of the ithrow of the first compressed matrix and the jthcolumn of the second compressed matrix based on the first bitmap and the second bitmap.

In one embodiment, a system includes a memory, a processor coupled to the memory, and an MMA coupled to the processor and the memory. The processor is configured to generate a first bitmap based on a first matrix, the first bitmap having a plurality of bit positions, each bit position corresponding to a different element of the first matrix, each bit position having a value of 1 when a value of the corresponding element of the first matrix is not 0, and a value of 0 when the value of the corresponding element of the first matrix is 0; compress the first matrix into a first compressed matrix, the first compressed matrix including fewer elements having the value of 0 than the first matrix; adjust the first bitmap based on the first compressed matrix; generate a second bitmap based on a second matrix, the second bitmap having a plurality of bit positions, each bit position corresponding to a different element of the second matrix, each bit position having the value of 1 when a value of the corresponding element of the second matrix is not 0, and the value of 0 when the value of the corresponding element of the second matrix is 0; compress the second matrix into a second compressed matrix, the second compressed matrix including fewer elements having the value of 0 than the second matrix; adjust the second bitmap based on the second compressed matrix. The MMA is configured to multiply the first compressed matrix and the second compressed matrix to generate an output matrix, including for each element i,j of the output matrix, calculate a dot product of the ithrow of the first compressed matrix and the jthcolumn of the second compressed matrix based on the first bitmap and the second bitmap.

In one embodiment, the MMA includes a first scalar register to store the first bitmap; a first vector register to store the first compressed matrix; a second scalar register to store the second bitmap; and a second vector register to store the second compressed matrix; an output register to store the output matrix; and an array of compute elements (CEs), coupled to the first scalar register, the second scalar register, the first vector register, the second vector register and the output register, each CE calculating the dot product for a different element i,j of the output matrix.

In one embodiment, each CE includes a first multiplexer to receive a row of the first compressed matrix, the row including a plurality of first elements, and to selectively output each of the first elements of the row based on a first data selection signal; a second multiplexer to receive a column of the second compressed matrix, the column including a plurality of second elements, and to selectively output each of the second elements of the column based on a second data selection signal; a data selection circuit, coupled to the first multiplexer and the second multiplexer, to receive the first bitmap and the second bitmap, to generate the first data selection signal based on the first bitmap, and to generate the second data selection signal based on the second bitmap; a multiplier circuit, coupled to the first multiplexer and the second multiplexer, to receive the first elements selectively output by the first multiplexer and the second elements selectively output by the second multiplexer, to multiply respective first elements and second elements to generate respective intermediate products, and to output the respective intermediate products; and an accumulator circuit, coupled to the multiplier circuit, to receive the respective intermediate products, and to accumulate the respective intermediate products into a value for one element of the output matrix.

In one embodiment, the first matrix has m rows and n columns, the first compressed matrix has m rows and c columns, and n is a multiple of c; the second matrix has n rows and p columns, and the second compressed matrix has c rows and p columns; the output matrix has m rows and p columns; and i goes from 1 to m, and j goes from 1 to p.

In one embodiment, calculating the dot product of the ithrow of the first compressed matrix and the jthcolumn of the second compressed matrix based on the first bitmap and the second bitmap includes when the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix has a value of 1 and when the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix has a value of 1, multiplying the element i,k and the element k,j to generate an intermediate product; when the bit position in the first bitmap corresponding to an element i,k of the ithrow of the first compressed matrix has a value of 0 or when the bit position in the second bitmap corresponding to an element k,j of the jthcolumn of the second compressed matrix has a value of 0, not multiplying the element i,k and the element k,j; and summing the intermediate products to generate the element i,j; where k goes from 1 to c.

In one embodiment, compressing the first matrix into the first compressed matrix includes beginning with an element located at a first row and a first column of the first matrix, move each element of the first matrix that has a non-zero value into the first compressed matrix in row major order, and when a row of the first matrix has less than c elements that have a non-zero value, move one or more elements that have a zero value into the first compressed matrix so that the corresponding row of the first compressed matrix has c elements; and adjusting the first bitmap based on the first compressed matrix includes change the corresponding bit values in the first bit map from 0 to 1 for said one or more elements of the first matrix that have a zero value that are moved into the first compressed matrix.

In one embodiment, compressing the second matrix into the second compressed matrix includes beginning with an element located at a first row and a first column of the second matrix, move each element of the second matrix that has a non-zero value into the second compressed matrix in column major order, and when a column of the second matrix has less than c elements that have a non-zero value, move one or more elements that have a zero value into the second compressed matrix so that the corresponding column of the second compressed matrix has c elements; and adjusting the second bitmap based on the second compressed matrix includes change the corresponding bit values in the second bit map from 0 to 1 for said one or more elements of the second matrix that have a zero value that are moved into the second compressed matrix.

In one embodiment, a first number of non-zero elements in the first matrix is equal to or less than c times m, and a second number of non-zero elements in the second matrix is equal to or less than c times p.

In one embodiment, compressing the first matrix into the first compressed matrix is performed in place, and said compress the second matrix into the second compressed matrix is performed in place.

In one embodiment, a non-transitory computer-readable medium stores instructions that, when executed by a processor, cause the processor to multiply matrices according to the method described above.

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.