Devices and methods for increasing the speed and efficiency at which a computer is capable of modeling a plurality of random walkers using a density method

Patent metadata

Field	Value
Publication number	US-11409922-B2
Application number	US-201816020627-A
Country	US
Kind code	B2
Filing date	Jun 27, 2018
Priority date	Jun 27, 2018
Publication date	Aug 9, 2022
Grant date	Aug 9, 2022

Abstract

A method for increasing a speed or energy efficiency at which a computer is capable of modeling a plurality of random walkers. The method includes defining a virtual space in which a plurality of virtual random walkers will move among different locations in the virtual space, wherein the virtual space comprises a plurality of vertices and wherein the different locations are ones of the plurality of vertices. A corresponding set of neurons in a spiking neural network is assigned to a corresponding vertex such that there is a correspondence between sets of neurons and the plurality of vertices, wherein a spiking neural network comprising a plurality of sets of spiking neurons is established. A virtual random walk of the plurality of virtual random walkers is executed using the spiking neural network, wherein executing includes tracking how many virtual random walkers are at each vertex at a given time increment.

First claim

What is claimed is:

1. A method for modeling random walkers in a circuit, the method comprising:
defining a virtual space in which a plurality of virtual random walkers will move among different locations in the virtual space, wherein the virtual space comprises a plurality of vertices and wherein the different locations are ones of the plurality of vertices;
assigning a corresponding set of neurons in a spiking neural circuit to a corresponding vertex in the plurality of vertices such that there is a correspondence between sets of neurons and the plurality of vertices, wherein the spiking neural circuit comprises a plurality of sets of spiking neurons; and
executing, with the spiking neural circuit, a stochastic process comprising a Markov process that uses the plurality of virtual random walkers, wherein executing includes tracking how many virtual random walkers are at each vertex at a given time increment.

2. The method of claim 1 wherein the sets of neurons each comprise a corresponding plurality of neurons.

3. The method of claim 1 wherein there is a one-to-one correspondence between sets of neurons and the plurality of vertices.

4. The method of claim 1 wherein executing further includes tracking all movements of all of the plurality of virtual random walkers by tracking in which vertices the plurality of virtual random walkers are located at the given time increment.

5. The method of claim 1 wherein the virtual space also includes edges connecting the plurality of vertices in a Euclidian grid.

6. The method of claim 1 wherein the virtual space also includes edges connecting the plurality of vertices in a non-Euclidian grid.

7. The method of claim 1 further comprising:
using spikes in the spiking neural circuit to move walkers from vertex to vertex, whereby additional neurons are not required to support additional virtual walkers on the virtual space, and whereby energy efficiency of executing is further improved.

8. The method of claim 1 further comprising:
storing a result of the virtual random walk on a non-transitory computer readable storage medium.

9. The method of claim 8 further comprising:
using the result to model a physical process.

10. The method of claim 9 wherein the physical process is selected from the group consisting of: radiation transport, plasma dynamics, and molecular dynamics.

11. The method of claim 8 wherein the result is used to track a property selected from the group consisting of: path dependent behavior of particles, interactions of virtual random walkers with one another, interactions of virtual random walkers with an environment in which the virtual random walkers are walking, and combinations thereof.

12. The method of claim 8 further comprising:
using the result to perform a discrete simulation Monte Carlo (DSMC) simulation of a physical process.

13. The method of claim 8 further comprising:
using the result to model an application-specific boundary condition of a physical process.

14. The method of claim 8 further comprising:
using the result to model information propagation through a social network.

15. The method of claim 8 further comprising:
using the result to compute a property of a computerized graph database.

16. The method of claim 15 further comprising:
estimating a shortest path between nodes of the computerized graph database.

17. The method of claim 15 further comprising:
finding one of a neighborhood or a clique within the computerized graph database.

18. An application-specific integrated circuit (ASIC) configured to execute a stochastic process comprising a Markov process, the ASIC comprising:
a processor architecture that implements a spiking neural circuit comprising a plurality of sets of spiking neurons, wherein each set of spiking neurons is assigned to calculate how many virtual random walkers are at each vertex in a defined virtual space at a given time increment, wherein the processor architecture further implements: using spikes in the spiking neural circuit to move walkers from vertex to vertex, whereby additional neurons are not required to support additional virtual walkers on the virtual space, and whereby energy efficiency of executing is further improved.

19. The application-specific integrated circuit of claim 18 wherein the processor architecture further implements: storing a result of the virtual random walk on a non-transitory computer readable storage medium; and using the result to model a physical process.

20. The method of claim 1 , wherein the circuit comprises:
neuromorphic hardware; or
a field programmable logic array.

21. The applications-specific integrated circuit of claim 18 , wherein the processor architecture is implemented in neuromorphic hardware.

Assignees

• Nat Tech & Eng Solutions Sandia Llc

Inventors

• Aimone James Bradley
• Severa William Mark
• Lehoucq Richard B
• Parekh Ojas D

Classifications

• G06N5/01

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

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N3/063

  using electronic means · CPC title

• G06N3/08

  Learning methods · CPC title

• G06F30/20 Primary

  Design optimisation, verification or simulation (optimisation, verification or simulation of circuit designs G06F30/30) · CPC title