# US 2023/0056246 A1 · Parallel matrix operations in a reconfigurable compute fabric

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

- Number: US 2023/0056246 A1
- Document ID: US20230056246A1
- Status: Published application
- Kind: A1
- Application number: 17/392,756
- Filed: 2021-08-03
- Published: 2023-02-23
- Earliest claimed: 2021-08-03
- Assignees: Micron Technology, Inc.
- Applicants: Micron Technology, Inc.
- Inventors: Skyler Arron Windh; Douglas Vanesko
- Web page: https://patentgrep.com/patent/US20230056246A1

## CPC

- G06F 7/5306: {with row wise addition of partial products (G06F7/5324 takes precedence)}
- G06F 7/5443: {Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00)}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A first set of multiple coordinate data structure elements describing non-zero values of an input matrix may be loaded to a compute element. A first set of input vector values having input vector row numbers corresponding to input matrix column numbers of the first set of multiple coordinate data structure elements may also be loaded to the compute element. Multiple parallel processing lanes of the compute element may be used to update multiple partial accumulation values, where each partial accumulation value corresponds to an output vector row and one of the multiple parallel processing lanes. At least a portion of the partial accumulation values corresponding to the first input matrix row may be summed across at least a portion of the parallel processing lanes to generate a first output vector row value.

## Claims

### Claim 1

A method comprising:
loading to a compute element a first set of multiple coordinate data structure elements, the first set of multiple coordinate data structure elements describing non-zero values of an input matrix, a first coordinate data structure element of the first set of multiple coordinate data structure elements comprising a first input matrix row number, a first input matrix column number, and a first input matrix value corresponding to the first input matrix row number and the first input matrix column number;
loading to the compute element a first set of input vector values having input vector row numbers corresponding to input matrix column numbers of the first set of multiple coordinate data structure elements;
using multiple parallel processing lanes of the compute element to update multiple partial accumulation values respectively corresponding to an output vector row and one of the multiple parallel processing lanes, the update being based at least in part on the first multiple coordinate data structure elements and the first set of input vector values; and
summing a portion of the multiple partial accumulation values corresponding to the first input matrix row across at least a portion of the parallel processing lanes to generate a first output vector row value.

### Claim 2 (depends on 1)

The method of claim 1, further comprising summing a portion of the multiple partial accumulation values corresponding to a second input matrix row across at least a portion of the parallel processing lanes to generate a second output vector row value.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
loading to the compute element a second set of multiple coordinate data structure elements, the second set of multiple coordinate data structure elements also describing non-zero values of the input matrix;
loading to the compute element a second set of input vector values having input vector row numbers corresponding to input matrix column numbers of the second set of multiple coordinate data structure elements; and
using the multiple parallel processing lanes of the compute element to update at least a portion of the plurality of partial accumulation values using the second set of multiple coordinate data structure elements and the second set of input vector values.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
determining a portion of the coordinate data structure elements corresponding to a first number of rows of the input matrix, the first number of rows of the input matrix comprising the first input matrix row, the portion of the coordinate data structure elements comprising the first set of multiple coordinate data structure elements; and
updating the multiple partial accumulation values using the portion of the coordinate data structure elements corresponding to the first number of rows of the input matrix before summing the portion of the multiple partial accumulation values corresponding to the first input matrix row.

### Claim 5 (depends on 1)

The method of claim 1, the first set of input vector values comprising multiple input vector values having non-contiguous input vector row numbers.

### Claim 6 (depends on 1)

The method of claim 1, wherein the update of the multiple partial accumulation values comprises executing a write operation that writes a first updated partial accumulation value of the multiple partial accumulation values to a first memory location and a second updated partial accumulation value of the multiple partial accumulation values to a second memory location that is not contiguous with the first memory location.

### Claim 7 (depends on 1)

The method of claim 1, the loading of the first set of input vector values being a gather load from non-contiguous memory locations at a compute element memory.

### Claim 8 (depends on 1)

The method of claim 1, the update of the multiple partial accumulation values comprising:
applying a hash function to the first input matrix row number to generate a first row number hash; and
writing a first partial accumulation value corresponding to the first input matrix row and a first processing lane of the multiple parallel processing lanes to a first location at a compute element memory using the first row number hash.

### Claim 9 (depends on 8)

The method of claim 8, the update of the multiple partial accumulation values comprising:
applying the hash function to a second input matrix row number of a second coordinate data structure of the first set of multiple coordinate data structure elements to generate a second row number hash; and
writing a second partial accumulation value corresponding to the second input matrix row and a second processing lane of the multiple parallel processing lanes to a second location at a compute element memory using the first row number hash, the second location being noncontiguous with the first location, and the writing of the first partial accumulation value and the second partial accumulation value being performed with a scatter write operation.

### Claim 10

