JPH0642200B2 - Production system - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a production system, and more particularly to a production system suitable for automatically designing a semiconductor integrated circuit using a forward reasoning program.

[Conventional technology]

As a conventional production system, the one described in cognitive psychology 2 learned by LISP (Yuichiro Anzai, The University of Tokyo Press, 1982, first edition, pages 132 to 136) is known. In the production system described in this document, the rule compiler method based on the discrimination net is adopted. However, the algorithm of this method is less efficient in the application field where there are many variables in the rule conditions. However, the compile time is also a problem. For example, in the field of handling semiconductor integrated circuits, in the case of equivalent conversion of mathematical logic into a logic circuit that can be realized as a semiconductor integrated circuit, since the connection information of the circuit is handled, the rule inevitably includes many variables. This method was not enough to speed up the production system.

Further, as an application of a production system to the equivalent conversion of a logic circuit, there is known one disclosed in Japanese Patent Application Laid-Open No. 59-168545. However, in the prior art, the speed of the production system is increased. It wasn't enough.

[Problems to be solved by the invention]

The above-mentioned conventional technique does not take into consideration the case of handling information without a hierarchy, such as connection information of a logic circuit, regarding speeding up of a production system, and when there are many variables in the conditional description of a rule. However, there is a problem that the processing speed decreases. In particular, as the scale of the circuit to be handled and the number of rules increase, there is a problem that it takes a lot of time to search for an adaptable rule. That is, in the case of performing the matching process for searching the applicable rule from the rule group,
Since it tried to match all the rules in each matching cycle, it took a lot of time to find an applicable rule from the rule group.

An object of the present invention is to provide a production system capable of rearranging the collation order of rules according to the collation result when performing collation processing for searching for an applicable rule from a rule group.

[Means for solving problems]

In order to achieve the above-mentioned object, the present invention stores a working storage unit for storing information about a conversion target and a precondition for converting the information about the conversion target into new information according to a list of character strings by symbols and variables. Rule storing means for storing a precondition part and an execution part for storing execution contents when the condition of the precondition part is satisfied according to a list of character strings in association with a collation order, and information and rules of work storing means. Interpretation execution means for sequentially matching the preconditions of each rule in the storage means for each matching cycle, executing the execution contents of the rule that succeeded in the matching, and updating the information in the working storage means according to the conclusion of the rule, and the rule storage A rule flag storage means for storing a matching result of each rule in each rule flag, the rule flag group being associated with each rule of the means, The executing means executes the collation with respect to the rule group of the rule storing means according to the collation order, and when the collation fails, the rule flag corresponding to the rule is collated with the rule with the highest collation order to the rule with the lowest collation order. When the matching is successful, when the matching is successful, the contents of the rule that succeeds first in the matching cycle are executed as one matching cycle. The processing shifts to the processing by the collation cycle, and in the next collation cycle, the collation of the rule for which the collation prohibition flag is set and the information in the working storage means is prohibited, and the collation is started from the rule that succeeded in the collation cycle in the previous time. Then
Further, after at least one round of matching with the rule group, only the rule that succeeds in matching is selected from the rule group, the selected rule group is changed to a higher rank of the matching order, and after the matching order is changed, the rule is changed again. The production system is configured to perform processing in accordance with the organized collation order.

[Action]

When the information in the work storage means and the rule group in the rule storage means are collated, the rule groups are collated in a fixed order. When the collation fails due to the collation execution, the collation prohibition flag is set in the rule flag corresponding to the rule until the collation for each rule is completed.
On the other hand, when the collation is successful, the content of execution of the rule is executed and the process proceeds to the next collation cycle. That is, in the first matching cycle, when a rule that succeeds in matching occurs, the second matching cycle is started. In the second collation cycle, the process for prohibiting collation is executed for the rule in which the collation prohibition flag is set in the first collation cycle. Therefore, in the second collation cycle, the first collation cycle is executed. Matching starts from the rule that was successfully matched in. The same processing as the processing in the first matching cycle is executed also in the transition to the second matching cycle, and when each rule fails in matching continuously, the processing ends. Further, when the rule group has been matched at least once, only the rule that has been successfully matched is selected from the rule groups, and the selected rule group is changed to a higher rank in the matching order. Then, after the collation order is changed, the processing is executed according to the reorganized collation order.
At this time, if the same problem is processed again, the number of collation failures can be reduced as compared with the case where the collation order is not reorganized.

