Method for the computation of a narrow bit width linear algebra operation
AssigneeBarcelona Supercomputing Center - Centro Nacional De SupercomputacióN (Bsc-Cns)
InventorsEnrico REGGIANI, Osman UNSAL, Adrián CRISTAL KESTELMAN
Life of this patent
Estimating the term…
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.
Claims16
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.
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.
Dependencies are inferred from the claim text.