Probabilistic computing methods and apparatus

• US 6,463,422 B1
• Filed: 07/22/1997
• Issued: 10/08/2002
• Est. Priority Date: 08/26/1994
• Status: Expired due to Term

• Current Assignee: Ricky D. Hangartner
• Original Assignee: Ricky D. Hangartner
• Inventors: Hangartner, Ricky D.
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): STARKS, WILBERT L
• Application Number:
  US08/898,528
• Time in Patent Office: 1,904 Days
• Field of Search: 706/13, 706/52, 706/45
• US Class Current: 706/14
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

A new probabilistic computing system (PCS) provides computational functionality needed to efficiently realize randomized computing methods in otherwise standard, deterministic digital computing systems. The PCS may be incorporated in a standard computing platform such as a PC or workstation. In the PCS, a computational path includes a random access memory (RAM) where a predetermined computing problem is stored in conjunctive normal form. A nondeterministic subsystem generates random binary values forming a proposed solution to the problem, which solution is rapidly checked through a crosspoint switch array coupled to the RAM. The computational path essentially runs asynchronously, while a delay circuit provides delay and timing signals for interfacing with external DRAM, as well as a synchronizing signal for operation of several of the PCS systems together for enhanced performance.

Claims

1. A nondeterministic logic circuit for generating random boolean values of one or more variables as a proposed solution to a computing problem expressed in conjunctive normal form as one more clauses in said one or more variables, the logic circuit comprising:

one nondeterministic logic element for generating a respective random boolean value for each one of the said one or more variables; and

each nondeterministic logic element comprising;

a cross-coupled pair of transistor inverter circuits;

means for controlling power to the cross-coupled pair of transistor inverter circuits; and

means for equalizing charge on the gates of the transistor inverter circuits while power is removed from the cross-coupled pair, thereby driving the cross-coupled pair to an unstable equilibrium, whereby intrinsic circuit noise will cause the cross-coupled pair to randomly assume one of two stable states when power is restored to the cross-coupled pair, the stable state assumed by the cross-coupled pair providing a probabilistically selected random boolean value

and further comprising common synchronization means coupled to all of the nondeterministic logic elements for synchronizing operation of the nondeterministic logic elements.

2. A hardware probabilistic computing system comprising:

memory means for receiving and storing a digital representation of a predetermined combinatorial computing problem expressed as a series of clauses in conjunctive normal form, the memory means including a plurality of rows of memory cells, each row arranged for storing a series of data bits corresponding to a respective clause of the computing problem;

nondeterministic logic means for generating a first set of random boolean values of a series of variables as a first proposed solution to the stored computing problem, the nondeterministic logic means including a series of semiconductor nondeterministic logic elements, each nondeterministic logic element arranged for generating a respective one of the random boolean values, and the series of semiconductor nondeterministic logic elements being coupled together so as to generate the random boolean values for all of the variables substantially concurrently in response to a single flip control signal;

testing means coupled to the memory means and to the nondeterministic logic means, the clause testing means including, for each row of the memory means, first logic means coupled to the corresponding row of the memory means and coupled to the nondeterministic logic elements for providing a respective computed function signal that indicates whether the series of random boolean values satisfies the corresponding clause of the computing problem;

second logic means coupled to receive all of the computed function signals for determining and indicating that the first proposed solution does not satisfy the computing problem as soon as any one of the computed function signals indicates, by its logic state, that the corresponding clause of the problem is not satisfied; and

feedback means coupled to the second logic means for asserting the flip signal to generate an alternative set of random boolean values as an alternative proposed solution to the computing problem responsive to the second logic means indicating the first proposed solution does not satisfy the computing problem, so that the nondeterministic logic means, the clause testing means, the second logic means and the feedback means together form a hardware loop operable asynchronously.

3. A probabilistic computing system according to claim 2 wherein:

the first logic means comprises a series of crosspoint switch circuits, each crosspoint switch circuit being coupled to receive a respective bit of the corresponding row of the memory means;

each crosspoint switch circuit further being coupled to receive the corresponding variable signal;

and each crosspoint switch circuit including means for coupling the corresponding probabilistic variable signal to a common circuit node only if the said respective bit has a first predetermined logic state; and

the first logic means further comprises a logic gate coupled to the common circuit node for asserting the computed function signal responsive to such of the probabilistic variable signals as are coupled to the common circuit node by the crosspoint switch circuits so as to indicate whether the first series of random probabilistic variable values satisfies the corresponding clause of the computing problem.

5. A probabilistic computing system according to claim 2 wherein:

the testing means includes an array of logic gates and a crosspoint switch array controllably interconnecting the nondeterministic logic means and the logic gates, the crosspoint switch array also being coupled to the memory means so that the crosspoint switch array couples selected ones of the said variables to the logic gates responsive to the representation of the computing problem stored in the memory means, whereby each logic gate computes a logical function of a subset of the variables, the subset being defined by data stored in the memory.

