Adiabatic annealing scheme and system for edge computing

Patent metadata

Field	Value
Publication number	US-11650751-B2
Application number	US-201916368981-A
Country	US
Kind code	B2
Filing date	Mar 29, 2019
Priority date	Dec 18, 2018
Publication date	May 16, 2023
Grant date	May 16, 2023

Abstract

A method for determining a solution to a constrained optimization problem includes programming a weights matrix of a Hopfield network with a first encoded matrix representation of an initial constrained optimization problem. The method also includes employing the Hopfield network to determine a solution to the initial constrained optimization problem. Additionally, the method includes encoding a plurality of constrained optimization problems associated with a target constrained optimization problem into a plurality of encoded matrix representations each of which are a combination of the first and the second encoded matrix representations. The plurality of encoded matrix representations increases in convergence to the second encoded matrix representation of the target constrained optimization problem sequentially. The method further includes re-programming the weights matrix of the Hopfield network in an iterative manner with the plurality of encoded matrix representations.

First claim

The invention claimed is:

1. An accelerator device, comprising:
a first memristor crossbar array having a plurality of non-volatile memory elements, each non-volatile memory element comprising a two-terminal memory element to generate a solution to an encoded matrix representation of a constrained optimization problem;
a filtering unit to receive and filter solutions generated from the plurality of non-volatile memory elements; and
a programming unit comprising dedicated hardware to write into the plurality of non-volatile memory elements an encoded matrix representation of a plurality of encoded matrix representations associated with the constrained optimization problem, in an iterative manner, upon each re-programming of the first memristor crossbar array,
wherein the plurality of encoded matrix representations are ordered to increase in convergence to the encoded matrix representation of the constrained optimization problem,
wherein the plurality of encoded matrix representations are each unique Hopfield network Hamiltonian functions associated with the constrained optimization problem, and
wherein stochastic noise is injected during employment of a Hopfield network associated with the Hopfield network Hamiltonian functions that comprises a current pulse between 50 and 150 μA which is induced for about 5 μs to about 50 μs.

2. The accelerator device of claim 1 , wherein the plurality of encoded matrix representations comprise a Hopfield network Hamiltonian function associated with the constrained optimization problem and the plurality of Hopfield network Hamiltonian functions that are each fractions of the Hopfield network Hamiltonian function associated with the constrained optimization problem.

3. The accelerator device of claim 1 , wherein the plurality of non-volatile memory elements comprise at least one of nonlinear resistors, phase change memory, and spin torque-transfer random access memory.

4. The accelerator device of claim 1 , wherein an initial encoded matrix representation of the plurality of encoded matrix representations associated with the constrained optimization problem is associated with an energy function having a single local minimum.

5. The accelerator device of claim 1 , further comprising a solutions memory to store filtered solutions generated by the filtering unit.

6. The accelerator device of claim 5 , further comprising a comparator to compare the filtered solutions stored in the solutions memory with a solution previously filtered from the filtering unit.

7. The accelerator device of claim 1 , further comprising:
a solutions memory; and
a second memristor crossbar array coupled to the filtering unit and the solutions memory.

8. The accelerator device of claim 7 , further comprising a weighting amplifier coupled to the first memristor crossbar array and the second memristor crossbar array, the weighting amplifier to generate a weighted sum of the solution received from the first memristor crossbar array and the second memristor crossbar array.

9. The accelerator device of claim 8 , wherein the solutions memory to store solutions generated by the filtering unit and transmission lines that are coupled to the second memristor crossbar array wherein the transmission lines are to send the solutions generated by the filtering unit to the second memristor crossbar array.

10. The accelerator device of claim 1 , wherein the programming unit comprises a digital-to-analog converter (DAC) to convert a digital representation of the plurality of encoded matrix representations into analog signals and an analog-to-digital converter (ADC) to convert an analog representation of the solution to the constrained optimization problem into digital signals.

11. The accelerator device of claim 1 , wherein the programming unit further comprises dedicated hardware to write into the plurality of non-volatile memory elements a target constrained optimization problem, the target constrained optimization problem being unrelated to the constrained optimization problem.

12. A non-transitory computer readable medium comprising computer executable instructions stored thereon that, when executed by one or more processing units, causes the one or more processing units to:
program a weights matrix of a Hopfield network with a first encoded matrix representation of an initial constrained optimization problem;
employ the Hopfield network to determine a solution to the initial constrained optimization problem;
encode a target constrained optimization problem into a second encoded matrix representation, the target constrained optimization problem being unrelated to the initial constrained optimization problem;
encode a plurality of constrained optimization problems into a plurality of encoded matrix representations, each encoded matrix representation being a combination of the first encoded matrix representation and the second encoded matrix representation, the plurality of encoded matrix representations sequentially increasing in convergence to the second encoded matrix representation of the target constrained optimization problem; and
re-program the weights matrix of the Hopfield network in an iterative manner with the plurality of encoded matrix representations, comprising:
re-program the weights matrix of the Hopfield network with one of the plurality of encoded matrix representations in a sequential manner;
inject stochastic noise that comprises a current pulse between 50 and 150 μA which is induced for about 5 μs to about 50 μs; and
employ the Hopfield network to determine a solution to the encoded matrix representation presently programmed in the Hopfield network using the stochastic noise.

13. The non-transitory computer readable medium of claim 12 , wherein the computer executable instructions, when executed by one or more processing units, further causes the one or more processing units to:
bit slice the plurality of encoded matrix representations.

14. The non-transitory computer readable medium of claim 12 , wherein the stochastic noise is injected during employment of the Hopfield network to determine the solution to the encoded matrix representation presently programmed in the Hopfield network.

15. The non-transitory computer readable medium of claim 14 , wherein injecting the stochastic noise during employment of the Hopfield network comprises injecting a first level of stochastic noise followed by injecting a second level of stochastic noise that is lesser in degree than the first level of stochastic noise.

16. The non-transitory computer readable medium of claim 12 , wherein the target constrained optimization problem is a non-deterministic polynomial-time hardness class of decision problems.

17. A method, comprising:
encoding, by an accelerator device, an initial constrained optimization problem into a first encoded matrix representation;
encoding a target constrained optimization problem into a second encoded matrix representation;
generating a weighted sum of the first encoded matrix representation and the second encoded matrix representation;
programming a weights matrix of a Hopfield network with the weighted sum of the first encoded matrix representation and the second encoded matrix representation; and
employing, by the accelerator device, the Hopfield network to determine a solution to the target constrained optimization problem, wherein stochastic noise is injected while employing the Hopfield network that comprises a current pulse between 50 and 150 μA which is induced for about 5 μs to about 50 μs.

18. The method of claim

Assignees

• Hewlett Packard Entpr Dev Lp

Inventors

• Kumar Suhas
• Vaerenbergh Thomas Van
• Strachan John Paul

Classifications

• G06N3/063 Primary

  using electronic means · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06F3/0655 Primary

  Vertical data movement, i.e. input-output transfer; data movement between one or more hosts and one or more storage devices · CPC title

• G06F3/0604

  Improving or facilitating administration, e.g. storage management · CPC title

• G06N3/044

  Recurrent networks, e.g. Hopfield networks · CPC title