# US 2022/0035890 A1 · Time Domain Unrolling Sparse Matrix Multiplication System and Method

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0035890 A1
- Document ID: US20220035890A1
- Status: Published application
- Kind: A1
- Application number: 17/103,676
- Filed: 2020-11-24
- Published: 2022-02-03
- Earliest claimed: 2020-07-30
- Assignees: Arm Limited
- Applicants: Arm Limited
- Inventors: Zhi-Gang Liu; Paul Nicholas Whatmough; Matthew Mattina
- Web page: https://patentgrep.com/patent/US20220035890A1

## CPC

- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 7/5443: {Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00)}
- G06F 15/80: comprising an array of processing units with common control, e.g. single instruction multiple data processors (G06F15/82 takes precedence {; for correlation function computation G06F17/15})
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/0495: Quantised networks; Sparse networks; Compressed networks
- G06F 7/50: Adding; Subtracting (G06F7/483 - G06F7/491, G06F7/544 - G06F7/556 take precedence)
- G06F 7/523: Multiplying only
- G06F 9/3893: {controlled in tandem, e.g. multiplier-accumulator}
- G06N 3/048: Activation functions
- G06N 3/08: Learning methods
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A system and method for multiplying matrices are provided. The system includes a processor coupled to a memory and a matrix multiply accelerator (MMA) coupled to the processor. The MMA is configured to multiply, based on a bitmap, a compressed first matrix and a second matrix to generate an output matrix including, for each element i,j of the output matrix, calculate a dot product of an ith row of the compressed first matrix and a jth column of the second matrix based on the bitmap. Or, the MMA is configured to multiply, based on the bitmap, the second matrix and the compressed first matrix and to generate the output matrix including, for each element i,j of the output matrix, calculate a dot product of an ith row of the second matrix and a jth column of the compressed first matrix based on the bitmap.

## Claims

### Claim 1

A system, comprising:
a processor coupled to a memory; and
a matrix multiply accelerator (MMA), coupled to the processor, configured to:
multiply, based on a bitmap, a compressed first matrix and a second matrix to generate an output matrix, the bitmap including a plurality of bit positions, each bit position corresponding to a different element of the first matrix, said multiply including:
for each element i,j of the output matrix, calculate a dot product of an ith row of the compressed first matrix and a jth column of the second matrix based on the bitmap; or multiply, based on the bitmap, the second matrix and the compressed first matrix and to generate the output matrix, including:
for each element i,j of the output matrix, calculate a dot product of an ith row of the second matrix and a jth column of the compressed first matrix based on the bitmap.

### Claim 2 (depends on 1)

The system of claim 1, where:
the processor is configured to:
generate the bitmap based on a first matrix having a plurality of elements; and
compress the first matrix into the compressed first matrix having fewer elements than the first matrix,
where each bit position has 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.

### Claim 3 (depends on 1)

The system of claim 1, where said compress the first matrix includes:
for each column of the first matrix, move each element of the column that has a non-zero value into a corresponding column of the compressed first matrix.

### Claim 4 (depends on 2)

The system of claim 2, where the MMA includes:
a scalar register to store the bitmap;
a first vector register to store the compressed first matrix;
a second vector register to store the second matrix;
an output vector register to store the output matrix; and
an array of processing engines (PEs), each PE coupled to the scalar register, the first vector register, the second vector register and the output vector register, each PE configured to calculate the dot product for a different element of the output matrix.

### Claim 5 (depends on 4)

The system of claim 4, where each PE includes:
a data selection circuit configured to receive the bitmap and generate a plurality of data selection signals based on the bitmap;
a plurality of data selectors, coupled to the data selection circuit, each data selector configured to:
receive one of the data selection signals from the data selection circuit,
receive a row of the second matrix, the row having a plurality of elements, and
selectively output one of the elements of the row based on the data selection signal;
a plurality of multiplier circuits, each multiplier circuit coupled to a respective data selector, each multiplier circuit configured to:
receive a column element of a same column of the compressed first matrix,
receive the row element selectively output by the respective data selector,
multiply the column element and the row element to generate an intermediate product, and
output the intermediate product; and
an accumulator circuit, coupled to the plurality of multiplier circuits, configured to:
receive the intermediate products from the multiplier circuits,
add the intermediate products to generate an element of the output matrix, and
output the element of the output matrix.

### Claim 6 (depends on 5)

The system of claim 5, where the data selectors are multiplexers.

### Claim 7 (depends on 6)

The system according to claim 6, where the array of PEs includes 16 PEs, each PE includes four multiplexers and four multiplier circuits, each multiplexer has eight input ports and one output port, the bitmap includes 32 bits, the compressed first matrix is a 4×4 matrix, the second matrix is a 4×8 matrix and the output matrix is a 4×4 matrix.

### Claim 8 (depends on 4)

