Associative program control

• US 5,259,066 A
• Filed: 04/16/1990
• Issued: 11/02/1993
• Est. Priority Date: 04/16/1990
• Status: Expired due to Term

• Current Assignee: Systemics LLC (Intellectual Ventures LLC)
• Original Assignee: Richard Q. Schmidt
• Inventors: Schmidt, Richard Q.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): Downs, Robert W.
• Application Number:
  US07/510,212
• Time in Patent Office: 1,296 Days
• Field of Search: 395/1, 395/54, 395/10, 365/49
• US Class Current: 706/50
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition

Abstract

Methods and an arrangement providing improved expert system performance. A mathematically based method is used in building a rule base that guarantees a complete and consistent rule set, providing an aid for identifying missing rules. The method is used in recognizing input variable patterns in parallel to provide rapid inferencing. An arrangement based on the method is given for a content addressable memory capable of returning an address of an executable routine for each rule of a rule set given the system state variables. The method is employed to provide associative program control, in which program control flow adapts to changing system state variables. A method is described for associative database management, using the new content addressable memory arrangement.

Claims

1. A method for rapidly processing expert system rules in computing machinery comprising the steps of:

a. determining all conditions that define knowledge within a domain boundary, said conditions defined by n different binary valued variables;

b. numbering said variables sequentially 1 through n;

c. for each said condition;

defining a rule word and an associated validity word, said rule word and said validity word containing bits numbered sequentially 1 through n;

d. defining a data word containing bits numbered sequentially 1 through n;

e. in all said words;

assigning said bits numbered 1 through n to represent said variables of corresponding number;

f. for each said rule word;

defining a value for said rule word by assigning a 1 to a bit in said rule word if the variable said bit represents is true or present in the condition said rule word represents, assigning a 0 to said bit otherwise;

g. for each said rule word;

defining a value for said associated validity word by assigning a 1 to a bit in said validity word if the variable said bit represents has an effect in the condition said rule word represents, assigning a 0 to said bit otherwise;

h. defining a value for said data word by assigning a 1 to a bit in said data word if the variable said bit represents is true or present, assigning a 0 to said bit otherwise;

i. storing said rule words and said associated validity words in a content addressable memory (CAM), said CAM performing the steps of;

3. A method as defined in claim 1, wherein step (i) is replaced by:

i. storing said rule words and said associated validity words in a content addressable memory (CAM), said CAM performing the steps of;

forming a comparison word for each said rule word, bits of said comparison word being set to 1 when corresponding bits of said data word and said rule word are equal;

logically ORing said comparison word with the logical inverse of said stored validity word associated with said rule word; and

declaring a match when the result of said ORing is a one for each said bit.

4. A method as defined in claim 1, wherein steps (i) through (j) are replaced by:

i. for each said rule word;

defining an associated reporting word and assigning a value to said reporting word;

j. storing said rule words, said associated validity words, and said associated reporting words in a content addressable memory (CAM), said CAM performing the steps of;

1. logically ANDing said data word with each said validity word, forming masked data words; and

2. declaring a match when one of said masked data words and the rule word associated with the validity word forming said one of said masked data words are equal; and

k. applying said data word to said CAM, said CAM reporting said reporting word associated with said rule word for which said match is declared.

5. A method as defined in claim 1 wherein the step of storing said rule words and said associated validity words is followed by a by a step of selecting a group of said rule words and associated validity words stored in said CAM, forming a selected group;

and said ANDing step and said declaring step are restricted to said selected group.

6. A method as defined in claim 1, wherein steps (i) through (j) are replaced by:

i. storing said rule words in a programmable content addressable memory (PCAM);

j. disabling each bit of each said rule word stored in said PCAM if the corresponding bit in said associated validity word is a 0, the remaining bits of said rule word being enabled; and

k. applying said data word to said PCAM, said PCAM reporting said rule word whose enabled bits are equal to corresponding bits in said data word.

7. A method as defined in claim 5 wherein the step of storing said rule words is followed by a by a step of selecting a group of said rule words stored in said PCAM, forming a selected group;

and in said applying step the reporting by said PCAM is restricted to said selected group by said PCAM.

8. A method as defined in claim 1, wherein steps (i) through (j) are replaced by:

i. storing said rule words in a maskable content addressable memory (MCAM);

j. disabling each bit of each said rule word stored in said MCAM if the corresponding bit in said associated validity word is a 0, the remaining bits of said rule word being enabled; and

k. applying said data word to said MCAM, said MCAM reporting said rule word whose enabled bits are equal to corresponding bits in said data word.

9. A method as defined in claim 7 wherein the step of storing said rule words is followed by a by a step of selecting a group of said rule words stored in said MCAM, forming a selected group;

and in said applying step the reporting by said MCAM is restricted to said selected group by said MCAM.

10. A method as defined in claim 1, wherein steps (i) through (j) are replaced by:

i. for each said rule word;

defining an associated reporting word and assigning a value to said reporting word;

