Systems, methods, and apparatuses for solving stochastic problems using probability distribution samples

• US 9,659,255 B2
• Filed: 11/19/2013
• Issued: 05/23/2017
• Est. Priority Date: 02/23/2010
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Jonas, Eric M., Mansinghka, Vikash K.
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Seck, Ababacar
• Application Number:
  US14/083,850
• Publication Number:
  US 20140081899A1
• Time in Patent Office: 1,281 Days
• Field of Search: None
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/043 Distributed expert systems; Blackboards
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence
• CPC Class Codes: G06N 5/048 Fuzzy inferencing
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

Abstract

Techniques described herein may be used to solve a stochastic problem by dividing the stochastic problem into multiple fragments. In some cases, each fragment may be related to a random variable that forms a part of the problem, such that each fragment may produce samples from a probability distribution for that variable. Each fragment of the stochastic problem may then be assigned to a configurable circuit to solve the stochastic fragment. Configurable circuits may be implemented using any suitable combination of hardware and/or software, including using stochastic circuitry. In some embodiments, stochastic circuitry may include a stochastic tile and/or a stochastic memory.

Claims

1. An apparatus for solving a stochastic problem, comprising:

a configurable circuit comprising a processing unit to produce samples from a probability distribution related to the stochastic problem;

a controller to configure the processing unit by providing information about the stochastic problem to the processing unit and to cause the processing unit to produce the samples;

at least one memory storing information regarding a plurality of stochastic problems, wherein the controller exercises a control to reconfigure the processing unit by providing information about a first stochastic problem of the plurality of stochastic problems to the processing unit at a first time and to provide information about a second stochastic problem of the plurality of stochastic problems at a second time; and

wherein the controller is further adapted to;

provide information regarding a first stochastic problem to the processing unit at a first time;

make a selection of a next stochastic problem, and

provide information regarding the next stochastic problem to the processing unit at a second time; and

wherein the controller is further adapted to provide a predetermined number of values to the processing unit and, when a number of other stochastic problems upon which the first stochastic problem depends is less than the predetermined number, the controller performs a masking operation which indicates to the processing unit that fewer than the predetermined number of values are being provided.

2. The apparatus of claim 1, wherein the controller is adapted to make the selection according to one of:

making the selection according to a predetermined order;

or

making the selection randomly.

3. The apparatus of claim 1:

wherein each of the plurality of stochastic problems is a stochastic fragment of a second stochastic problem;

wherein a first stochastic fragment is conditionally dependent upon a second stochastic fragment, and

wherein the controller is adapted to provide information regarding the first stochastic fragment to the processing unit by providing to the processing unit a sample produced from a probability distribution associated with the second stochastic fragment.

4. The apparatus of claim 1, wherein each of the plurality of stochastic problems is a stochastic fragment of a second stochastic problem, and

wherein the controller is adapted to provide information about a first stochastic fragment to the processing unit, the information about the first stochastic fragment comprising at least one sample generated from at least one second stochastic fragment.

5. The apparatus of claim 1, wherein the configurable circuit is a core of a multi-core system,

wherein the controller configures the processing unit to solve the stochastic problem by assigning a processing unit of the core to execute a first thread and providing a first thread stack to the core, the first thread including instructions to produce samples from a first probability distribution;

and

wherein the controller reconfigures the processing unit to solve a next stochastic problem by assigning the processing unit of the core to execute a second thread and providing a second thread stack to the core, the second thread including instructions to produce samples from a second probability distribution.

6. The apparatus of claim 5, wherein the multi-core system is selected from one of:

a multi-core processor;

a multi-core processor wherein each of the cores constitute a low precision core having a small amount of memory, and wherein the processing unit generates the sample with low precision;

a multi-core processor wherein each of the cores processes data in words having a size of less than or equal to 8 bits;

a multi-core processor wherein each of the cores processes data in words having a size of less than or equal to 16 bits;

a multi-core processor wherein each of the cores processes data in words having a size of less than or equal to 32 bits;

a multi-core processor wherein each of the cores processes data in words having a size less than or equal to 64 bits;

a multi-core processor comprised of hundreds of cores, each of the cores being arranged as a configurable circuit; and

a multi-core processor comprised of thousands of cores, each of the cores being arranged as a configurable circuit.

7. The apparatus of claim 6, wherein the multi-core system operates each of the cores in parallel such that each solves a fragment of a stochastic problem.

8. The apparatus of claim 6, wherein the multi-core system operates each of the cores in parallel asynchronously.

9. The apparatus of claim 6, wherein the multi-core system is implemented within a single integrated circuit.

10. The apparatus of claim 6, wherein no core of the multi-core system includes a memory management unit or a general purpose cache.

11. The apparatus of claim 6, wherein each core of the multi-core system includes memory of a single type, and wherein the single type is a register.

12. The apparatus of claim 6, wherein each core comprises a memory and a processing unit, the processing unit of each core being adapted to request data from the memory, and the memory is adapted to return the data to the processing unit without communicating outside the core.

13. The apparatus of claim 1, wherein the configurable circuit comprises a stochastic tile, the stochastic tile comprising at least one stochastic circuit acting as the processing unit, and

