# US 2026/0087091 A1 · Work graph-based sparse linear algebra operations for parallel processors

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

- Number: US 2026/0087091 A1
- Document ID: US20260087091A1
- Status: Published application
- Kind: A1
- Application number: 18/895,657
- Filed: 2024-09-25
- Published: 2026-03-26
- Earliest claimed: 2024-09-25
- Assignees: Advanced Micro Devices, Inc.
- Applicants: Advanced Micro Devices, Inc.
- Inventors: William Peter Ehrett; Bradford Michael Beckmann; Paul Fridtjof Trojahn; Dominik Joerg Baumeister; Fabian Robert Sebastian Wildgrube
- Web page: https://patentgrep.com/patent/US20260087091A1

## CPC

- 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 processor includes a plurality of processing elements. The processor is configured to execute a work graph including a plurality of nodes representing kernels executable by one or more processing elements of the plurality of processing elements. A first processing element of the one or more of the processing elements associated with a first node of the plurality of nodes is configured to assign each logical division of a sparse input matrix to a bin of a plurality of bins. Responsive to a dispatch condition associated with a bin of the plurality of bins, the processor is configured to dispatch a workgroup to at least a second processing element associated with at least a second node of the plurality of nodes corresponding to the bin. The workgroup includes a plurality of work items based on one or more logical divisions of the sparse input matrix assigned to the bin.

## Claims

### Claim 1

A method comprising:
executing, at a processor of a computing system, a work graph comprising a plurality of nodes representing kernels executable by one or more processing elements of the processor;
assigning, by a first node of the plurality of nodes, each logical division of a sparse input matrix to a bin of a plurality of bins; and
responsive to a dispatch condition associated with a bin of the plurality of bins, dispatching a workgroup to a second node of the plurality of nodes associated with the bin, the workgroup comprising a plurality of work items based on one or more logical divisions of the sparse input matrix assigned to the bin.

### Claim 2 (depends on 1)

The method of claim 1, wherein assigning each logical division of the sparse input matrix to a bin of the plurality of bins comprises:
calculating, by the first node, a logical division length for each logical division of the sparse input matrix; and
assigning, by the first node, each logical division of the sparse input matrix to a bin of the plurality of bins based on the logical division length calculated for the logical division.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
initializing, by the processor, the plurality of bins;
assigning, by the processor, each bin of the plurality of bins to a different range of logical division lengths; and
assigning, by the processor, one or more nodes of the plurality of nodes to each bin of the plurality of bins.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
storing in memory, by the first node, a copy of the plurality of work items in the workgroup dispatched to the second node.

### Claim 5 (depends on 1)

The method of claim 1, wherein the dispatch condition comprises at least one of a number of logical divisions of the sparse input matrix assigned to the bin satisfying a first threshold, or a cache locality of logical divisions of the sparse input matrix assigned to the bin satisfying a second threshold.

### Claim 6 (depends on 1)

The method of claim 1, wherein further comprising:
performing, by the second node, one or more sparse linear algebra operations on the one or more logical divisions of the sparse input matrix assigned to the bin.

### Claim 7 (depends on 6)

The method of claim 6, wherein performing the one or more sparse linear algebra operations comprises, for each logical division of the one or more logical divisions:
multiplying each non-zero value of the logical division by a corresponding element in an input vector to produce a partial result;
accumulating each partial result into a logical division result; and
storing the logical division result in an output vector.

### Claim 8

A processor, comprising:
a plurality of processing elements,
the processor configured to execute a work graph comprising a plurality of nodes representing kernels executable by one or more processing elements of the plurality of processing elements,
a first processing element of the one or more of the processing elements associated with a first node of the plurality of nodes is configured to assign each logical division of a sparse input matrix to a bin of a plurality of bins, and
responsive to a dispatch condition associated with a bin of the plurality of bins, the processor is configured to dispatch a workgroup to at least a second processing element associated with at least a second node of the plurality of nodes corresponding to the bin, the workgroup comprising a plurality of work items based on one or more logical divisions of the sparse input matrix assigned to the bin.

### Claim 9 (depends on 8)

The processor of claim 8, wherein the first processing element is configured to assign each logical division of the sparse input matrix to a bin of the plurality of bins by:
calculating a logical division length for each logical division of the sparse input matrix; and
assigning each logical division of the sparse input matrix to a bin of the plurality of bins based on the logical division length calculated for the logical division.

### Claim 10 (depends on 8)

The processor of claim 8, wherein the processor is further configured to:
initialize the plurality of bins;
assign each bin of the plurality of bins to a different range of logical division lengths; and
assign one or more nodes of the plurality of nodes to each bin of the plurality of bins.

### Claim 11 (depends on 8)

The processor of claim 8, wherein the first processing element is further configured to:
store in a memory of the processor a copy of the plurality of work items in the workgroup dispatched to the at least second processing element.

### Claim 12 (depends on 8)

The processor of claim 8, wherein the dispatch condition comprises at least one of a number of logical divisions of the sparse input matrix assigned to the bin satisfying a first threshold, or a cache locality of logical divisions of the sparse input matrix assigned to the bin satisfying a second threshold.

### Claim 13 (depends on 8)

The processor of claim 8, wherein the at least second processing element is configured to:
perform one or more sparse linear algebra operations on the one or more logical divisions of the sparse input matrix assigned to the bin.

### Claim 14 (depends on 13)

The processor of claim 13, wherein the at least second processing element is configured to perform the one or more sparse linear algebra operations, for each logical division of the one or more logical divisions, by:
multiplying each non-zero value of the logical division by a corresponding element in an input vector to produce a partial result;
accumulating each partial result into a logical division result; and
storing the logical division result in an output vector.

### Claim 15

A method comprising:
executing, at a processor of a computing system, a work graph comprising a plurality of nodes representing kernels executable by one or more processing elements of the processor; and
during a first set of operations on a sparse input matrix using a first input vector:
assigning, by a binning node of the plurality of nodes, each logical division of the sparse input matrix to a bin of a plurality of bins; and
storing, by the binning node for each bin of the plurality of bins, a logical division count in one or more buffers indicating a number of logical divisions of the sparse input matrix assigned to the bin.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
during a second set of operations on the sparse input matrix using a second input vector, initializing, by a preparation node of the plurality of nodes, a work item buffer comprising headers identifying subregions of the work item buffer as input work items for processing nodes of the plurality of nodes.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
during the second set of operations, dispatching, by the binning node, a workgroup to at least one processing node of the plurality of nodes comprising a plurality of work items based on one or more logical divisions of the sparse input matrix assigned to at least one bin of the plurality of bins associated with at least one processing node; and
storing a copy of the plurality of work items in corresponding locations of the work item buffer as the input work items.

### Claim 18 (depends on 17)

The method of claim 17, further comprising:
during a third set of operations on the sparse input matrix using a third input vector, scheduling the plurality of work items on the at least one processing node of the plurality of nodes based on the copy of the plurality of work items stored in the work item buffer.

### Claim 19 (depends on 15)

The method of claim 15, wherein assigning each logical division of the sparse input matrix to a bin of the plurality of bins comprises:
calculating, by the binning node, a logical division length for each logical division of the sparse input matrix; and
assigning, by the binning node, each logical division of the sparse input matrix to a bin of the plurality of bins based on the logical division length calculated for the logical division.

### Claim 20 (depends on 15)

The method of claim 15, wherein assigning each logical division of the sparse input matrix to a bin of the plurality of bins comprises:
associating, by the binning node, at least a logical division identifier with the bin for each logical division assigned to the bin.
