# US 12,001,508 B1 · Methods for multiplying matrices using a plurality of chiplets

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

- Number: US 12,001,508 B1
- Document ID: US12001508B1
- Status: Granted
- Kind: B1
- Application number: 18/492,016
- Filed: 2023-10-23
- Granted: 2024-06-04
- Earliest claimed: 2023-10-23
- Assignees: Persimmons, Inc.
- Applicants: Persimmons, Inc.
- Inventors: James Michael Bodwin
- Web page: https://patentgrep.com/patent/US12001508B1

## CPC

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

## Abstract

A plurality of chiplets may be used to multiply two matrices A and B. Matrix A may be decomposed into horizontal stripes and matrix B may be decomposed into vertical stripes. Each of the horizontal stripes may be multiplied by each of the vertical stripes to form the output matrix C. Specifically, horizontal stripes may be stored in a stationary, distributed manner across the chiplets, while the vertical stripes (or sub-vertical stripes) may be passed between respective pairs of the chiplets until each of the vertical stripes (or sub-vertical stripes) of matrix B has been received and processed by each of the chiplets. The vertical stripes may be passed along one or more paths that interconnect the chiplets. Similar techniques can be applied to an arrangement in which the vertical stripes are stationary and the horizontal stripes (or sub-horizontal stripes) are passed between respective pairs of the chiplets.

## Claims

### Claim 1

A method, comprising:
partitioning a first matrix, A, with size m rows by n columns into a plurality of input horizontal stripes, A1, . . . , AS, such that
A
=
[
A
1
⋮
A
s
]
,
each of the input horizontal stripes, Ai, for i=1, . . . , s, having size h rows by n columns, with h being is less than m;
partitioning each of the input horizontal stripes, Ai, for i=1, . . . , s into a plurality of sub-horizontal stripes {Ei,k}|i=1 . . . s,k=1 . . . u, such that
Ai=[Ei,1 . . . Ei,u],
each of the sub-horizontal stripes, Ei,k, having size h rows by x columns, with x being less than n;
partitioning a second matrix, B, with size n rows by p columns into a plurality of vertical stripes, B1, . . . , Bt, such that
B=[B1 . . . Bt],
each of the vertical stripes, Bj, for j=1, . . . , t with size n rows by w columns, with w being is less than p;
partitioning each of the vertical stripes, Bj, for j=1, . . . , t into a plurality of sub-vertical stripes {Fk,j}|k=1 . . . u,j=1 . . . t, such that
B
j
=
[
F
1
,
j
⋮
F
u
,
j
]
,
each of the sub-vertical stripes, Fk,j, having size x rows by w columns;
storing the input horizontal stripes A1, . . . , Ar across a plurality of chiplets, L1, . . . , Lr, such that horizontal stripe Ad is stored at chiplet Ld, for d=1 . . . r, wherein each of the chiplets comprises a systolic array;
communicating each of the sub-vertical stripes {Fk,j}|k=1 . . . u,j=1 . . . t between respective pairs of the chiplets from the plurality of chiplets until each of the chiplets from the plurality of chiplets has received each of the sub-vertical stripes {Fk,j}|k=1 . . . u,j=1 . . . t; and
at the chiplet, Ld, for d=1 . . . r:
multiplying, by the systolic array, the sub-horizontal stripe Ed,k with the sub-vertical stripe Fk,j for j=1 . . . t and k=1 . . . u so as to form a plurality of products Ed,kFk,j for j=1 . . . t and k=1 . . . u;
summing, by the systolic array, the plurality of products in accordance with
A
d
⁢
B
j
=
∑
k
=
1
u
⁢
E
d
,
k
⁢
F
k
,
j
,
for
⁢
j
=
1
⁢
…
⁢
t
;
and
forming an output horizontal stripe, Cd, in accordance with
Cd=[AdB1 . . . AdBt],
each of the output horizontal stripes, Cd, having size h rows by p columns.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of chiplets is logically divided into one or more chiplet groups which form a partition of the plurality of chiplets, wherein respective chiplets within each of the chiplet groups are interconnected to one another via one or more closed paths, and wherein communicating each of the sub-vertical stripes {Fk,j}|k=1 . . . u,j=1 . . . t between respective pairs of the chiplets comprises passing the sub-vertical stripes {Fk,j}|k=1 . . . u,j=1 . . . t through each of the one or more closed paths.

### Claim 3 (depends on 2)

The method of claim 2, wherein at least one of the one or more closed paths contains at least two copies of each of the sub-vertical stripes {Fk,j}|k=1 . . . u,J=1 . . . t.

### Claim 4 (depends on 2)

The method of claim 2, wherein sub-vertical stripes from a first one of the vertical stripes are processed on the plurality of chiplets in a first time period, and sub-vertical stripes from a second one of the vertical stripes are processed on the plurality of chiplets in a second time period, the first time period being disjoint from the second time period.

### Claim 5 (depends on 2)

The method of claim 2, wherein sub-vertical stripes from a first one of the vertical stripes are processed on the plurality of chiplets in a first time period, and sub-vertical stripes from a second one of the vertical stripes are processed on the plurality of chiplets in a second time period, the first time period being identical to the second time period.

### Claim 6 (depends on 2)

The method of claim 2, wherein each of the one or more closed paths traverses each of the chiplets at most one time.

### Claim 7 (depends on 6)

The method of claim 6, each of the one or more closed paths is bi-directional.