j. storing said rule words and said associated reporting words in a programmable content addressable memory (PCAM) with each bit of each said rule word stored in said PCAM enabled if the corresponding bit in said associated validity word is a 1, otherwise said bit is disabled; and

k. applying said data word to said PCAM, said PCAM reporting said reporting word associated with said rule word whose enabled bits are equal to corresponding bits in said data word.

11. A method as defined in claim 1, wherein steps (i) through (j) are replaced by:

i. for each said rule word;

defining an associated reporting word and assigning a value to said reporting word;

j. storing said rule words and said associated reporting words in a maskable content addressable memory (MCAM) with each bit of each said rule word stored in said MCAM enabled if the corresponding bit in said associated validity word is a 1, otherwise said bit is disabled; and

k. applying said data word to said MCAM, said MCAM reporting said reporting word associated with said rule word whose enabled bits are equal to corresponding bits in said data word.

13. A rule based expert system as defined in claim 11 wherein said rule applying means and rule masking means are replaced by:

rule applying means for recording a "match" state for each said bit of said rules stored in said rule memory means for which said bit equals the state of a corresponding bit of a data word, recording a "no match" state for each said bit of said rules for which said bit does not equal the state of a corresponding bit of said data word; and

rule masking means for reporting a matching rule when no bits of said matching rule are recorded "no match" by said rule applying means for which the corresponding indicator stored in said mask memory means is in a given state, said matching rule being one of said rules stored in said rule memory means.

15. A rule based expert system as defined in claim 11 wherein said rule memory means, said mask memory means, said rule applying means, and said rule masking means comprises a content addressable memory (CAM).

2. logically ANDing said data word with each said validity word, forming masked data words;

and

2. declaring a match when one of said masked data words and the rule word associated with the validity word forming said one of said masked data words are equal; and

j. applying said data word to said CAM, said CAM reporting said rule word for which said match is declared.

12. A rule based expert system comprising:

rule memory means for storing rules, each said rule composed of bits, each said bit representing one state of a binary valued condition variable;

mask memory means for storing masks, one said mask associated with each said rule, each said mask comprising binary indicators, one said indicator for each said bit of said rule;

rule applying means for reporting a matching rule when all bits of a data word coupled to said rule applying means equal the corresponding bits of said matching rule, said matching rule being one of said rules stored in said rule memory means; and

rule masking means for coupling said data word, wherein for each said mask associated with each said rule, each said indicator stored in said mask couples a different said bit of said data word to said rule applying means when said indicator is in one given state, said bit of said data word is not coupled when said indicator is in a second state.

14. A rule based expert system as defined in claim 12 wherein said rule memory means, said mask memory means, said rule applying means, and said rule masking means comprises a content addressable memory (CAM).

16. A rule based expert system as defined in claim 14 wherein said rule applying means comprises further single step control means for selecting a group of said rules stored in said rule memory means and associated said masks stored in said mask memory means;

and means for restricting said rule applying means to reporting a matching rule within said group selected.

17. A rule based expert system as defined in claim 14 wherein said CAM reports a reporting word associated with said matching rule in place of said matching rule and said CAM further includes:

reporting word storage means for storing said reporting word, at least one said reporting word associated with each said stored rule.

19. A rule based expert system as defined in claim 17 wherein said rule applying means comprises further single step control means for selecting a group of said rules stored in said rule memory means;

and means for restricting said rule applying means to reporting a matching rule within said group selected.

20. A rule based expert system as defined in claim 17 wherein said PCAM reports a reporting word associated with said matching rule in place of said matching rule and said PCAM further includes:

reporting word storage means for storing said reporting word, at least one said reporting word associated with each said stored rule.

22. A rule based expert system as defined in claim 20 wherein said rule applying means comprises further single step control means for selecting a group of said rules stored in said rule memory means;

and means for restricting said rule applying means to reporting a matching rule within said group selected.

23. A rule based expert system as defined in claim 20 wherein said MCAM reports a reporting word associated with said matching rule in place of said matching rule and said MCAM further includes:

reporting word storage means for storing said reporting word, at least one said reporting word associated with each said stored rule.

18. A rule based expert system comprising a programmable content addressable memory (PCAM) containing:

rule memory means for storing rules, each said rule composed of bits, each said bit representing one state of a binary valued condition variable;

rule applying means for reporting a matching rule when all selected bits of a data word applied to said rule applying means equal the corresponding bits of said matching rule, said matching rule being one of said rules stored in said rule memory means; and

rule masking means for selecting said selected bits applied to said rule applying means, each said rule having an independent set of said selected bits.

21. A rule based expert system comprising a maskable content addressable memory (MCAM) containing:

rule memory means for storing rules, each said rule composed of bits, each said bit representing one state of a binary valued condition variable;

rule applying means for reporting a matching rule when all selected bits of a data word applied to said rule applying means equal the corresponding bits of said matching rule, said matching rule being one of said rules stored in said rule memory means; and

rule masking means for selecting said selected bits applied to said rule applying means, each said rule having an independent set of said selected bits.