Accelerated Quasi-Newton methods on analog crossbar hardware

Patent metadata

Field	Value
Publication number	US-11790033-B2
Application number	US-202017023318-A
Country	US
Kind code	B2
Filing date	Sep 16, 2020
Priority date	Sep 16, 2020
Publication date	Oct 17, 2023
Grant date	Oct 17, 2023

Abstract

A computer implemented method for speeding up execution of a convex optimization operation one or more quadratic complexity operations to be performed by an analog crossbar hardware switch, and identifying one or more linear complexity operations to be performed by a CPU. At least one of the quadratic complexity operations is performed by the analog crossbar hardware, and at least one of the linear complexity operations is performed by the CPU. An iteration of an approximation of a solution to the convex optimization operation is updated by the CPU.

First claim

What is claimed is:

1. A computer implemented method for speeding up execution of a convex optimization operation, the method comprising:
identifying one or more quadratic complexity operations to be performed by an analog crossbar hardware unit;
identifying one or more linear complexity operations to be performed by a CPU;
performing at least one of the quadratic complexity operations;
performing at least one of the linear complexity operations; and
updating an iteration of an approximation of a solution to the convex optimization algorithm by the CPU.

2. The method according to claim 1 , further comprising computing, by the CPU, a difference between two most recent gradients of the approximation of the solution to the convex optimization operation.

3. The method according to claim 1 , wherein the performing the at least one of the quadratic complexity operation includes mapping an initial approximation of a Hessian matrix or an inverse Hessian matrix to the analog crossbar hardware unit.

4. The method according to claim 3 , further comprising updating the initial approximation of the Hessian matrix or the inverse Hessian matrix in the analog crossbar hardware unit.

5. The method according to claim 4 , wherein the convex optimization operation comprises a Quasi-Newton algorithm, and the method further comprises configuring a plurality of analog crossbars elements of the analog crossbar hardware unit into a matrix to perform the one or more quadratic complexity operations of the Quasi-Newton algorithm.

6. The method according to claim 5 , wherein the performing the at least one quadratic complexity operation includes obtaining a search direction by performing a matrix-vector product in the analog crossbar hardware elements.

7. The method according to claim 5 , wherein the Quasi-Newton algorithm comprises a training algorithm for a Deep Neural Network.

8. The method according to claim 1 , further comprising performing a line search by the CPU.

9. A convex optimization device comprising:
an analog crossbar hardware unit comprising a plurality of memristor elements configured in a matrix to perform one or more quadratic complexity operations;
a CPU configured to perform one or more linear complexity operations; and
a memory configured to store an input and receive an output from the analog crossbar hardware unit and to store an output of the linear complexity operation executed by the CPU.

10. The device according to claim 9 , further comprising an identifier module configured to identify one or more quadratic complexity operations to be performed by the analog crossbar hardware unit, and to identify the one or more linear complexity operations to be performed by the CPU.

11. The device according to claim 10 , wherein the plurality of memristor elements comprise one or more resistor processing unit (RPU) switches.

12. The device according to claim 11 , wherein each of the RPU switches represents a value of the matrix, respectively.

13. The device according to claim 12 , wherein:
the matrix of the plurality of memristor elements includes a voltage input and a voltage output to each respective RPU switch; and
an output of each respective RPU switch comprises a current having a particular value.

14. The device according to claim 9 , wherein:
the matrix of the plurality of memristor elements of the analog crossbar hardware is configured to one of a Hessian matrix or an inverse Hessian matrix configured to perform quadratic complexity operations of a Quasi-Newton algorithm; and
the CPU is configured to perform linear complexity operations of the Quasi-Newton algorithm.

15. The device according to claim 14 , wherein an initial approximation of one of the Hessian matrix or the inverse Hessian matrix is mapped to the analog hardware crossbar unit.

16. A computer implemented accelerated Quasi-Newton method of convex optimization, the method comprising:
configuring a plurality of memristor elements of an analog crossbar hardware unit in a matrix to perform one or more quadratic complexity operations;
executing one or more linear complexity operations of the algorithm by a CPU;
storing an input and receiving an output of data from the analog crossbar hardware unit; and
storing an output of the linear complexity operation executed by the CPU.

17. The computer implemented Quasi-Newton method according to claim 16 , further comprising:
identifying one or more quadratic complexity operations to be performed by the analog crossbar hardware unit; and
identifying one or more linear complexity operations to be executed by the CPU.

18. The computer implemented Quasi-Newton method according to claim 16 , wherein the plurality of memristor elements are configured in one of a Hessian matrix or an inverse Hessian matrix to perform the quadratic complexity operations.

19. The computer implemented Quasi-Newton method according to claim 16 , further comprising mapping one of an initial Hessian matrix or an initial inverse Hessian matrix to the analog hardware crossbar unit.

20. The computer implemented Quasi-Newton method according to claim 19 , further comprising updating an initial approximation of the Hessian matrix or an initial approximation of the inverse Hessian matrix in the analog crossbar hardware unit.

Assignees

• IBM
• Univ Ramot

Inventors

• Kalantzis Vasileios
• Ubaru Shashanka
• Horesh Lior
• Avron Haim
• Onen Oguzhan Murat

Classifications

• G06N3/0499

  Feedforward networks · CPC title

• G06F17/12 Primary

  Simultaneous equations {, e.g. systems of linear equations} · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F17/16

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

• G06N3/04

  Architecture, e.g. interconnection topology · CPC title