Sparse matrix multiplier in hardware and a reconfigurable data processor including same

A method to perform a matrix multiply using an array of configurable units coupled by an array level network, the array of configurable units including configurable memory units having one or more banks of scratchpad memory and configurable compute units having a multi-stage single-instruction multiple datapath (SIMD) computation pipeline, the method comprising:

• obtaining, at a first set of configurable units, a multiplicand matrix and an index of columns for non-zero values of a multiplier matrix;
• selecting, by the first set of configurable units, rows of the multiplicand matrix based on respective entries of the index of columns of the multiplier matrix;
• obtaining, at a second set of configurable units, a first list of non-zero values of the multiplier matrix, and a second list of a number of non-zero entries per row of the multiplier matrix;
• multiplying, in the second set of configurable units, the selected rows of the multiplicand matrix by respective non-zero values of the first list to create partial products;
• selectively accumulating the partial products in the second set of configurable units based on the second list to generate a product matrix;
• and
• providing the product matrix as a result of the matrix multiply.

A non-transitory machine-readable medium comprising one or more instructions that in response to being executed on a computing device cause the computing device to carry out a matrix multiply using an array of configurable units coupled by an array level network, the array of configurable units including configurable memory units having one or more banks of scratchpad memory and configurable compute units having a multi-stage single-instruction multiple datapath (SIMD) computation pipeline using a method comprising:

• obtaining, at a first set of configurable units, a multiplicand matrix and an index of columns for non-zero values of a multiplier matrix;
• selecting, by the first set of configurable units, rows of the multiplicand matrix based on respective entries of the index of columns of the multiplier matrix to create an intermediate matrix having one row per entry in said index;
• obtaining, at a second set of configurable units, a first list of non-zero values of the multiplier matrix, and a second list of a number of non-zero entries per row of the multiplier matrix;
• multiplying, in the second set of configurable units, the non-zero values of the first list and elements of the intermediate matrix to create partial products;
• selectively accumulating the partial products in the second set of configurable units based on the second list to generate a product matrix;
• and
• providing the product matrix as a result of the matrix multiply.

An apparatus to multiply a multiplicand matrix by a sparse multiplier matrix comprising:

• a first scratchpad memory to store at least a portion of the multiplicand matrix;
• address calculation circuitry configured to obtain an index of columns for non-zero values of the sparse multiplier matrix, calculate a location of a corresponding row of the multiplicand matrix in the first scratchpad memory for each entry of the index of columns to be a row of an intermediate matrix, and retrieve the rows of the intermediate matrix from the first scratchpad memory;
• multiplication circuitry configured to obtain a first list of the non-zero values of the sparse multiplier matrix corresponding to the index of columns, and to multiply entries of the rows of the intermediate matrix by a corresponding entry in the first list to generate rows of partial products;
• and
• accumulation circuitry configured to obtain a second list of a number of non-zero entries per row of the sparse multiplier matrix and selectively add the rows of the partial products based on the second list to generate rows of a product matrix.