〔Example〕

 An embodiment of the present invention will be described below with reference to FIG.

As shown in FIG. 1, the production system in this embodiment has an initial data input section 31, a work storage section 3
2, a rule interpreter (interpretation execution unit) 33, a rule storage unit 34, a rule flag storage unit 35, a collation failure cycle storage unit 36, a data output unit 37, and a control unit 38, and each unit is controlled by the control unit 38. The processing is executed according to the command.

The initial data input unit 31 is adapted to input the information about the function of the circuit elements of the semiconductor integrated circuit and the connection relation between the respective circuit elements according to the Prolog language. For example, as shown in FIG.
41, 42, AND gates 43, 44, 45, 46, O
When the mathematical logic composed of the R gates 47 and 48 is equivalently converted into a circuit that can be realized as a circuit element of a semiconductor integrated circuit, the function of each circuit element shown in FIG. Relationships are entered in the prologue language shown in FIG. Then, the initial data is stored as a working memory wm (working memory) in the working storage unit 32 as working storage means. In the working memory wm, the first and and, inv and or of the first element represent the logic type of the gate, the second element represents the node number of the input terminal or the node name list, and the third and elements are the node numbers of the output terminals. Alternatively, it represents a node name.

The rule storage unit 34 as a rule storage unit stores a precondition for equivalently converting the information about the mathematical logic shown in FIG. 2 into a CMOS logic circuit according to a list of character strings by symbols and variables. And a rule group including an execution unit that stores the execution contents when the condition of the precondition unit is satisfied according to a list of character strings. When the rule group is composed of 20 items of rules, these rules are stored according to the if-then format prolog language. After if, the information about the function of the logical element of the mathematical logic to be subjected to the equivalent conversion and the connection relationship between the respective logical elements is described as a precondition part in the form of the node information of the list as a variable, The prolog language is used to assign the same node number to the same variable.

Further, after "then", the execution content when the condition of the precondition section is satisfied (when collation is successful) as the execution section (a program in a prolog language for updating the content of the work memory stored in the work memory 32) is described. Has been done.

For example, of the 20 item rules, the rule 5 has a fourth rule.
As shown in the figure, rules for equivalent conversion of the mathematical logic shown in FIG. 4 (b) into the CMOS logic circuit shown in FIG. 4 (c) are described. Similarly, rule 9 describes a rule for converting the mathematical logic shown in (e) into the logic circuit shown in (f), and rule 11 shows in (h). A rule for equivalently converting the mathematical logic shown in (i) into the CMOS logic circuit shown in (i) is described. In Rule 17, the mathematical logic shown in (k) is converted into the CM shown in (l).
A rule for equivalent conversion into an OS logic circuit is described.

The rule flag storage unit 35 has, as a rule flag storage unit, a rule flag group associated with each rule of the rule storage unit 34, and stores the matching result of each rule in each rule flag. For example, the collation success flag OK is stored when the collation succeeds because the precondition of the rule is satisfied, and the collation prohibition flag NG is stored when the collation fails.

The collation failure cycle storage unit 36 stores the rule for which collation failed during each collation cycle and its cycle number in association with each other. Further, the data output unit 37 is adapted to display the connection information of the circuit stored in the working storage unit 32 as data.