An apparatus comprising:
a compute element memory comprising multiple memory locations; and
a compute element in communication with the compute element memory, the compute element comprising multiple parallel processing lanes, the compute element programmed to execute operations comprising:
loading a first set of multiple coordinate data structure elements, the first set of multiple coordinate data structure elements describing non-zero values of an input matrix, a first coordinate data structure element of the first set of multiple coordinate data structure elements comprising a first input matrix row number, a first input matrix column number, and a first input matrix value corresponding to the first input matrix row number and the first input matrix column number;
loading from the compute element memory a first set of input vector values having input vector row numbers corresponding to input matrix column numbers of the first set of multiple coordinate data structure elements;
using the multiple parallel processing lanes of the compute element to update multiple partial accumulation values respectively corresponding to an output vector row and one of the multiple parallel processing lanes, the update being based at least in part on the first set of multiple coordinate data structure elements and the first set of input vector values; and
summing a portion of the multiple partial accumulation values corresponding to the first input matrix row across at least a portion of the parallel processing lanes to generate a first output vector row value.

### Claim 11 (depends on 10)

The apparatus of claim 10, the operations further comprising summing a portion of the multiple partial accumulation values corresponding to a second input matrix row across at least a portion of the parallel processing lanes to generate a second output vector row value.

### Claim 12 (depends on 10)

The apparatus of claim 10, the operations further comprising:
loading to the compute element a second set of multiple coordinate data structure elements, the second set of multiple coordinate data structure elements also describing non-zero values of the input matrix;
loading to the compute element a second set of input vector values having input vector row numbers corresponding to input matrix column numbers of the second set of multiple coordinate data structure elements; and
using the multiple parallel processing lanes of the compute element to update at least a portion of the multiple partial accumulation values using the second set of multiple coordinate data structure elements and the second set of input vector values.

### Claim 13 (depends on 10)

The apparatus of claim 10, the operations further comprising:
determining a portion of the coordinate data structure elements corresponding to a first number of rows of the input matrix, the first number of rows of the input matrix comprising the first input matrix row, the portion of the coordinate data structure elements comprising the first set of multiple coordinate data structure elements; and
updating the multiple partial accumulation values using the portion of the coordinate data structure elements corresponding to the first number of rows of the input matrix before summing the portion of the multiple partial accumulation values corresponding to the first input matrix row.

### Claim 14 (depends on 10)

The apparatus of claim 10, the first set of input vector values comprising multiple input vector values having non-contiguous input vector row numbers.

### Claim 15 (depends on 10)

The apparatus of claim 10, wherein the update of the multiple partial accumulation values comprises executing a write operation that writes a first updated partial accumulation value of the multiple partial accumulation values to a first memory location and a second updated partial accumulation value of the multiple partial accumulation values to a second memory location that is not contiguous with the first memory location.

### Claim 16 (depends on 10)

The apparatus of claim 10, the loading of the first set of input vector values being a gather load from non-contiguous memory locations at a compute element memory.

### Claim 17 (depends on 10)

The apparatus of claim 10, the update of the multiple partial accumulation values comprising:
applying a hash function to the first input matrix row number to generate a first row number hash; and
writing a first partial accumulation value corresponding to the first input matrix row and a first processing lane of the multiple parallel processing lanes to a first location at a compute element memory using the first row number hash.

### Claim 18 (depends on 17)

The apparatus of claim 17, the update of the multiple partial accumulation values comprising:
applying the hash function to a second input matrix row number of a second coordinate data structure of the first set of multiple coordinate data structure elements to generate a second row number hash; and
writing a second partial accumulation value corresponding to the second input matrix row and a second processing lane of the multiple parallel processing lanes to a second location at a compute element memory using the first row number hash, the second location being noncontiguous with the first location, and the writing of the first partial accumulation value and the second partial accumulation value being performed with a scatter write operation.

### Claim 19

A machine-readable medium comprising instructions thereon that, when executed by a computer architecture, causes the computer architecture to execute operations comprising:
loading to a compute element of the computer architecture a first set of multiple coordinate data structure elements, the first set of multiple coordinate data structure elements describing non-zero values of an input matrix, a first coordinate data structure element of the first set of multiple coordinate data structure elements comprising a first input matrix row number, a first input matrix column number, and a first input matrix value corresponding to the first input matrix row number and the first input matrix column number;
loading to the compute element a first set of input vector values having input vector row numbers corresponding to input matrix column numbers of the first set of multiple coordinate data structure elements;
using multiple parallel processing lanes of the compute element to update multiple partial accumulation values respectively corresponding to an output vector row and one of the multiple parallel processing lanes, the update being based at least in part on the first set of multiple coordinate data structure elements and the first set of input vector values; and
summing a portion of the multiple partial accumulation values corresponding to the first input matrix row across at least a portion of the parallel processing lanes to generate a first output vector row value.

### Claim 20 (depends on 19)

The machine-readable medium of claim 19, the operations further comprising summing a portion of the multiple partial accumulation values corresponding to a second input matrix row across at least a portion of the parallel processing lanes to generate a second output vector row value.
