Hardware acceleration with preconditioners

Patent metadata

Field	Value
Publication number	US-11907715-B2
Application number	US-202117556252-A
Country	US
Kind code	B2
Filing date	Dec 20, 2021
Priority date	Dec 20, 2021
Publication date	Feb 20, 2024
Grant date	Feb 20, 2024

Abstract

Techniques are provided to implement hardware accelerated application of preconditioners to solve linear equations. For example, a system includes a processor, and a resistive processing unit coupled to the processor. The resistive processing unit includes an array of cells which include respective resistive devices, wherein at least a portion of the resistive devices are tunable to encode entries of a preconditioning matrix which is storable in the array of cells. When the preconditioning matrix is stored in the array of cells, the processor is configured to apply the preconditioning matrix to a plurality of residual vectors by executing a process which includes performing analog matrix-vector multiplication operations on the preconditioning matrix and respective ones of the plurality of residual vectors to generate a plurality of output vectors used in one or more subsequent operations.

First claim

What is claimed is:

1. A system, comprising:
a processor; and
a resistive processing unit coupled to the processor, the resistive processing unit comprising an array of cells, the cells respectively comprising resistive devices, a least a portion of the resistive devices being tunable to encode entries of a preconditioning matrix storable in the array of cells;
wherein, when the preconditioning matrix is stored in the array of cells, the processor is configured to apply the preconditioning matrix to a plurality of residual vectors by executing a process which comprises performing analog matrix-vector multiplication operations on the preconditioning matrix and respective ones of the plurality of residual vectors to generate a plurality of output vectors used in one or more subsequent operations,
wherein in a first iteration of at least a portion of the process, the processor is configured to:
input a first residual vector of the plurality of residual vectors to the array of cells;
utilize the resistive processing unit to perform a first matrix-vector multiplication operation by multiplying the first residual vector with the preconditioning matrix in the array of cells to generate a first output vector of the plurality of output vectors;
combine a given matrix with the first output vector to generate a first augmented matrix which is output from the array of cells;
perform a second matrix-vector multiplication operation; and
compute a second residual vector of the plurality of residual vectors based at least in part on the product of the second matrix-vector multiplication operation.

2. The system of claim 1 , wherein the first output vector comprises a column vector.

3. The system of claim 1 , wherein in executing the process, the processor is further configured to:
compute a conjugate transpose of the first augmented matrix; and
compute a weight vector based at least in part on the conjugate transpose.

4. The system of claim 3 , wherein in executing the process, the processor is configured to compute a matrix-vector product of the first augmented matrix and the weight vector, wherein the matrix-vector product comprises one of a plurality of iterative solutions to a linear system.

5. The system of claim 1 , wherein in executing the process, the processor is configured to:
estimate an inverse matrix of a designated matrix; and
store the estimated inverse matrix as the preconditioning matrix in the array of cells.

6. The system of claim 5 , wherein:
the plurality of output vectors are used in the one or more subsequent operations to return a plurality of iterative solutions to a linear system; and
the linear system corresponds to the equation Ax=b, wherein A is the designated matrix, b is a right-hand side vector, and x is a variable vector corresponding to a given one of the plurality of iterative solutions.

7. The system of claim 1 , wherein
the second matrix-vector multiplication operation comprises multiplying the first augmented matrix with a first weight vector.

8. The system of claim 1 , wherein in a second iteration of at least a portion of the process, the processor is configured to:
input the second residual vector to the array of cells;
utilize the resistive processing unit to perform a third matrix-vector multiplication operation by multiplying the second residual vector with the preconditioning matrix in the array of cells to generate a second output vector of the plurality of output vectors;
combine the first augmented matrix with the second output vector to generate a second augmented matrix which is output from the array of cells;
perform a fourth matrix-vector multiplication operation by multiplying the second augmented matrix with a second weight vector; and
compute a third residual vector of the plurality of residual vectors based at least in part on the product of the fourth matrix-vector multiplication operation.

9. The system of claim 8 , wherein:
the plurality of output vectors are used in the one or more subsequent operations to return a plurality of iterative solutions to a linear system;
the linear system corresponds to the equation Ax=b, wherein A is a left-hand side matrix, b is a right-hand side vector, and x is a variable vector corresponding to a given one of the plurality of iterative solutions; and
the first, second and third residual vectors correspond to the equation r=b−Ax.

10. The system of claim 8 , wherein upon completing a plurality of iterations of the process, the processor is configured to one of:
determine whether the plurality of iterations corresponds to a threshold number of iterations; and
determine whether a last residual vector computed from a last completed iteration of the plurality of iterations satisfies a given convergence criterion.

11. A computer program product, comprising:
one or more computer readable storage media, and program instructions collectively stored on the one or more computer readable storage media, the program instructions comprising:
program instructions to receive a preconditioning matrix from an application;
program instructions to store the preconditioning matrix in an array of cells of a resistive processing unit; and
program instructions to execute a process to apply the preconditioning matrix to a plurality of residual vectors, wherein the program instructions to execute the process comprise program instructions to perform analog matrix-vector multiplication operations on the preconditioning matrix and respective ones of the plurality of residual vectors to generate a plurality of output vectors used in one or more subsequent operations;
wherein the program instructions to execute the process further comprise program instructions to perform a first iteration, which comprises:
inputting a first residual vector of the plurality of residual vectors to the array of cells;
utilizing the resistive processing unit to perform a first matrix-vector multiplication operation by multiplying the first residual vector with the preconditioning matrix in the array of cells to generate a first output vector of the plurality of output vectors;
combining a given matrix with the first output vector to generate a first augmented matrix which is output from the array of cells;
performing a second matrix-vector multiplication operation; and
computing a second residual vector of the plurality of residual vectors based at least in part on the product of the second matrix-vector multiplication operation.

12. The computer program product of claim 11 , wherein the first output vector comprises a column vector.

13. The computer program product of claim 11 , wherein the program instructions to execute the process further comprise:
program instructions to compute a conjugate transpose of the first augmented matrix; and
program instructions to compute a weight vector based at least in part on the conjugate transpose.

14. The computer program product of claim 13 , wherein the program instructions to execute the process further comprise program instructions to compute a matrix-vector product of the first augmented matrix and the weight vector, wherein the matrix-vector product comprises one of a plurality of iterative solutions to a linear system.

15. The computer program product of claim 11 , wherein the
the second matrix-vector multiplication operation comprises multiplying the first augmented matrix with a first weight vector.

16. The computer program product of claim 11 , wherein the program instructions to execute the process further comprise program instructions to perform at least a secon

Assignees

• IBM

Inventors

• Kalantzis Vasileios
• Horesh Lior
• Ubaru Shashanka

Classifications

• G06F9/30036 Primary

  Instructions to perform operations on packed data, e.g. vector, tile or matrix operations · CPC title

• G06F9/3001

  Arithmetic instructions · CPC title

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title