JPH0287232A - Parallel executing system for production system - Google Patents

Abstract

PURPOSE:To reduce the amount of calculation and to execute processing at a high speed by executing interference detection with the partial interference detected result of another unadjusted processor after a partial interference detecting phase is finished and executing instantiation to be selected by this detecting phase. CONSTITUTION:In a rule collating part 5 of each processor 4, rule collation is executed while a working memory (WM) control part 2 is referred. Then, the couple of the collated rule and WM is sent from the rule collating part 5 to a partial interference detecting part 6 as instantiation 8. In the partial interference detecting part 6, the interference detection is executed concerning the rule, for which the collation is executed in the same processor. Then, the processor 4, for which the partial interference detection is finished, sends the selected instantiation through a common bus 9 to an interference detecting part 3. The interference detecting part 3 executes the interference detection concerning the rule to be collated in the other processor, which can not be detected by the partial interference detecting part 6 of the certain processor. Thus, the amount of the calculation is reduced and a production system is executed at the high speed.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a production system, and for details, refer to 5.
This paper relates to a parallel execution method for a production system that aims to speed up the execution of rules whose conditions have been matched by multiple processors.

[Conventional technology]

A production system is a method for realizing an artificial intelligence (AI) system. The production system consists of a knowledge base that describes knowledge and an inference engine that performs inference.

A knowledge base consists of facts, which are knowledge about facts, and rules, which are knowledge about rules.

Each fact is described as a working memory element (WME) and stored in working memory (WM).

WME is usually written as class name, @character 1: attribute value, . . . , attribute n: attribute value. Furthermore, each rule consists of a condition part (LH3 part) that describes conditions and an action part (RH5 part) that describes execution procedures. The LHS part of a rule consists of one or more condition elements, and one condition element describes one or more condition expressions. The RH8 section consists of one or more execution elements, and operations such as WME update/display and input are described in the execution elements. When there is a WME group that satisfies all the conditional expressions of all the conditional elements in the LH8 part of the rule, L
It is said that the H3 section was satisfied by the WME group.

The inference engine performs inference by repeating the matching phase, conflict resolution phase, and rule execution phase. This series of operations is called a cognitive cycle. In the matching phase, all WMEs are checked to see if they satisfy the conditional expressions described in the condition elements of the LH3 part of all rules, and the WMEs that satisfy the LH5 part and the rules that are satisfied by them are checked. Generate a set of tuples. This set is called an instantiation, and the set consisting of the instantiations is called a conflict set. In the conflict resolution phase, only one instantiation to be executed is selected from the conflict set. The rule execution unit applies the RH5 portion of the selected rule to the WME group in the instantiation selected in the conflict resolution phase.