6. A probabilistic computing system according to claim 2 further comprising a DRAM type of interface means for storing intermediate results in a second memory.

7. A probabilistic computing system according to claim 2 further comprising a DRAM type of interface means for interfacing the probabilistic computing system to a host processor as a memory-mapped peripheral device.

4. A probabilistic computing system according to claim 4 wherein the second logic means comprises a NOR gate having a number of inputs at least equal to the number of clauses in the computing problem.

8. A hardware probabilistic computing system comprising:

memory means for receiving and storing a digital representation of a predetermined combinatorial computing problem expressed as a Boolean function;

nondeterministic logic means for generating a first set of random boolean values of a series of variables as a first proposed solution to the stored computing problem, the nondeterministic logic means including a series of semiconductor nondeterministic logic elements, each nondeterministic logic element having a pair of outputs arranged for generating a respective one of the random boolean values and its logical complement, and the series of nondeterministic logic elements being coupled together and arranged so as to assert both the uncomplemented and complemented outputs for all the variables to a first predetermined logical state in response to receiving a common flip control signal asserted to a predetermined logical ‘

reset’

state, and arranged so as to generate the random boolean values for all of the variables substantially concurrently in response to the flip control signal switching from the ‘

reset’

state to a logically complementary ‘

generate’

state;

configurable logic means having the pairs of outputs from the nondeterministic logic means, as input pairs and having a single output and including means for computing the Boolean function of the input pairs;

the configurable logic means including a circuit which computes the Boolean function such that the output of the configurable logic means assumes a first predetermined logical value—

a ‘

satisfied’

value—

when the flip control signal is in the logical ‘

reset’

state and both outputs in every output pair of the non-deterministic logic means representing the true and complemented random variables are asserted to a first predetermined logic state;

the output of the configurable logic means assuming a logically complementary ‘

unsatisfied’

value when the set of random Boolean values generated by the non-deterministic logic means in response to assertion of the flip control signal to the ‘

generate’

value is not a solution to the computing problem represented by the Boolean function;

the output of the configurable logic means further assuming the ‘

satisfied’

value when the set of random Boolean values generated by the non-deterministic logic means in response to assertion of the flip control signal to the ‘

generate’

value is a solution to the computing problem represented by the Boolean function; and

the configurable logic means further arranged such that if the output of the configurable logic means changes from the ‘

satisfied’

value to the ‘

unsatisfied’

value when one output pair of the non-deterministic logic means changes to the state in which the outputs have random complementary values in response to assertion of the single flip signal to the ‘

generate’

value, the configurable logic means output cannot change back to the ‘

satisfied’

value as each of the remaining output pairs of the non-deterministic logic change to the state in which those outputs have a random complementary values in response to the assertion of the single flip signal to the ‘

generate’

value; and

feedback means coupled to the output of the configurable logic means for asserting the flip signal to the ‘

generate’

state to generate an alternative set of random boolean values as an alternative proposed solution to the computing problem responsive to the output of the configurable logic means assuming the ‘

unsatisfied’

value so that the nondeterministic logic means, the configurable logic means and the feedback means together form a hardware loop operable asynchronously.

9. A hardware probabilistic computing system according to claim 8 wherein:

the memory means includes a plurality of rows of memory cells, each row arranged for storing a series of data bits corresponding to a respective clause of the computing problem and comprising a series of bits, each bit such corresponding to a respective one of the variables;

the configurable logic means includes, for each row of the memory means, first logic means coupled to the corresponding row of the memory means and coupled to the nondeterministic logic means for providing a respective computed function signal that indicates whether the series of random boolean values satisfies the corresponding clause of the computing problem; and

second logic means coupled to receive all of the computed function signals for determining and indicating that the first proposed solution satisfies the computing problem when all of the computed function signals indicate that the corresponding clauses of the problem are satisfied.

10. A hardware probabilistic computing system according to claim 9 wherein:

the first logic means comprises a series of crosspoint switch circuits, each crosspoint switch circuit being coupled to receive a respective bit of the corresponding row of the memory means;

each crosspoint switch circuit further being coupled to receive the corresponding variable signal from the nondeterministic logic means;

and each crosspoint switch circuit including means for coupling the corresponding probabilistic variable signal to a common circuit node only if the said respective bit has a first predetermined logic state; and

the first logic means further comprises a logic gate coupled to the common circuit node for asserting the computed function signal responsive to such of the probabilistic variable signals as are coupled to the common circuit node by the crosspoint switch circuits so as to indicate whether the first set of random Boolean values satisfies the corresponding clause of the computing problem.