# US 12,007,885 B2 · Fetching non-zero data

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

- Number: US 12,007,885 B2
- Document ID: US12007885B2
- Status: Granted
- Kind: B2
- Application number: 17/729,931
- Filed: 2022-04-26
- Published: 2023-10-26
- Granted: 2024-06-11
- Earliest claimed: 2022-04-26
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Karthikeyan Avudaiyappan; Jeffrey A Andrews
- Web page: https://patentgrep.com/patent/US12007885B2

## CPC

- G06F 9/345: of multiple operands or results {(addressing multiple banks G06F12/06)}
- G06F 12/023: {Free address space management}
- G06F 9/3824: {Operand accessing}
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- G06F 2212/251: Local memory within processor subsystem
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Embodiments of the present disclosure include techniques storing and retrieving data. In one embodiment, sub-matrices of data are stored as row slices and column slices. A fetch circuit determines if particular slices of one sub-matrix, when combined with corresponding slices of another sub-matrix, produce a zero result and need not be retrieved. In another embodiment, the present disclosure includes a memory circuit comprising memory banks and sub-banks. The sub-banks store slices of sub-matrices. A request moves between serially configured memory banks and slices in different sub-banks may be retrieved at the same time.

## Claims

### Claim 1

A circuit for storing and retrieving data comprising:
at least one memory circuit storing a first sub-matrix of data as a plurality of row slices comprising a plurality of data values and storing a second sub-matrix of data as a plurality of column slices comprising a plurality of data values; and
a fetch circuit,
wherein the fetch circuit determines row slices of the first sub-matrix of data that produce a non-zero result when multiplied by a plurality of corresponding column slices of the second sub-matrix of data, and the determined row slices are retrieved from the at least one memory circuit.

### Claim 2 (depends on 1)

The circuit of claim 1, wherein the fetch circuit determines row slices of the first sub-matrix of data that produce a non-zero result when multiplied by a plurality of corresponding column slices of the second sub-matrix of data while row slices of a third sub-matrix of data that produce a non-zero result when multiplied by a plurality of corresponding column slices of the fourth sub-matrix of data are being retrieved.

### Claim 3 (depends on 2)

The circuit of claim 2, wherein the first sub-matrix of data and the third sub-matrix of data are from a first matrix of data, and wherein the second sub-matrix of data and the fourth sub-matrix of data are from a second matrix of data.

### Claim 4 (depends on 1)

The circuit of claim 1, wherein the at least one memory circuit stores a first mask corresponding to the first sub-matrix, wherein the first mask specifies row slices having at least one non-zero value.

### Claim 5 (depends on 4)

The circuit of claim 4, wherein the fetch circuit eliminates row slices having all zero values from being retrieved based on the first mask.

### Claim 6 (depends on 1)

The circuit of claim 1, wherein the fetch circuit analyzes the first sub-matrix in said at least one memory to determine the row slices that produce non-zero results.

### Claim 7 (depends on 6)

The circuit of claim 6, wherein the fetch circuit determines, for a plurality of row slices, whether a particular row slice produces a zero or non-zero result when multiplied by a plurality of corresponding column slices.

### Claim 8 (depends on 6)

The circuit of claim 6, wherein the fetch circuit receives a bit mask comprising 1 bit per row slice of the first sub-matrix, wherein particular row slices of the first sub-matrix having a first bit mask value indicating the particular row slices comprise all zeros are eliminated from the determined row slices to be retrieved.

### Claim 9 (depends on 8)

The circuit of claim 8, further wherein, after eliminating row slices comprising all zeros, the fetch circuit determines first row slices of the first sub-matrix of data that produce a zero result when multiplied by a plurality of corresponding column slices of the second sub-matrix of data to eliminate the first row slices from the determined row slices to be retrieved.

### Claim 10 (depends on 8)

The circuit of claim 8, further wherein the fetch circuit logically ANDs values of remaining non-all zero row slices of the first sub-matrix with corresponding values of the column slices of the second sub-matrix to produce a plurality of results and logically ORs the plurality of results to eliminate a plurality of non-all zero row slices producing a zero result from the determined row slices to be retrieved.

### Claim 11 (depends on 1)

The circuit of claim 1, wherein the first sub-matrix is stored in row major order and the second sub-matrix is stored in column major order.

### Claim 12 (depends on 1)

The circuit of claim 1, wherein the first sub-matrix is a portion of a first matrix stored in row major order and the second sub-matrix is a portion of a second matrix stored in column major order.

### Claim 13 (depends on 1)

The circuit of claim 1, wherein the fetch circuit generates at least one data structure specifying said row slices that produce a non-zero result when multiplied by corresponding column slices.

### Claim 14 (depends on 13)

The circuit of claim 13, wherein the fetch circuit generates a first data structure specifying addresses of a plurality of sub-matrices and a mask specifying the location of said row slices that produce a non-zero result when multiplied by corresponding column slices across within the plurality of sub-matrices.

### Claim 15 (depends on 14)

The circuit of claim 14, wherein the fetch circuit generates a second data structure storing retrieved row slices and a mask specifying the location of said row slices within the plurality of sub-matrices.

### Claim 16 (depends on 1)

The circuit of claim 1, wherein the at least one memory circuit is a static random access memory.

### Claim 17 (depends on 1)

The circuit of claim 1, wherein the determined row slices retrieved from the at least one memory circuit are loaded into a multiplier circuit.

### Claim 18 (depends on 1)

The circuit of claim 1, wherein the fetch circuit determines column slices of the second sub-matrix of data that produce a non-zero result when multiplied by a plurality of corresponding row slices of the first sub-matrix of data, and the determined column slices are retrieved from the at least one memory circuit.

### Claim 19

A method of storing and retrieving data comprising:
storing a first sub-matrix of data in at least one memory as a plurality of row slices comprising a plurality of data values;
storing a second sub-matrix of data in the at least one memory as a plurality of column slices comprising a plurality of data values;
determining row slices of the first sub-matrix of data that produce a non-zero result when multiplied by a plurality of corresponding column slices of the second sub-matrix of data; and
retrieving the determined row slices from the at least one memory.

### Claim 20

A non-transitory machine-readable medium storing a program executable by a computer for storing and retrieving data, the program comprising sets of instructions for:
storing a first sub-matrix of data in at least one memory as a plurality of row slices comprising a plurality of data values;
storing a second sub-matrix of data in the at least one memory as a plurality of column slices comprising a plurality of data values;
determining row slices of the first sub-matrix of data that produce a non-zero result when multiplied by a plurality of corresponding column slices of the second sub-matrix of data; and
retrieving the determined row slices from the at least one memory.