Conventionally, as an execution method to speed up production systems, a method has been proposed in which multiple instantiations are selected from a competitive set and rules are executed in parallel to match a certain sequential execution result (@ Journal of the Society of Information and Communication Engineers Dvo1.J 71-D N (13pp
, 567-576 1988.3 Ishida: Analysis of parallel execution possibility of production systems). This method will be briefly explained below.

If the following relationship exists between two rules, the results of parallel execution of these rules will not match any sequential execution results.

■ When the WME to be deleted in Rule 1 is set as a conditional element in Rule 2 ■ When the WME to be generated in Rule 2 is set as a not conditional element (true if that WME does not exist) in Rule 2 ■ When the WME is generated in Rule 1 and the rule Common WM to be deleted in 2
When E exists, these relationships are called rule interference, and when selecting multiple instantiations from a competitive set, selections must be made so that no rule interference occurs between any two rules. Therefore, when executing rules in parallel, a phase is required to detect rule interference.
If we call this the interference detection phase, the production system's cognitive cycle will be in the form of matching phase → interference detection phase → execution phase.

Next, parallel execution using interference detection will be explained using examples. This N uses a common WM that can be accessed by all processors. First, it is assumed that the WME stored in the initial WM (WMO) is (at b, c) and there is a first-order rule.

Rule 1: I Fa, THE N del
ete b rule 2: I F b, THEN
delete a rule 3: I F c, TH
EN create d FIG. 3 is an example of sequential execution. In sequential execution 1 of (a), rule 1 is executed first, and b, which is a conditional element of rule 2, is deleted, so rule 2 cannot be executed. Therefore, the next rule to be executed will be rule 3, and the sequential execution result will be (a, b).

Also, in sequential execution 2 in (b), rule 2 is executed first,
Since a, which is the conditional element of rule 1, is deleted, rule 1
cannot be executed, and in the first cognitive cycle, rule 3 is executed, and the result is (b, d).

FIG. 4 shows an example in which rules are unconditionally executed in parallel without interference detection. In this S, all the instantiations checked against the WMO, that is, rule 1, rule 2, and rule 3, are executed simultaneously, and a and b are deleted by executing rule 1 and rule 2.

Generate d by executing rule 3, and the execution result is (d)
becomes. If parallel execution is performed unconditionally in this way, the result will not match any of the sequential execution results shown in FIG.

FIG. 5 shows an example in which rules selected as a result of interference detection are executed in parallel. Rules 1, 2.3 to be checked against WMO satisfy the condition (2) for rules 1 and 2 to cause interference detection. Therefore, in this case, either rule 1 or rule 2 is excluded from the selection candidates, and the rule set after interference detection is (1
): (Rule 1, Rule 3) or (2): (Rule 2. Rule 3). There is no priority among these rule sets, and it does not matter which rule set is selected. FIG. 5 shows the case where rule set (1) is selected and executed in parallel. By executing rules 1 and 3, WME of WMO: b and c are changed at the same time, and the execution result becomes (a, c), which matches the result of sequential execution 1 in FIG. 3(a).

[Problem to be solved by the invention]

As explained above, in a production system, interference detection must be performed when parallel execution is performed, but there is a problem that the amount of calculation required for this interference detection is large. Now, assuming that the total number of rules is n, and one instance is matched per rule (the same applies below), in the interference detection phase, 2
In order to detect rule interference between rules, the amount of calculation in the interference detection phase is nC,=n (n-1)
/2. In other words, the amount of calculation on the order of n2 is required.

As for the number of rules in the production system.

Since it is not uncommon for the number of rules to be several hundred or more, the overhead caused by the interference detection phase may actually make it slower than the sequential execution method.

Therefore, one possible method for performing interference detection at high speed is to limit the rules for performing interference detection. first,
During rule compilation, rules that may cause interference (interference rules) are checked by checking the condition and execution parts of the rules.In the interference detection phase, WME checks only the interference rules. Check if they are the same. According to this method, when the number of interference rules is m on average per rule, the amount of calculation in the interference detection phase is nm/2. The reason why it is set to 1/2 here is that detection can be performed using either one of the two rules. Therefore, it is effective if n>m, but in reality m is often large in proportion to n,
In the end, it ended up being on the order of n2. The amount of calculation is not reduced.

As described above, in the conventional parallel execution method using interference detection, the amount of calculation in the interference detection phase increases as the number of rules increases, resulting in a problem that the execution becomes slower than sequential execution.

An object of the present invention is to provide a high-speed parallel execution method for a production system by partially performing interference detection on the matching results of each processor, narrowing down the instantiations, and reducing the execution time of the interference detection phase. It's about doing.

[Means to solve the problem]

In order to achieve the above object, the present invention performs interference detection on the matching results of each processor (hereinafter referred to as 1 partial interference detection) after completing the matching phase in each processor and before performing the interference detection phase. After the partial interference detection phase ends, interference detection is performed with partial interference detection results of other processors that were not investigated in the partial interference detection, and the instantiation selected in the interference detection phase is executed. It is something.

[For production]

The parallel execution method usually uses a plurality of processors for parallelization not only in the rule execution phase but also in the collation phase. Therefore, the results of the matching phase are obtained for each processor.

In the present invention, after executing rule matching in each processor, interference detection is performed partially on the matching results of the processor to narrow down the instantiations.

Let us calculate the amount of calculation required for interference detection in the method of the present invention. In this case, if two processors are used, the average number of matching rules per processor is □, so the amount of calculation for one partial interference detection is as follows. Next, in the interference detection phase, the amount of computation per p1 processor is p x for partial interference detection, accessing (p-1) processors, and so on. Therefore, for all processors, the number of interference detections in the present invention method is reduced by 2 (px)'' as shown above.From this equation, the higher the number of processors p and the degree of refinement of rules in partial interference detection It can be seen that the invented method is effective.In fact, as one of the parallel methods in the matching phase, it is possible to allocate a group of rules that cause interference to the same processor and perform matching, so this matching method It can be seen that in one-part interference detection using , the one-hydraulic formula becomes more effective if the number of rules can be narrowed down to one digit.

Next, as a modification of the method of the present invention, it is conceivable to select a certain rule preferentially in the interference detection phase.

In fact, it doesn't matter which rule you choose when it comes to rules that cause rule interference.

All selected instantiations of the processor for which partial interference detection has been completed first are executed in the execution phase. That is, the processor moves immediately to the execution phase without performing the interference detection phase. Executed rules are stored in memory that can be accessed by all processors. Next, the processor that has completed the partial interference detection uses the 1 partial interference detection result as follows.
Select and execute an instantiation that does not interfere with rules that have already been executed.

The difference between this method and the previous method is that interference detection does not require partial interference detection results from other processors. In the above method, since partial interference detection results of other processors are required, even if one partial interference detection ends early, interference detection cannot be performed until all processors complete partial interference detection. Furthermore, even after interference detection has started, all processors access other processors at the same time, so communication conflicts are likely to occur where the communication line connecting the processors is being used for communication by other processors. In this scheme, each processor can perform the interference detection phase by referencing an instantiation in a common memory, regardless of the execution state of other processors.

Furthermore, since the timing of transition to the interference detection phase is different for each processor, communication conflicts are less likely to occur. In this way, if some of the interference rules are selected preferentially, there is no need to synchronize in the interference detection phase.

Able to execute cognitive cycles at high speed.

〔Example〕

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

FIG. 1 is a block diagram for explaining one embodiment of the system of the present invention. In FIG. 1, a production system execution device 1 includes a working memory (WM) management section 2. It is composed of an interference detection section 3 and several processors 4.

Each processor 4 includes a rule matching section 5 and a partial interference detection section 6.
．． It is composed of a rule execution section 7.

The rule matching unit 5 of each processor 4 performs rule matching while referring to the WM management unit 2. The WM management unit 2 stores a common memory (
WM). The matched set of rules and WMEs is sent from the rule matching unit 5 to the partial interference detection unit 6 as an instantiation 8. In the partial interference detection section 6,
Interference detection is performed for rules that are matched by the same processor.

After completing the partial interference detection, the processor 4 transfers the selected instantiation to the interference detection unit 3 via the common bus 9.
send to The interference detection unit 3 performs rule interference detection when instantiations are received from all the processors 4. That is, the partial interference detection unit 6 of a certain processor
could not be detected. Interference detection is performed for rules that are checked in other processors. Interference detection section 3
may be accessible from all processors, and the communication method between each processor 4 and the interference detection unit 3 may use a communication line in addition to the common bus 9.

After the interference detection is completed, the selected instantiation is notified to the rule execution unit 7 of each processor 4. The rule execution unit 7 executes the rules and sends the WME information 10 to be newly added or deleted to the WM management unit 2. The WM management unit 2 rewrites the WM for the WME.

The above recognition cycle is repeated until all processors 4 run out of rules to check.

FIG. 2 shows a block diagram of an embodiment in which an interference detection section 3 is provided in each processor 4 and some rules are selected with priority. The configuration of the production system execution device 1 is basically the same as that shown in FIG. 1, but instead of having the interference detection section 3 in each processor, a rule buffer storage section 11 is provided in common to each processor 4.

Each processor 4 accesses the rule buffer storage unit 11 when partial interference detection is completed.

Here, the rule buffer storage section 11 can be accessed from all processors, and the communication method between each processor 4 and the rule buffer storage section 11 may be by using the common bus 9 or by using a communication line. good.

If nothing is written in the rule buffer storage section 11, the processor 4 sends all the instantiations selected by the partial interference detection section 6 to the rule buffer storage section 11, and skips the execution of the interference detection section 3. , these rules are executed in the rule execution unit 7. If some instantiations are written in the rule buffer storage section 11, the interference detection section 3 of the processor 4 selects an instantiation that does not interfere with these instantiations. Further, the selected instantiations are written into the rule buffer storage section 11, and the rule execution section 7 executes these rules.

〔Effect of the invention〕

As described above, according to the present invention, compared to the parallel execution method of conventional production systems, by performing partial interference detection, the amount of calculation required for interference detection is reduced, and the production system can be run at high speed. It has the advantage of being able to be executed.

[Brief explanation of drawings]

1 and 2 are block diagrams for explaining one embodiment of the present invention, and FIGS. 3, 4, and 5 are diagrams for explaining the execution method of a conventional production system. 6 1...Production system execution device, 2...
WM management section, 3... interference detection section. 4... Processor, 5... Rule matching unit, 6...
・Partial interference detection unit, 7... Rule execution unit, 9...
common bus, 11... rule buffer storage section; Average J1] Award 1 (α9 悉二疋寅い弯”C))) Is it a Kaiinu ite?

Claims (2)

[Claims] (1) In a production system in which a recognition cycle is executed by a plurality of processors, a partial interference detection phase in which, after executing rule matching in each processor, interference detection is performed on the matching results of the processor;
After completing partial interference detection in all processors, an interference detection phase is provided in which interference is detected between the partial interference detection results and the partial interference detection results of other processors, and the instance selected in the interference detection phase is A parallel execution method for production systems characterized by (2) In the above interference detection phase, the processor whose partial interference detection phase is completed first executes all the selected instantiations, and the processor whose partial interference detection phase is subsequently completed executes the partial interference detection results. 2. The parallel execution method for a production system according to claim 1, wherein an instantiation that does not interfere with an already executed instantiation is selected and executed.