wherein the controller configures the processing unit by providing information to the at least one stochastic circuit describing a current state of one or more variables and information describing a probability distribution from which to produce the samples.

14. The method of claim 13, wherein the controller provides the information describing the probability distribution by providing to the processing unit a look-up table including values of a conditional probability table.

15. The apparatus of claim 1, wherein the apparatus comprises a deterministic processor, and wherein the deterministic processor assigns to a configurable circuit the stochastic problem to be solved.

16. The apparatus of claim 15, wherein the deterministic processor transmits an operation code to the configurable circuit instructing the configurable circuit to solve the stochastic problem.

17. The apparatus of claim 1, further comprising at least one hundred second configurable circuits, each second configurable circuit of the at least one hundred second configurable circuits comprising:

a second processing unit to produce samples from a probability distribution related to a stochastic problem;

a second controller to configure the second processing unit by providing information about the stochastic problem to the processing unit and to cause the processing unit to produce the samples; and

wherein the at least one hundred second configurable circuits are arranged to be operated in parallel asynchronously to each solve a particular stochastic problem.

18. The apparatus of claim 17, wherein each of the at least one hundred configurable circuits comprises a stochastic tile, each stochastic tile comprising at least one stochastic circuit acting as the processing unit, and

wherein the controller configures the processing unit by providing information to the at least one stochastic circuit describing a current state of one or more variables and information describing a probability distribution from which to produce the samples.

19. A method for solving a stochastic problem executed by a system having at least a processor and a memory therein to carry out instructions for solving the stochastic problem, wherein the method comprises:

producing samples from a probability distribution via a configurable circuit of the system having a processing unit therein, the samples produced being related to the stochastic problem to be solved;

configuring, via a controller of the system, the processing unit by providing information about the stochastic problem to the processing unit, wherein configuring the processing unit causes the processing unit to produce the samples;

storing information within the memory of the system, the information regarding a plurality of stochastic problems;

reconfiguring, via the controller, the processing unit by providing information about a first stochastic problem of the plurality of stochastic problems to the processing unit at a first time and by further providing, via the controller, information about a second stochastic problem of the plurality of stochastic problems to the processing unit at a second time;

wherein the reconfiguring of the processing unit via the controller comprises at least;

(i) making a selection, via the controller, of a next stochastic problem from the plurality of stochastic problems and (ii) providing, via the controller, information regarding the next stochastic problem to the processing unit at the second time; and

providing, from the controller, a predetermined number of values to the processing unit and, when a number of other stochastic problems upon which the first stochastic problem depends is less than the predetermined number, performing a masking operation from the controller indicating to the processing unit that fewer than the predetermined number of values are being provided.

20. The method of claim 19, wherein (i) making a selection, via the controller, of a next stochastic problem from the plurality of stochastic problems comprises one of:

making a selection, via the controller, according to a predetermined order;

or

making a selection, via the controller, randomly.

21. The method of claim 19:

wherein each of the plurality of stochastic problems is a stochastic fragment of a second stochastic problem;

wherein a first stochastic fragment is conditionally dependent upon a second stochastic fragment, and

wherein the method further comprises providing, via the controller, information regarding the first stochastic fragment to the processing unit by providing to the processing unit a sample produced from a probability distribution associated with the second stochastic fragment.

22. Non-transitory computer readable storage media having instructions stored thereupon that, when executed by a processing unit of a system in conjunction with a memory, the instructions cause the system to carry out operations comprising:

producing samples from a probability distribution via a configurable circuit of the system having a processing unit therein, the samples produced being related to the stochastic problem to be solved;

configuring, via a controller of the system, the processing unit by providing information about the stochastic problem to the processing unit, wherein configuring the processing unit causes the processing unit to produce the samples;

storing information within the memory of the system, the information regarding a plurality of stochastic problems;

reconfiguring, via the controller, the processing unit by providing information about a first stochastic problem of the plurality of stochastic problems to the processing unit at a first time and by further providing, via the controller, information about a second stochastic problem of the plurality of stochastic problems to the processing unit at a second time; and

wherein the reconfiguring of the processing unit via the controller comprises at least;

(i) making a selection, via the controller, of a next stochastic problem from the plurality of stochastic problems and (ii) providing, via the controller, information regarding the next stochastic problem to the processing unit at the second time; and

providing, from the controller, a predetermined number of values to the processing unit and, when a number of other stochastic problems upon which the first stochastic problem depends is less than the predetermined number, performing a masking operation from the controller indicating to the processing unit that fewer than the predetermined number of values are being provided.

23. The non-transitory computer readable storage media of claim 22, wherein (i) making a selection, via the controller, of a next stochastic problem from the plurality of stochastic problems comprises one of:

making a selection, via the controller, according to a predetermined order;

or

making a selection, via the controller, randomly.

24. The non-transitory computer readable storage media of claim 22:

wherein each of the plurality of stochastic problems is a stochastic fragment of a second stochastic problem;

wherein a first stochastic fragment is conditionally dependent upon a second stochastic fragment, and

wherein the instructions cause the system to perform operations further comprising;

providing, via the controller, information regarding the first stochastic fragment to the processing unit by providing to the processing unit a sample produced from a probability distribution associated with the second stochastic fragment.