# US 2025/0165220 A1 · Method for the computation of a narrow bit width linear algebra operation

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

- Number: US 2025/0165220 A1
- Document ID: US20250165220A1
- Status: Published application
- Kind: A1
- Application number: 18/841,898
- Filed: 2022-12-28
- Published: 2025-05-22
- Earliest claimed: 2022-02-28
- Assignees: Barcelona Supercomputing Center - Centro Nacional De SupercomputacióN (Bsc-Cns)
- Applicants: Barcelona Supercomputing Center - Centro Nacional De SupercomputacióN (Bsc-Cns)
- Inventors: Enrico REGGIANI; Osman UNSAL; Adrián CRISTAL KESTELMAN
- Web page: https://patentgrep.com/patent/US20250165220A1

## CPC

- G06F 7/544: for evaluating functions by calculation {(G06F7/4824 takes precedence)}
- G06F 17/153: {Multidimensional correlation or convolution}
- 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

The present invention relates to a method for computing a linear algebra operation of two operands or arrays comprising one or more narrow bit width elements with a digital circuit. The method uses the principle of binary segmentation to reduce the computation overhead of linear algebra operations like linear convolution and inner product of operands such as vectors with narrow bit width components. The invention is also directed to a digital circuit configured to execute the method.

## Claims

### Claim 1

A method for the computation of a linear algebra operation of two operands u, v, using a digital circuit operatively connected to an arithmetic-logic unit; wherein the method comprises, by the digital circuit, the steps of:
receiving two operands u, v, composed of m, n narrow bit width elements, respectively, such that u=[u0, . . . , um−1], v=[v0, . . . , vn−1], the elements having bit widths bu, bv, respectively,
extending the bit width of each element of the operands to a clustering bit width cw by adding zeroes to the left of the most significant bit of the element, and concatenating the elements of each operand to obtain the values U, V, of bit widths cw·m and cw·n, respectively, wherein the clustering width fulfils the condition:
cw≥max(bu,bv)
feeding the values U, V, to the arithmetic-logic unit,
receiving a result value W of bit width p from the arithmetic-logic unit, W=[W0, . . . , Wp−1],
extracting an operation result w from the result value W, wherein the operation result w comprises one or more bits of W.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the value W from the arithmetic-logic unit is obtained by multiplying, or adding the values U and V.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the clustering width fulfils the condition:
c
w
≥
b
u
+
b
v
+
log
2
(
max
⁡
(
m
,
n
)
)
.

### Claim 4 (depends on 3)

The method according to claim 3, wherein after receiving two operands u, v, the method comprises the step of reverting the order of the elements of the operand v=[v0, . . . , vn−1] to obtain an operand v′=[vn−1, . . . , v0].

### Claim 5 (depends on 3)

The method according to claim 3, wherein each of the elements of operand v equals one:
v
0
=
…
=
v
n
-
1
=
1.

### Claim 6 (depends on 1)

The method according to claim 1, wherein the operation result w comprises one or more elements, w=[w0, w1, . . . ], and wherein each element wi comprises one or more bits of W according to:
w
i
=
[
W
i
·
c
w
+
(
c
w
-
1
)
,
...
,
W
i
·
c
w
]
,
with
⁢
i
∈
{
0
,
...
,
m
+
n
-
1
}
.

### Claim 7 (depends on 4)

The method according to claim 4, wherein the operation result w comprises one or more bits of W according to:
w
=
[
W
c
w
(
m
-
1
)
+
(
c
w
-
1
)
,
...
,
W
c
w
(
m
-
1
)
]
.

### Claim 8 (depends on 1)

The method according to claim 1, wherein the clustering width fulfils the condition:
c
w
≥
b
u
+
log
2
(
m
)
.

### Claim 9 (depends on 8)

The method according to claim 8, wherein, n=1 and v=[v0]=[k].

### Claim 10 (depends on 1)

The method according to claim 1, wherein the clustering width fulfills the condition:
c
w
≥
max
⁡
(
b
u
,
b
v
)
+
1.

### Claim 11 (depends on 10)

The method according to claim 10, wherein, after the step of extending the bit width of each element, the method comprises the step of computing the 2's complement of the elements v0, . . . , vn−1 of operand v.

### Claim 12 (depends on 10)

The method according to claim 10, wherein the operation result w comprises one or more elements, w=[w0, w1, . . . ], and wherein each element wi comprises one or more bits of W according to:
w
i
=
[
W
i
·
c
w
+
(
c
w
-
1
)
,
...
,
W
i
·
c
w
]
,
with
⁢
i
∈
{
0
,
...
,
m
-
1
}
.

### Claim 13

A digital circuit operatively connected to an arithmetic-logic unit, wherein the digital circuit comprises:
a pre-processing unit, configured for:
receiving two operands u, v, composed of m, n narrow bit width elements, respectively, such that u=[u0, . . . , um−1], v=[v0, . . . , vn−1], the elements having bit widths bu, bv, respectively, and
extending two operands u, v, and to feed two values U, V to the arithmetic-logic unit, and
wherein the digital circuit further comprises a post-processing unit configured to receive a result value W from the arithmetic-logic unit and extract an operation result w;
wherein the digital post-processing unit is configured for performing the steps of:
receiving the two operands u, v;
extending the bit width of each element of the operands to a clustering bit width cw by adding zeroes to the left of the most significant bit of the element, and concatenating the elements of each operand to obtain the two values U, V, of bit widths cw·m and cw·n, respectively, wherein the clustering width fulfils the condition:
cw≥max(bu,bv)
feeding the values U, V, to the arithmetic-logic unit;
receiving the result value W of bit width p from the arithmetic-logic unit, W=[W0, . . . , Wp−1]; and
extracting the operation result w from the result value W, wherein the operation result w comprises one or more bits of the result value W.

### Claim 14 (depends on 13)

The digital circuit according to claim 13, further configured to be operatively connected to an arithmetic-logic unit of a computer, and further configured to feed or receive values U, V, W to or from the arithmetic-logic unit through a register file, a by-pass logic and/or a memory hierarchy.

### Claim 15 (depends on 13)

The digital circuit according to claim 13, wherein the pre-processing unit and the post-processing unit are implemented on a configurable logic block, CLB, wherein the CLB comprises registers and look up tables, LUT.

### Claim 16 (depends on 5)

The method according to claim 5, wherein the operation result w comprises one or more bits of W according to:
w
=
[
W
c
w
(
m
-
1
)
+
(
c
w
-
1
)
,
...
,
W
c
w
(
m
-
1
)
]
.
