Data processing: artificial intelligence – Adaptive system
Reexamination Certificate
1997-07-22
2002-10-08
Teska, Kevin J. (Department: 2122)
Data processing: artificial intelligence
Adaptive system
C706S052000, C706S045000
Reexamination Certificate
active
06463422
ABSTRACT:
BACKGROUND OF THE INVENTION
For each combinatoric computing problem which focuses on finding an appropriate value assignment for the variables in the problem, a corresponding decision problem can be constructed which seeks a YES-NO answer as to whether a candidate assignment for the variables is actually a solution to the combinatoric problem. Nondeterministic Polynomial Time complete (NP-complete) decision problems are those for which no efficient solution method is known, in the sense that the number of steps in the solution method is a polynomial function of the size of the smallest representation of the problem (referred to as “polynomial-time”), but for which a candidate guess of the solution can be checked in polynomial time. It is known that all NP-complete problems are polynomial-time Karp-reduction equivalent, i.e., any instance of a particular NP-complete problem can be mapped in a polynomial time into an instance of some other NP-complete problem such that the solutions of this problem correspond to solutions of the original problem under the mapping.
Randomized computing methods incorporate probabilistic decision making techniques in addition to deterministic techniques and provide a solution to the problem which is correct with some minimum and selectable probability. Although it is believed that no deterministic, polynomial-time solution method exists for NP-Complete problems, it is known that the class PP of decision problems solvable in polynomial time by randomized computing methods includes the NP-complete problems. See “Structural Complexity I” by J. L. Balcazar, J. Diaz and J. Gabarro.
In the prior art, simulated annealing methods so-called Boltzmann machines have been referred to as randomized computing systems. See “Optimization by Simulated Annealing” by S. Kirkpatrick, C. D. Gelett and M. P. Vecchi; “A Thermodynamic Approach to the Traveling Salesman Problem: An Efficient Simulation” by V. Cerny, and “Boltzmann Machines: Constraint Satisfaction Networks that Learn” by G. E. Hinton, T. J. Sejnowski and D. H. Ackley. These methods differ from the present invention, however, in that they are more properly identified as heuristic methods for solving combinatorial computing problems. Although some versions of these methods do incorporate probabilistic decision techniques, the solutions they provide in polynomial-time are not guaranteed to be correct with some minimum selectable probability. The prior art does not appear to include any computing systems which efficiently realize randomized computing methods in the formal rigorous sense defined above.
SUMMARY OF THE INVENTION
The probabilistic computing system (PCS) of the present invention provides the 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 in various ways. For example, for applications requiring moderate performance, a VLSI probabilistic computation network chip, further described below, can be combined with standard dynamic RAMs and used as a memory-mapped peripheral. In such a configuration, multiple PCS-DRAM modules can be interconnected for increased processing power. For higher performance applications, a peripheral device analogous to a mass memory peripheral (for example a hard disk) can be constructed by combining multiple PCS chips with dynamic RAM and interface logic. The disclosed invention allows solution of computing problems that heretofore could not be practically solved in small systems.
A probabilistic computing system according to the invention includes a memory for receiving and storing a digital representation of a predetermined combinatorial computing problem. The problem is expressed as a series of clauses in conjunctive normal form. In the preferred embodiment, the memory 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. Each row stores a series of pairs of bits, each bit pair corresponding to a respective one of the variables and its logical complement.
A nondeterministic logic subsystem is provided for generating a set of random boolean values of the variables as a first proposed solution to the stored computing problem. Testing circuitry is coupled to the memory and to the nondeterministic logic means for testing whether the first set of random boolean values satisfies the stored computing problem. Finally, a feedback circuit couples the testing circuit and to the nondeterministic logic subsystem for controlling the ND subsystem so as to generate an alternative set of random boolean values of the series of variables as an alternative proposed solution to the computing problem whenever the testing circuit indicates that the computing problem is not satisfied. Thus the nondeterministic subsystem, the testing circuit and the feedback circuit together form a hardware loop for asynchronous operation. The system preferably is run asynchronously to maximize speed.
The nondeterministic subsystem includes a series of semiconductor nondeterministic logic elements. Each ND logic element includes a cross-coupled pair of inverting gates arranged for generating a respective one of the random boolean values of the series of variables, responsive to the variety of noise sources intrinsic to VLSI circuits.
The testing circuit includes, for each row of the memory means, a wide “programmable” NOR gate. The NOR gate provides a computed function signal (Cn) that indicates whether the proposed series of random boolean values satisfies the corresponding clause of the computing problem. Each bit of the data stored in the memory determines whether or not a corresponding one of the variables is included as an input to the NOR gate. In this way, the NOR gate is programmed to reflect the clause of the problem stored in that row of the memory.
Thus, the first wide NOR gate may be considered as part of a crosspoint switch array overlying the memory. The crosspoint switch array includes a series of crosspoint switch circuits, each crosspoint switch circuit being coupled to a respective bit of the corresponding row of the memory. Each crosspoint switch circuit also receives the corresponding variable signal from the corresponding ND logic element. In operation, each crosspoint switch circuit couples the corresponding probabilistic variable signal to a common circuit node—the NOR gate input—only if the said respective bit has a first predetermined logic state.
Accordingly, the programmable NOR gate in each row asserts the corresponding computed function signal responsive to such of the probabilistic variable signals as are coupled to the NOR input 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.
A second wide NOR gate is coupled to receive all of the computed function signals (C
1
-Cq) for determining and indicating whether the proposed solution satisfies the computing problem. This is true only when all of the computed function signals indicate that the corresponding clauses of the problem are satisfied. Accordingly, the second NOR gate has a number of inputs at least equal to the number of clauses in the computing problem. The output of the second NOR gate is used in the feedback circuit to trigger another set of values if the problem is not yet satisfied. A delay circuit in the feedback circuit provides for writing intermediate results to a DRAM.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment which proceeds with reference to the drawings.
REFERENCES:
patent: 3812473 (1974-05-01), Tucker
patent: 5148513 (1992-09-01), Koza et al.
patent: 5390282 (1995-02-01), Koza et al.
patent: 5680518 (1997-10-01), Hangartner
patent: 5742738 (1998-04-01), Koza et al.
patent: 5812740
Starks Wilber
Stoel Rives LLP
Teska Kevin J.
LandOfFree
Probabilistic computing methods and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Probabilistic computing methods and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic computing methods and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984226