### Claim 8 (depends on 1)

The method of claim 1, wherein a time at which a first one of the sub-vertical stripes is communicated between a first pair of the chiplets is independent from a time at which a second one of the sub-vertical stripes is communicated between a second pair of the chiplets.

### Claim 9 (depends on 1)

The method of claim 1, further comprising for d=1 . . . r, transmitting, by the chiplet, Ld, the output horizontal stripe, Cd to a client device.

### Claim 10 (depends on 1)

The method of claim 1, further comprising for d=1 . . . r, repurposing the output horizontal stripe, Cd as a further input horizontal stripe to a matrix multiplication operation.

### Claim 11

A method, comprising:
partitioning a first matrix, A, with size m rows by n columns into a plurality of input horizontal stripes, A1, . . . , AS, such that
A
=
[
A
1
⋮
A
s
]
,
each of the input horizontal stripes, Ai, having size h rows by n columns, with h being is less than m;
partitioning each of the input horizontal stripes, A1, . . . , AS into a plurality of sub-horizontal stripes {Ei,k}|i=1 . . . s,k=1 . . . u, such that
A1=[Ei,1 . . . Ei,u],
each of the sub-horizontal stripes, Ei,k, having size h rows by x columns, with x being less than n;
partitioning a second matrix, B, with size n rows by p columns into a plurality of vertical stripes, B1, . . . , Bt, such that
B=[B1 . . . Bt],
each of the vertical stripes, Bj, with size n rows by w columns, with w being is less than p;
partitioning each of the vertical stripes, B1, . . . , Bt into a plurality of sub-vertical stripes {Fk,j}|k=1 . . . u,j=1 . . . t, such that
B
j
=
[
F
1
,
j
⋮
F
u
,
j
]
,
each of the sub-vertical stripes, Fk,j, having size x rows by w columns;
storing the input vertical stripes B1, . . . , B, across a plurality of chiplets, {Ld}|d=1 . . . r, such that input vertical stripe Bd is stored at the chiplet Ld, for d=1 . . . r, wherein each of the chiplets comprises a systolic array;
communicating each of the sub-horizontal stripes {Ei,k}|i=1 . . . s,k= . . . u between respective pairs of the chiplets from the plurality of chiplets until each of the chiplets from the plurality of chiplets has received each of the sub-horizontal stripes {Ei,k}|i=1 . . . s,k=1 . . . 1; and
at the chiplet, Ld, for d=1 . . . r:
multiplying, by the systolic array, the sub-horizontal stripe E1,k with the sub-vertical stripe Fk,d for i=1 . . . s and k=1 . . . u so as to form a plurality of products E1,kFk,d for i=1 . . . sand k=1 . . . u;
summing, by the systolic array, the plurality of products in accordance with
A
i
⁢
B
d
=
∑
k
=
1
u
⁢
E
i
,
k
⁢
F
k
,
d
,
for
⁢
i
=
1
⁢
…
⁢
s
;
and
forming an output vertical stripe, γd, wherein
γ
d
=
[
A
1
⁢
B
d
⋮
A
s
⁢
B
d
]
,
each of the output vertical stripes, γd, having size m rows by w columns.

### Claim 12 (depends on 11)

The method of claim 11, wherein the plurality of chiplets is logically divided into one or more chiplet groups which form a partition of the plurality of chiplets, wherein respective chiplets within each of the chiplet groups are interconnected to one another via one or more closed paths, and wherein communicating each of the sub-horizontal stripes {Ei,k}|i=1 . . . s,k=1 . . . u between respective pairs of the chiplets comprises passing the sub-horizontal stripes {Ei,k}|i=1 . . . s,k=1 . . . u through each of the one or more closed paths.

### Claim 13 (depends on 12)

The method of claim 12, wherein at least one of the one or more closed paths contains at least two copies of each of the sub-horizontal stripes {Ei,k}|i=1 . . . s,k=1 . . . u.

### Claim 14 (depends on 12)

The method of claim 12, wherein sub-horizontal stripes from a first one of the horizontal stripes are processed on the plurality of chiplets in a first time period, and sub-horizontal stripes from a second one of the horizontal stripes are processed on the plurality of chiplets in a second time period, the first time period being disjoint from the second time period.

### Claim 15 (depends on 12)

The method of claim 12, wherein sub-horizontal stripes from a first one of the horizontal stripes are processed on the plurality of chiplets in a first time period, and sub-horizontal stripes from a second one of the horizontal stripes are processed on the plurality of chiplets in a second time period, the first time period being identical to the second time period.

### Claim 16 (depends on 12)

The method of claim 12, wherein each of the one or more closed paths traverses each of the chiplets at most one time.

### Claim 17 (depends on 16)

The method of claim 16, each of the one or more closed paths is bi-directional.

### Claim 18 (depends on 11)

The method of claim 11, wherein a time at which a first one of the sub-horizontal stripes is communicated between a first pair of the chiplets is independent from a time at which a second one of the sub-horizontal stripes is communicated between a second pair of the chiplets.

### Claim 19 (depends on 11)

The method of claim 11, further comprising for d=1 . . . r, transmitting, by the chiplet, Ld, the output vertical stripe, γd to a client device.

### Claim 20 (depends on 11)

The method of claim 11, further comprising for d=1 . . . r, repurposing the output vertical stripe, γd as a further input vertical stripe to a matrix multiplication operation.