The rule interpreter 33 is configured as an interpretation executing means, and sequentially collates the information stored in the work storage unit 32 with the preconditions of each rule in the rule storage unit 34 in each collation cycle. Then, the rule storage unit 34
When the matching is performed, only the first successful rule is executed in the matching cycle to update the information in the working storage unit 32 according to the conclusion of the rule. , The process shifts to the next matching cycle. On the other hand, when the collation fails, the collation prohibition flag is set in the rule flag corresponding to the rule until the collation for each rule is completed, and in the subsequent collation cycle, the rule and the working storage unit in which the collation prohibition flag is set are set. The process of prohibiting collation with the information of 32 is executed.

Next, the operation of this embodiment will be described based on the flow chart of FIG.

First, the information about the mathematical logic circuit shown in FIG. 2 is input to the initial data input unit 31 as the initial data by the net list shown in FIG. 3 (step 100). After this, the initial data input unit 31 is instructed by the control unit 38.
The data input to is transferred to the work storage unit 32 (step 101).

Next, the cycle counter 1 for counting the rule matching cycle is initialized (step 102), and all rule flags are set to OK (step 103). Thereafter, the rule pointer N indicating the item number of the rule is set to 1 (step 104).

Next, the rule flag F (1) corresponding to N = 1 is extracted from the rule flag group of the rule flag storage unit 35 (step 105). In this case, since the rule flags are all set to OK, the rule of N = 1 is taken out (steps 106 and 107). Next, the list of the preconditions stored in the rule of N = 1 and the working storage unit The collation with the work memory contents stored in 22 is executed (step 108). When the collation fails, NG is set in the rule flag F (1) (steps 109 and 112), and the current collation cycle 1 is substituted into the counter C (n) of the collation failure cycle storage (step 113).

At this stage, since OK is stored in the rule flags F (2) to F (20), the process proceeds from step 114 to step 117, and the rule pointer is incremented by 1 and set to 2. To do. This value is the total number of rules N
Since it is smaller than 20, the process returns to the process of step 105 to move to the next rule and application after the process of step 118.

In this case, since the value of the rule pointer is set to 2, the rule flag F (2) is taken out. The value of rule flag F (2) is set to OK, so rule 2
Is taken out (step 107) and the rule 2 is checked (step 108). When the collation for rule 2 also fails, the same process as that for rule 1 is performed.

As a result of such processing, as shown in FIG. 6A, when the collation from rule 1 to rule 4 fails, NG is stored in all of the rule flags F (1) to F (4). The current collation cycle number 1 is substituted into the collation failure cycle memory C (1) to C (4).

Next, when the rule 5 is taken out and the matching with the rule 5 is successful, the contents of the condition part of the rule 5 are embodied as follows.

[[And, [1000, 1001, 2], 2002] [and, [1000, 1001, 1002], 2003], [not match
[1000, 1001, 2], [1000, 1001, 1002]], [intersect [1000, 1001, 2], [1000, 1001, 100]
2], [1000, 1001]] [num of atom, [1000, 1001], 2] [not match, 2, 0], [not match, 2, 1]] where not match is a function that checks whether two lists are different, and intersect is a function that finds the common atom of two lists and returns it to the third argument.

After that, the execution unit is executed, and the mathematical logic circuit shown in FIG. 4B is equivalently converted into the CMOS logic circuit shown in FIG. 4C (step 110). After that, the routine proceeds to step 121, the collation cycle counter 1 is incremented, and the routine proceeds to the next collation cycle 2 (step 104).

In verification cycle 2, rule flags F (1) to F (4) are set to N
Since it is G, the collation is started from rule 5 (step 106, step 111, step 106, step 1).
11 ... Step 106, Step 106). When the collation with rule 5 fails, the rule flag F (5) is set to N.
G is set (steps 108, 109, 112), and the current collation cycle number 2 is substituted into the collation failure cycle memory C (5) (step 113). After this step 114,11
The collation processing of the next rule shifts via 7, 118, 105, but since the rule flags F (1) to F (5) are NG,
The collation starts from the rule 6 whose rule flag is OK.

