US 2024/0192920 A1Published application

Special Purpose Integrated Circuits and Methods for Matrix Multiplication Using Only Addition

OwnerDaniel Cusseninventor

Life of this patent

Estimating the term…

Loading patent…

Abstract

Special purpose integrated circuits and methods for matrix multiplication are disclosed. In some embodiments, a special purpose integrated circuit is constructed to perform mathematical operations. For matrix A and matrix B, an outer product of each column i of matrix A [vector Ai] and a corresponding row i of matrix B [vector Bi], for all i, is used to calculate all the products used for determining matrices A and B. A product matrix C (where A×B=C) is assembled using additions of the elements of the calculated outer products. Each outer product of Ai and Bi may be calculated using a series of vector-scalar products. Each vector-scalar product is calculated using the vector Bi and a selected element of Ai as the scalar. Thus, calculating the vector-scalar product for all the elements of Ai will produce the outer product of Ai and Bi.

Claims22

Dependent claims

A special purpose integrated circuit for implementing vector-scalar multiplications between a vector and a scalar, the special purpose integrated circuit constructed to perform mathematical operations comprising:

a) sorting a vector V having values [v1;
:
:
:
;
vn] to create a sorted vector S having values [s1;
:
:
:
;
sn] such that s1≤s2≤_ _ _≤sn;
b) eliminating duplicate values to reduce the sorted vector S to [s1;
:
:
:
;
sm] such that s1<s2<_ _ _<sm, m being less than or equal to n;
c) creating an array of pointers [p1;
:
:
:
;
pn] where pi is a unique value j such that vi=sj;
d) calculating d1=s1 and di=si−si−1 for i=2;
3;
:
:
:m to construct a difference vector D having values [d1;
:
:
:
;
dm] of the differences between adjacent elements of the sorted vector S;
e) constructing another new vector V and setting values [v1;
:
:
:
;
vn] of the another new vector V to [d1;
:
:
:
;
dm] of the difference vector D;
f) performing steps a-e recursively until m is less than a desired threshold;
g) using Russian-Peasants multiplication of the difference vector D and a scalar c to produce a scalar product vector C having values [cd1;
:
:
:
;
cdm];
h) calculating cs1=cd1 and csi=csi-1+cdi for i=2;
3;
:
:
:
;
m using the scalar c and vector S having values [s1;
:
:
:
;
sm] to construct a product vector G having values [cs1;
:
:
:
;
csm];
j) copying the value csj from the product vector G to cvi using the array of pointers [p1;
::
:
;
pn] for a current level of recursion, a pointer pi for the current level of recursion being that j such that vi=sj for each vi, and such that cvi=csj;
and
k) repeating steps h-j for each level of recursion.

72 more elements

A method for implementing vector-scalar multiplications between a vector and a scalar, comprising:

a) sorting, by a special purpose integrated circuit constructed to perform mathematical operations, a vector V having values [v1;
:
:
:
;
vn] to create a sorted vector S having values [s1;
::
:
;
sn] such that s1<≤s2≤_ _ _≤sn;
b) eliminating, by the special purpose integrated circuit, duplicate values to reduce the sorted vector S to [s1;
:
:
:
;
sm] such that s1<s2<_ _ _<sm, m being less than or equal to n;
c) creating, by the special purpose integrated circuit, an array of pointers [p1;
:
:
:
;
pn] where pi is a unique value j such that vi=sj;
d) calculating, by the special purpose integrated circuit, d1=s1 and di=si−si−1 for i=2;
3;
:
:
:m to construct a new difference vector D having values [d1;
:
:
:
;
dm] of the differences between adjacent elements of the sorted vector S;
e) constructing, by the special purpose integrated circuit, another new vector V and setting values [v1;
:
:
:
;
vn] of the another new vector V to [d1;
:
:
:
;
dm] of the difference vector D;
f) performing steps a-e recursively until m is less than a desired threshold;
g) using Russian-Peasants multiplication, by the special purpose integrated circuit, of the difference vector D and a scalar c to produce a scalar product vector C having values [cd1;
:
:
:
;
cdm];
h) calculating, by the special purpose integrated circuit, cs1=cd1 and csi=csi−1+cdi for i=2;
3;
:
:
:
;
m using the scalar c and vector S having values [s1;
:
:
:
;
sm] to construct a product vector G having values [cs1;
:
:
:
;
csm];
j) copying, by the special purpose integrated circuit, the value csj from the product vector G to cvi using the pointer array [p1;
:
:
:
;
pn] for a current level of recursion, a pointer pi for the current level of recursion being that j such that vi=sj for each vi, and such that cvi=csj;
and
k) repeating steps h-j for each level of recursion.

72 more elements

Dependencies are inferred from the claim text.

Facts

Application: 18/520,347Filed 27 Nov 2023
Priority: 2 Dec 2022
Published: 13 Jun 2024
Term ends: Not estimatedThe source records don’t support an estimate.

Classification3 codes

G06F 7/501
Adding; Subtracting: half or full adders, i.e. basic adder cells for one denomination
G06F 7/57
Using non-contact-making devices, e.g. tube, solid state device; using unspecified devices: arithmetic logic units [ALU], i.e. arrangements or…
G06F
Computing and data processing