Constant depth, near constant depth, and subcubic size threshold circuits for linear algebraic calculations

Patent metadata

Field	Value
Publication number	US-10445065-B2
Application number	US-201715699077-A
Country	US
Kind code	B2
Filing date	Sep 8, 2017
Priority date	Sep 8, 2017
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

Abstract

A method of increasing an efficiency at which a plurality of threshold gates arranged as neuromorphic hardware is able to perform a linear algebraic calculation having a dominant size of N. The computer-implemented method includes using the plurality of threshold gates to perform the linear algebraic calculation in a manner that is simultaneously efficient and at a near constant depth. “Efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm. The naïve algorithm is a straightforward algorithm for solving the linear algebraic calculation. “Constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the linear algebraic calculation. The near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.

First claim

What is claimed is:

1. A method of increasing an efficiency at which a plurality of threshold gates arranged as neuromorphic hardware is able to perform a linear algebraic calculation having a dominant size of N, the method comprising:
using the plurality of threshold gates to perform the linear algebraic calculation in a manner that is simultaneously efficient and at a near constant depth, wherein “efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm, wherein the naïve algorithm is a straightforward algorithm for solving the linear algebraic calculation, wherein “constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the linear algebraic calculation, and wherein the near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.

2. The method of claim 1 wherein the linear algebraic calculation comprises matrix multiplication of two square matrices of size N×N.

3. The method of claim 2 wherein the calculation algorithm has a first number of operations of O(N 2+δ ) compared to the straightforward algorithm having a second number of operations of O(N 3 ), wherein δ comprises a number that is greater than or equal to zero but less than one.

4. The method of claim 3 further comprising:
converting an initial depth of the linear algebraic calculation, wherein the initial depth is log 2 N, to the near constant depth.

5. The method of claim 4 wherein the near constant depth is the constant depth, and wherein converting comprises:
setting the constant depth to a value of at most 2d+5 that determines whether trace (A 3 )≥τ using Õ(dN ω+cγ d ) of the plurality of threshold gates, where c>0 and γ<1 are constants with respect to N and d that depend on parameters of the calculation algorithm, wherein d is a constant, and wherein ω is between exactly 2 and less than 3.

6. The method of claim 4 further comprising:
dedicating a sub-plurality of the plurality of threshold gates to communicate non-binary numbers that require increasing precision to define during subsequent stages of the calculation algorithm.

7. The method of claim 1 wherein the linear algebraic calculation comprises a matrix inversion.

8. The method of claim 1 wherein the linear algebraic calculation comprises multiplying at least two matrices in order to count triangles in a graph G.

9. A neuromorphic computer comprising:
a plurality of threshold gates or spiking neurons configured to compute a specific linear algebraic calculation having a dominant size of N in a manner that is simultaneously efficient and at a near constant depth, wherein “efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm, wherein the naïve algorithm is a straightforward algorithm for solving the specific linear algebraic calculation, wherein “constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the specific linear algebraic calculation, and wherein the near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.

10. The neuromorphic computer of claim 9 wherein the specific linear algebraic calculation comprises matrix multiplication of two square matrices of size N×N.

11. The neuromorphic computer of claim 10 wherein the calculation algorithm has a first number of operations of O(N 2+δ ) compared to the straightforward algorithm having a second number of operations of O(N 3 ), wherein δ comprises a number that is greater than or equal to zero but less than one.

12. The neuromorphic computer of claim 11 wherein the plurality of threshold gates or spiking neurons are further configured to convert an initial depth of the specific linear algebraic calculation to the near constant depth, wherein the initial depth is log 2 N.

13. The neuromorphic computer of claim 12 wherein the near constant depth is the constant depth, and wherein in being configured to convert, the plurality of threshold gates or spiking neurons are further configured to set the constant depth to a value of at most 2d+5 that determines whether trace (A 3 )≥τ using Õ(dN ω+cγ d ) of the plurality of threshold gates or spiking neurons, where c>0 and γ≤1 are constants with respect to N and d that depend on parameters of the calculation algorithm, wherein d is a constant, and wherein ω is between exactly 2 and less than 3.

14. The neuromorphic computer of claim 12 wherein a sub-plurality of the plurality of threshold gates or spiking neurons are dedicated to communicate non-binary numbers that require increasing precision to define during subsequent stages of the calculation algorithm.

15. The neuromorphic computer of claim 9 wherein the specific linear algebraic calculation comprises a matrix inversion.

16. The neuromorphic computer of claim 9 wherein the specific linear algebraic calculation comprises multiplying at least two matrices in order to count triangles in a graph G.

17. A method of manufacturing a neuromorphic computer tailored to perform a specific linear algebraic calculation, the method comprising:
manufacturing a plurality of threshold gates or spiking neurons; and
arranging the plurality of threshold gates or spiking neurons to compute the linear algebraic calculation having a dominant size N in a manner that is simultaneously efficient and at a near constant depth, wherein “efficient” is defined as a calculation algorithm that uses fewer of the plurality of threshold gates than a naïve algorithm, wherein the naïve algorithm is a straightforward algorithm for solving the linear algebraic calculation, wherein “constant depth” is defined as an algorithm that has an execution time that is independent of a size of an input to the linear algebraic calculation, and wherein the near constant depth comprises a computing depth equal to or between O(log(log(N)) and the constant depth.

18. The method of claim 17 wherein the specific linear algebraic calculation comprises matrix multiplication of two square matrices of size N×N.

19. The method of claim 18 further comprising:
further arranging the plurality of threshold gates or spiking neurons to convert an initial depth of the specific linear algebraic calculation to the near constant depth, wherein the initial depth is log 2 N.

20. The method of claim 19 further comprising:
further arranging the plurality of threshold gates or spiking neurons to dedicate a sub-plurality of the plurality of threshold gates or spiking neurons to communicate non-binary numbers that require increasing precision to define during subsequent stages of the calculation algorithm.

Assignees

• Nat Tech & Eng Solutions Sandia Llc

Inventors

• Aimone James Bradley
• Parekh Ojas D
• Phillips Cynthia A

Classifications

• G06N3/045

  Combinations of networks · CPC title

• G06N3/065

  Analogue means · CPC title

• G06N3/049

  Temporal neural networks, e.g. delay elements, oscillating neurons or pulsed inputs · CPC title

• G06F7/4833 Primary

  Logarithmic number system · CPC title

• G06N3/063

  using electronic means · CPC title