When all of the rules 6 to 10 have failed to be matched, the rule flags F (6) to F (10) are set to NG as shown in FIG. 6 (a).

When the rule 11 succeeds in the collation, the next collation cycle 3 starts (step 121). In the matching cycle 3, the same processing as described above is performed, and rules 11 to 1 are executed.
When the collation with No. 6 fails and the collation with Rule 17 succeeds, the process proceeds to the next collation cycle 4. As shown in FIG. 6A, when the collation with the rule 17 is successful in the collation cycle 4, the next collation cycle 5 is started at this point. When the rule 17 is successfully verified, the mathematical logic circuit shown in (k) of FIG. 4 is equivalently converted into the CMOS logic circuit shown in (l).

In the collation cycle 5, when all the collations for the rules 17 to 20 have failed, the process proceeds to the next collation cycle 6. In this case, the collation of the rules that failed to be applied during the previous collation cycle in one collation cycle is prohibited, and the termination of the process is determined when all the rule flags become NG (steps 114 and 115).

As the end determination condition, a condition that the difference between the values of the collation failure cycle memories C (1) to C (20) provided for each rule one to one is 1 or less is used. For example, as shown in collation cycles 8 and 9, if all the rules fail in succession, it is determined that there is no collable rule, and the process ends.

On the other hand, if the content of the matching cycle memory is not less than 1, the cycle counter is incremented by 1 to indicate that the rule matching has not failed in succession for all rules (step 110). , Move to the next matching cycle. In this case, the process proceeds to step 120, and the value of the rule flag of the rule corresponding to the stored cycle number other than the one having the largest cycle number in the collation cycle storage is returned from NG to OK. That is, when the collation fails, the collation prohibition flag is set in the rule flag corresponding to the rule until the collation for each rule completes one cycle. Therefore, when shifting from the collation cycle 5 to the collation cycle 6, The value of the rule flag for is reset from NG to OK.

In the matching cycle 6, when all the matching with the rules 1 to 8 fails, NG is substituted into the rule flags of these rules. After this, when the collation against the rule 9 is successful, a process for equivalently converting the mathematical logic circuit shown in (e) of FIG. 4 into the CMOS logic circuit shown in (f) is performed. Then, after this, the process goes to the verification cycle 7, and when the verification against the rule 9 is successful again, the same processing as described above is performed. The collation with respect to this rule 9 is unsuccessful in the first collation cycle, but new information is generated by updating the work content in the first collation cycle with respect to each rule,
This means that the matching of rule 9 has succeeded for the information.

By the above processing, the contents of the working memory shown in FIG. 3 are converted into the contents shown in FIG. 8, and the mathematical logic circuit shown in FIG. 2 is equivalently converted into the CMOS logic circuit shown in FIG. To be done. Here, 50, 52 and 57 indicate NOR gates, 51, 53, 55 and 56 indicate AND gates, and 54 and 58 indicate inverters.

As described above, in the present embodiment, the collation for the rule group is executed, and when the collation is successful, the execution content of the rule that succeeds first in the collation cycle is executed and the process in the next collation cycle is performed, When the collation fails, the rule flag corresponding to the rule is set to NG until the rule is completely collated, and in the subsequent collation cycle, NG is set to prohibit the collation to the set rule. Since it is not necessary to perform collation for all rules in each collation cycle, it is not necessary to collate the blank portion shown in FIG. 6A, and the speed can be increased. In addition, in FIG. 6, a cross indicates a collation failure, and a circle indicates a collation success.

Further, when comparing the number of collations between the production system of the present embodiment and the conventional simple production system, as shown by the characteristic A in FIG. 13, according to the production system of the present embodiment, the conventional simple system is used. It was confirmed that the speed was about 1.7 times faster than the production system.

Next, another embodiment of this embodiment will be described based on the flow chart of FIG.