The system of claim 4, where each PE includes:
a data selection circuit configured to receive the bitmap and generate a data selection signal based on the bitmap;
a data selector, coupled to the data selection circuit, configured to:
receive a row of the second matrix, the row having a plurality of elements, and
selectively output one of the elements of the row based on the data selection signal;
a multiplier circuit, coupled to the data selector, configured to:
receive a column element of a column of the compressed first matrix,
receive the row element selectively output by the data selector,
multiply the column element and the row element to generate an intermediate product, and
output the intermediate product; and
an accumulator circuit, coupled to the multiplier circuit, configured to:
receive the intermediate product from the multiplier circuit,
accumulate the intermediate product into an element of the output matrix, and
output the element of the output matrix after a last column element has been received by the multiplier circuit.

### Claim 9 (depends on 8)

The system of claim 8, where the data selector is a multiplexer.

### Claim 10 (depends on 9)

The system according to claim 9, where the array of PEs includes 16 PEs, the multiplexer has eight input ports and one output port, the bitmap includes 32 bits, the compressed first matrix is a 4×4 matrix, the second matrix is a 4×8 matrix and the output matrix is a 4×4 matrix.

### Claim 11

A computer-based method for multiplying matrices, comprising:
multiplying, based on a bitmap, a compressed first matrix and a second matrix to generate an output matrix, the bitmap including a plurality of bit positions, each bit position corresponding to a different element of the first matrix, said multiplying including:
for each element i,j of the output matrix, calculating a dot product of an ith row of the compressed first matrix and a jth column of the second matrix based on the bitmap; or
multiplying, based on the bitmap, the second matrix and the compressed first matrix to generate the output matrix, including:
for each element i,j of the output matrix, calculating a dot product of an ith row of the second matrix and a jth column of the compressed first matrix based on the bitmap.

### Claim 12 (depends on 11)

The computer-based method of claim 11, further comprising:
generating the bitmap based on a first matrix having a plurality of elements; and
compressing the first matrix into the compressed first matrix having fewer elements than the first matrix,
where each bit position has 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.

### Claim 13 (depends on 11)

The computer-based method of claim 11, where said compressing the first matrix includes:
for each column of the first matrix, moving each element of the column that has a non-zero value into a corresponding column of the compressed first matrix.

### Claim 14 (depends on 12)

The computer-based method of claim 12, where said calculating the dot product is performed by a matrix multiply accelerator that includes a scalar register, a first vector register, a second vector register, an output vector register and an array of processing engines (PEs), and the computer-based method further comprises:
storing the bitmap in the scalar register;
storing the compressed first matrix in the first vector register;
storing the second matrix in the second vector register;
storing the output matrix in the output vector register; and
calculating, by each PE, the dot product for a different element of the output matrix.

### Claim 15 (depends on 14)

The computer-based method of claim 14, where each PE includes a data selection circuit, a plurality of data selectors, a plurality of multiplier circuits, each multiplier circuit coupled to a respective data selector, and an accumulator circuit coupled to the multiplier circuits, and the computer-based method further comprises:
at the data selection circuit:
receiving the bitmap, and
generating a plurality of data selection signals based on the bitmap;
at each data selector:
receiving one of the data selection signals from the data selection circuit,
receiving a row of the second matrix, the row having a plurality of elements, and
selectively outputting one of the elements of the row based on the data selection signal;
at each multiplier circuit:
receiving a column element of a same column of the compressed first matrix,
receiving the row element selectively output by the respective data selector,
multiplying the column element and the row element to generate an intermediate product, and
outputting the intermediate product; and
at the accumulator circuit:
receiving the intermediate products from the multiplier circuits,
adding the intermediate products to generate an element of the output matrix, and
outputting the element of the output matrix.

### Claim 16 (depends on 15)

The computer-based method of claim 15, where the data selectors are multiplexers.

### Claim 17 (depends on 16)

The computer-based method of claim 16, where the array of PEs includes 16 PEs, each PE includes four multiplexers and four multiplier circuits, each multiplexer has eight input ports and one output port, the bitmap includes 32 bits, the compressed first matrix is a 4×4 matrix, the second matrix is a 4×8 matrix and the output matrix is a 4×4 matrix.

### Claim 18 (depends on 14)

The computer-based method of claim 14, where each PE includes a data selection circuit, a data selector, a multiplier circuit coupled to the data selector, and an accumulator circuit, and the computer-based method further comprises:
at the data selection circuit:
receiving the bitmap, and
generating a data selection signal based on the bitmap;
at the data selector:
receiving a row of the second matrix, the row having a plurality of elements, and
selectively outputting one of the elements of the row based on the data selection signal;
at the multiplier circuit:
receiving a column element of a column of the compressed first matrix,
receiving the row element selectively output by the data selector,
multiplying the column element and the row element to generate an intermediate product, and
outputting the intermediate product; and
at the accumulator circuit:
receiving the intermediate product from the multiplier circuit,
accumulating the intermediate product into an element of the output matrix, and
outputting the element of the output matrix after a last column element has been received by the multiplier circuit.

### Claim 19 (depends on 18)

The computer-based method of claim 18, where the data selector is a multiplexer.

### Claim 20 (depends on 19)

The computer-based method of claim 19, where the array of PEs includes 16 PEs, the multiplexer has eight input ports and one output port, the bitmap includes 32 bits, the compressed first matrix is a 4×4 matrix, the second matrix is a 4×8 matrix and the output matrix is a 4×4 matrix.
