Inferencing production control computer system

• US 5,615,309 A
• Filed: 12/14/1994
• Issued: 03/25/1997
• Est. Priority Date: 11/13/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kogge, Peter M., Bezek, John D.
• Primary Examiner(s): Donaghue, Larry D.
• Application Number:
  US08/356,925
• Time in Patent Office: 832 Days
• Field of Search: 395/800, 395/325, 395/524, 395/435, 395/375, 395/51, 395/52, 395/50, 395/64, 365/49
• US Class Current: 706/50
• CPC Class Codes: F02B 2075/027 four
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 15/17343 wherein the interconnection is dynamically configurable, e.g. having loosely coupled nearest neighbor architecture reconfigurable processors arrays G06F15/7867
• CPC Class Codes: G06F 15/17368 non hierarchical topologies
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 15/8007 single instruction multiple data [SIMD] multiprocessors
• CPC Class Codes: G06F 15/8015 One dimensional arrays, e.g. rings, linear arrays, buses
• CPC Class Codes: G06F 15/803 Three-dimensional arrays or hypercubes
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A computer system, and its parallel and serial implementations, its serial and parallel network and multi-processor configurations, with tight and loose coupling among processors. The computer system has a CAM coupled to the computer system or imbedded therein. CAM requests may be processed serially, or as parallel queries and coupled with PAPS (Parallel Associative Processor System) capabilities (P-CAM). The computer system may be configured as an expert system preferably having combined tuple space (TS) and CAM (content addressable memory) resources, an inference engine and a knowledge base. As an expert system, improvements for production processing are provided which surpass prior art performance represented by RETE and CLIPS. An inferencing process for production systems is disclosed, and a process for working memory element assertions. The computer system is provided with a language construct which is language independent in the form of a sub-set paradigm having three basic operators and three basic extensions. The basic primitive sub-set paradigm including OUT(); IN() and READ(). Extensions of said basic sub-set are Sample(); SampleList(); and ReadList(). These primitives may be used with LINDA, and with various compilers. EVAL of LINDA is not used but instead the sub-set paradigm is used with CAM for tuple space operations in data base applications. The language construct paradigm is use to envelope and control CAM operations.

Claims

1. A computer system for implementing an inferencing process, the computer system comprising:

an instruction processing unit (IPU);

content addressable memory (CAM) including;

working memory (WM) having working memory elements (WME),

a check list including rules each having left hand sides (LHS) data,

an agenda, and

means for storing in the WM a new WME output by an executed rule from the agenda;

means for loading data into the CAM in response to the IPU;

means for comparing the LHS data and the WMEs;

satisfaction bits each associated with a rule'"'"'s LHS datum for indicating whether or not at least one of the WMEs match the rule'"'"'s LHS datum;

the check list including rules each of whose associated satisfaction bits indicate a match between each of the rules'"'"' LHS data and at least one of the WMEs;

a pattern register for holding LHS data from a rule in the check list to be compared concurrently with a plurality of the WMEs;

the agenda including;

rules from the check list each of whose LHS data each

matched with a WME and are now scheduled to be executed; and

a mask register for selecting only a portion of LHS data in the pattern register to be compared concurrently with the plurality of the WMEs.

2. The computer system according to claim 1 wherein the CAM further includes means for deleting a WME from the WM in response to the executed rule from the agenda.

3. The computer system according to claim 1 wherein the CAM further includes refraction means for checking whether the agenda includes duplicate rules each of whose LHS data matched with a same set of WMEs.

4. The computer system according to claim 1 further comprising means for switching a satisfaction bit, associated with an LHS datum of a rule from the check list, which did not match with any WME and which caused its corresponding rule not to be included on the agenda.

5. A computer system according to claim 1 wherein said computer system is a parallel associative processor system.

6. A computer system for implementing an inferencing process, the computer system comprising:

an instruction processing unit (IPU);

content addressable memory (CAM) including working memory (WM) having working memory elements (WMEs);

means for loading data into the CAM in response to the IPU;

a check list including rules each having left hand sides (LHS) data, each LHS datum of each of the rules having associated therewith a satisfaction bit for indicating whether or not at least one of the WMEs match the LHS datum, said each LHS datum of each of the rules having its associated satisfaction bit indicating that at least one of the WMEs match said each LHS datum;

a pattern register for holding LHS data from a rule in the check list to be compared concurrently with a plurality of the WMEs;

means for comparing concurrently the LHS data from a rule in the check list with the plurality of the WMEs;

a mask register for selecting only a portion of the LHS data in the pattern register to be compared concurrently with the plurality of the WMEs;

an agenda for storing executable rules from the check list whose LHS data successfully passed a comparison with the WMEs; and

means for storing in the WM a new WME output by an executed rule from the agenda.

7. A computer system according to claim 6 wherein said computer system is a parallel associative processor system.

8. The computer system according to claim 6 further comprising means for deleting a WME from the WM in response to the executed rule from the agenda.

9. The computer system according to claim 6 further comprising refraction means for checking whether the agenda includes duplicate rules each of whose LHS data successfully passed a comparison with a same set of WMEs.

10. The computer system according to claim 6 further comprising means for switching a satisfaction bit, associated with an LHS datum of a rule from the check list, which did not match with any WME and which caused its corresponding rule not to be stored in the agenda.

11. A computer system for implementing an inferencing process, the computer system comprising:

an instruction processing unit (IPU);

content addressable memory (CAM) including working memory (WM) having working memory elements (WMEs);

means for loading data into the CAM in response to the IPU;

a check list including rules each having left hand sides (LHS) data, each LHS datum of each of the rules having associated therewith a satisfaction bit for indicating whether or not at least one of the WMEs match the LHS datum, said each LHS datum of each of the rules having its associated satisfaction bit indicating that at least one of the WMEs match said each LHS datum;

a pattern register for holding LHS data from a rule in the check list to be compared concurrently with a plurality of the WMEs;

means for comparing concurrently the LHS data from a rule in the check list with the plurality of the WMEs;

an agenda for storing executable rules from the check list whose LHS data successfully passed a comparison with the WMEs; and

means for storing in the WM a new WME output by an executed rule from the agenda.

12. A computer system according to claim 11 wherein said computer system is a parallel associative processor system.

13. The computer system according to claim 11 further comprising means for deleting a WME from the WM in response to the executed rule from the agenda.

14. The computer system according to claim 13 further comprising refraction means for checking whether the agenda includes duplicate rules each of whose LHS data successfully passed a comparison with a same set of WMEs.

15. The computer system according to claim 14 further comprising means for switching a satisfaction bit, associated with an LHS datum of a rule from the check list, which did not match with any WME and which caused its corresponding rule not to be stored in the agenda.