In the present embodiment, after the cycle counter is set to 1 (step 200), the matching cycle number and the number of the rule that has succeeded in matching are set in the rule matching processing (step 201) by the same processing as the above embodiment. Working memory 32
Are sequentially stored (step 202). This process is continued until the end condition is satisfied (steps 203 and 204), and in the working memory, as shown in FIG. 10, the information of the collation cycle number and the rule number collated in that cycle is cycled (cycle). ) Listed by predicate. FIG. 10 shows the processing contents shown in FIG. 6 (a), in which the rules 5, 11, 17, 17, 17, 9, 9 are used for matching in the matching cycles 1, 2, 3, 4, 6, 7. Successful is listed, and in the matching cycles 5, 8 and 9, no successful rule is listed.

When the end condition is satisfied, the learning process (step 20
Go to step 5) (step 205). This processing is performed according to the flow chart shown in FIG.

In FIG. 11, first, a process of substituting the number of matching cycles required for the equivalent conversion process into Lmax is performed (step 30).
0). In this embodiment, 9 is substituted for Lmax. Next, 1 is assigned to the variable n (step 301). 2 in variable m
Is substituted (step 302). After this, the cycle predicate whose matching cycle number corresponds to the variables n and m is referred to (step 303), and the values of the rule numbers Rn and Rm are checked. That is, the value of the cycle predicate of the collation cycle numbers 1 and 2 is checked.

First, in step 305, it is checked whether or not Rn is an invalid number "1". To see if.

When Rm corresponds to the invalid number 1, the process proceeds to step 306, and when Rm does not correspond to the invalid number 1, step 307.
Then, the magnitude of Rn and Rm is compared. Since Rn = 5 and Rm = 11 when n = 1, the process proceeds to step 308 after step 307. Then, 1 is added to the variable n, and the same processing is continued until n exceeds Lmax (step 309).

On the other hand, in the size comparison of step 307, Rn is Rm
If it is larger, the process moves to step 311, and the Rn-th rule is moved one position behind the Rn-th rule. For example, as shown in FIG. 6A, in the matching cycle 6, even after the matching with respect to the rule group has been completed, a new matching rule 9 is generated from the unsuccessful matching in the previous matching cycle. In this case, the collation order of the rule 9 is changed immediately after the rule 17 that was successfully collated last in the first collation cycle. That is, as shown in FIG. 6B, the rule 9 is changed immediately after the rule 17, and the collation order of the rules is reorganized.

When the matching process is performed on the same thing after performing the learning process in the present embodiment, it is possible to reduce the number of cycles and the number of matching failures compared to those of the above-described embodiments.
That is, the number of collation cycles can be reduced from 9 cycles to 8 cycles, and the collation failure cycle can be reduced as shown by the characteristic B of FIG. 13, which is about 2 times less than that of the conventional simple production system. 0.5 times faster.

Next, the processing for changing the order of the rules more efficiently by using the cycle predicate obtained in the above embodiment will be explained based on the flow chart of FIG.

First, the value of the rule pointer p is initialized to 1 in order to give the position of the rule after being reorganized according to the above embodiment (step 400). Next, the maximum number of cycles reorganized by the above-described embodiment is substituted into the variable Lmax (step 401). In this embodiment, the value of Lmax is 8.

Next, the variable n is initialized to 1 (step 402), and the variable m is initialized to 2 (step 403). Next, the cycle predicate corresponding to the cycle numbers n and m is taken out (steps 404 and 405). It is assumed that this cycle predicate is registered in the working memory in the course of processing of the above embodiment. That is, in the matching cycles 1 to 5,
The values 1, 17, 17, 9, 9 are substituted, and the verification cycle 7, 8 is substituted with the invalid number 1.

Next, it is checked whether Rn corresponds to the invalid number 1 (step 406), and further it is checked whether Rm and Rn are equal (step 407). When n = 1, Rn = R1 =
5 and Rn = R ₂ = 11. Therefore, after steps 406 and 407, the process proceeds to step 410, where n
Is incremented by 1 and the rule 5 is moved to the position of the value 1 of the rule pointer p (step 413). That is, as shown in FIG. 6C, the rule 5 is positioned at the beginning of the matching cycle 1. After this, the value of the rule pointer p is incremented by 1, and the process proceeds to step 411. In this case, the value of n is
Since it is less than or equal to Lmax, the process returns to step 403 and the same process as the above-mentioned process is performed.

