US 12,001,508 B1Granted

Methods for multiplying matrices using a plurality of chiplets

AssigneePersimmons, Inc.

InventorJames Michael Bodwin

Life of this patent

Estimating the term…

Loading patent…

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.

Claims20

Dependent claims

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.

74 more elements

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.

90 more elements

Dependencies are inferred from the claim text.