Gaussian elimination via a vector matrix multiplication accelerator

Patent metadata

Field	Value
Publication number	US-10489482-B1
Application number	US-201815995505-A
Country	US
Kind code	B1
Filing date	Jun 1, 2018
Priority date	Jun 1, 2018
Publication date	Nov 26, 2019
Grant date	Nov 26, 2019

Abstract

Methods for solving systems of linear equations via utilization of a vector matrix multiplication accelerator are provided. In one aspect, a method includes receiving, from a controller and by the vector matrix multiplication accelerator, an augmented coefficient matrix. The method also comprises implementing Gaussian Elimination using the vector matrix multiplication accelerator by: monitoring, by a register in at least one swap operation, a row order of the augmented coefficient matrix when a first row is swapped with a second row of the augmented coefficient matrix, delivering, by the controller in at least one multiply operation, an analog voltage to a desired row of the augmented coefficient matrix to produce a multiplication result vector, and adding, in at least one add operation, the first row to another desired row of the augmented coefficient matrix to produce an add result vector. Systems and circuits are also provided.

First claim

What is claimed is:

1. A method for solving systems of linear equations via utilization of a vector matrix multiplication accelerator, the method comprising:
receiving, from a controller and by the vector matrix multiplication accelerator, an augmented coefficient matrix comprising n rows by m columns; and
implementing Gaussian Elimination using the vector matrix multiplication accelerator by:
monitoring, by a register in at least one swap operation, a row order of the augmented coefficient matrix when a first row of the augmented coefficient matrix is swapped with a second row of the augmented coefficient matrix;
delivering, by the controller in at least one multiply operation, an analog voltage corresponding to a non-zero number to a desired row of the augmented coefficient matrix to produce a multiplication result vector; and
adding, in at least one add operation, the first row of the augmented coefficient matrix to another desired row of the augmented coefficient matrix to produce an add result vector.

2. The method of claim 1 , wherein, in the at least one add operation, the first row of the augmented coefficient matrix and the desired row of the augmented coefficient matrix are stored in a buffer.

3. The method of claim 2 , wherein, in the at least one add operation, the first row of the augmented coefficient matrix is another multiplication result vector.

4. The method of claim 1 , wherein, in the at least one add operation, the add result vector is stored in a buffer.

5. The method of claim 1 , wherein, in the at least one add operation, the add result vector is stored in the vector matrix multiplication accelerator.

6. The method of claim 1 , wherein the at least one multiply operation, further includes monitoring, by the controller, a scaling of the multiplication result vector.

7. The method of claim 1 , wherein the vector matrix multiplication accelerator comprises an analog resistive memory crossbar array.

8. The method of claim 1 , wherein implementing Gaussian elimination comprises determining a final matrix in row echelon form.

9. The method of claim 8 , wherein the final matrix is stored in a buffer.

10. The method of claim 8 , wherein the final matrix is stored in the vector matrix multiplication accelerator.

11. A system for solving systems of linear equations via utilization of an analog resistive memory crossbar array, the system comprising:
a memory comprising instructions; and
one or more processors configured to execute the instructions to:
receive, from the one or more processors and by the analog resistive memory crossbar array, an augmented coefficient matrix comprising n rows by m columns; and
implement Gaussian Elimination on the augmented coefficient matrix using the analog resistive memory crossbar array by:
monitoring, by a register in at least one swap operation, a row order of the augmented coefficient matrix when a first row of the augmented coefficient matrix is swapped with a second row of the augmented coefficient matrix;
delivering, by the one or more processors in at least one multiply operation, an analog voltage corresponding to a non-zero number to a desired row of the augmented coefficient matrix to produce a multiplication result vector, and monitoring, by the one or more processors, a scaling of the multiplication result vector;
adding, in at least one add operation, the first row of the augmented coefficient matrix to another desired row of the augmented coefficient matrix to produce an add result vector; and
determining a final matrix in row echelon form.

12. The system of claim 11 , wherein, in the at least one add operation, the first row of the augmented coefficient matrix and the multiplication result vector are stored in a buffer.

13. The system of claim 12 , wherein, in the at least one add operation, the first row of the augmented coefficient matrix is another multiplication result vector.

14. The system of claim 11 , wherein, in the at least one add operation, the add result vector is stored in a buffer.

15. The system of claim 11 , wherein, in the at least one add operation, the add result vector is stored in the analog resistive memory crossbar array.

16. The system of claim 11 , wherein the final matrix is stored in a buffer.

17. The system of claim 11 , wherein the final matrix is stored in the analog resistive memory crossbar array.

18. A circuit, comprising:
a controller;
an analog resistive memory crossbar array configured to receive, from the controller, an augmented coefficient matrix comprising n rows by m columns,
the controller configured to deliver, in at least one multiply operation of Gaussian Elimination, an analog voltage corresponding to a non-zero number to a desired row of the augmented coefficient matrix to produce a multiplication result vector; and
a register configured to monitor, in at least one swap operation of Gaussian Elimination, a row order of the augmented coefficient matrix when a first row of the augmented coefficient matrix is swapped with a second row of the augmented coefficient matrix,
wherein the controller is configured to add, via the analog resistive memory crossbar array, in at least one add operation of Gaussian Elimination, the first row of the augmented coefficient matrix to another desired row of the augmented coefficient matrix to produce an add result vector.

19. The circuit of claim 18 , further including a buffer configured to store, in the at least one add operation of Gaussian Elimination, the add result vector.

20. The circuit of claim 18 , further including at least one analog-to-digital converter configured to generate a digital multiplication result vector based on the multiplication result vector via at least one sample-and-hold circuit.

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Graves Catherine
• Strachan John Paul

Classifications

• G06G7/32

  for solving of equations {or inequations; for matrices} · CPC title

• G06G7/16

  for multiplication or division {(G06G7/19 and G06G7/24 take precedence; measuring electric power G01R21/00)} · CPC title

• G06F17/12 Primary

  Simultaneous equations {, e.g. systems of linear equations} · 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