After this, when Rn corresponds to the invalid number 1, the variable n
Is incremented by 1 (step 408) and the process proceeds to step 411. On the other hand, when Rn and Rm are equal, 2 is added to the value of the variable n and the processing of step 413 is executed.

By performing the above processing, the rules 11, 17, and 9 are respectively changed to positions higher in the collation order as shown in (c) of FIG.

In the present embodiment, the parts that have succeeded in the collation are reorganized to the higher rank of the collation order, so that when the same problem is dealt with, the number of collation failures can be further reduced as compared with the above-mentioned respective embodiments. That is, in this embodiment, as shown by the characteristic C in FIG. 13, it was confirmed that the speed could be increased by about 3.6 times as compared with the conventional production system.

〔The invention's effect〕

According to the present invention, the rule collating order is reorganized according to the rule collating result, which can contribute to the speedup of the production system.

[Brief description of drawings]

FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is a block diagram of a mathematical logic circuit, FIG. 3 is a diagram for explaining connection information of the circuit shown in FIG. 2, and FIG. Is a configuration diagram of a rule group, FIG. 5 is a flow chart for explaining the operation of the first embodiment of the present invention, FIG. 6 is a diagram for explaining the collation content of the device according to the present invention, and FIG. FIG. 8 is a block diagram of a logic circuit equivalently converted by the device according to the present invention, FIG. 8 is a diagram for connecting connection information of the circuit shown in FIG. 7, and FIG. 9 is a second embodiment of the present invention. Float chart to explain, first
FIG. 0 is an explanatory diagram of the structure of the cycle predicate, FIG. 11 is a flow chart for explaining the contents of the learning process shown in FIG. 9,
FIG. 12 is a flow chart for explaining the third embodiment of the present invention, and FIG. 13 is a diagram for comparing the number of collations between the conventional simple production system and the production system according to the present invention. . 31 ... Initial data input unit, 32 ... Work storage unit, 33
...... Rule interpreter, 34 ...... Rule storage unit, 35
...... Rule flag storage unit, 36 …… collation failure cycle storage unit, 37 …… data output unit, 38 …… control unit.

Claims (1)

[Claims] 1. A work storage unit for storing information about a conversion target, and a precondition section and a precondition for storing a precondition for converting the information about the conversion target into new information according to a list of character strings by symbols and variables. Rule storage means for storing the execution contents when a condition of a section is satisfied according to a list of character strings, and a rule storage unit for storing a rule group including an execution unit in association with a collation order; Correspond to each rule in the rule storage means and an interpretation execution means for sequentially collating conditions with each other in each collation cycle, executing the execution content of the rule for which the collation succeeds, and updating the information in the working storage means according to the conclusion of the rule. And a rule flag storage unit that stores the collation result of each rule in each rule flag. When collation fails for a group of rules according to the collation order and the collation fails, the rule flag corresponding to the rule is prohibited from collating until the rule with the highest collation order has reached the lowest rule. When the flag is set and the collation succeeds, the process until the first collation succeeds is regarded as one collation cycle, the execution content of the rule that succeeds first in the collation cycle is executed, and the process proceeds to the process of the next collation cycle. Then, in the next collation cycle, the collation of the rule in which the collation prohibition flag is set and the information in the working storage means is prohibited, and the collation is started from the rule that succeeded in the collation in the previous collation cycle.
Further, after at least one round of matching with the rule group, only the rule that succeeds in matching is selected from the rule group, the selected rule group is changed to a higher rank of the matching order, and after the matching order is changed, the rule is changed again. A production system characterized by performing processing in accordance with the organized collation order.