JPH0554136B2 - - Google Patents

Description

[Detailed Description of the Invention] [Field of Application of the Invention] The present invention is a knowledge-based system that performs inferences based on specialized knowledge (empirical rules) and facts stored as data in a computer, and is capable of processing large amounts of list data at high speed. This invention relates to a parallel inference method suitable for processing.

[Background of the invention]

The parallel reasoning method of conventional knowledge-based systems is
This method uses memory that can be commonly accessed by each processor (shared memory), and is convenient for this purpose, but it requires a high software and hardware overhead to handle shared memory access contention, and requires more than 10 computers. In this complex system, no performance improvement could be expected due to the access network.
As a conventional parallel inference method, for example, RD
FENNELL, VRLESSER: Parallelism
in Artificial Intelligence Problem Solving:
A Case Study of Hearsay, IE ³ .
Trans. Comput., Feb.1977 is known.

[Purpose of the invention]

The purpose of the present invention is to provide an ultra-high-speed inference method by parallel processing inference in a knowledge-based system written in LISP using several dozen microcomputers. be.

[Summary of the invention]

In order to achieve such an objective, the present invention
The feature is that the memory of each processor is expanded, the shared memory is eliminated, fact data is stored in the expanded memory of each processor, and only new facts are sent simultaneously to all reasoning processors.

[Embodiments of the invention]

An embodiment of the present invention will be described below with reference to FIGS. 1 to 5.

FIGS. 1 and 2 show the system configuration of an embodiment of an apparatus that implements the method of the present invention. FIG. 1 is a schematic diagram of the overall configuration, and FIG. 2 is a detailed diagram of the system.

1 and 2 are microcomputers called an interpreter computer and an inference computer, respectively, and are connected to each other or by, for example, a hexagonal grid bus 4 as shown in FIG.
An interpreter computer 1 is coupled to an input/output device 3 called an inference data input/output device such as a console, a disk, or a process input/output device. The bus may be connected in other shapes such as a rectangular shape.

In addition, as microcomputers 1 and 2,
HMCS68000 etc. can be used.

As shown in FIG. 2, the interpreter computer 1 is composed of an interpreter processor 11 and its local memory 12, and the inference computer 2 is composed of an inference processor 21 and its local memory 22.

FIG. 3 shows an example of the flow of messages between each processor 11 or 21 and between the interpreter processor 11 and the inference data input/output device 3 in the system of this embodiment.

The interpreter processor 11 inputs inference data 51 through the inference data input/output device 3,
An inference result message 55 is output.

In order to perform parallel inference processing, the interpreter processor 11 performs the following for all inference processors 21:
The inference request message 52 and, if necessary, the inference data message 53 are transmitted by broadcast method.

The inference processor 21 returns the inference result as an inference response message 54.

FIG. 4 is an example of the format of the inference request message 52.

The request message flag 521 is a flag indicating that the message is an inference request message 52. The request message serial number 522 is the inference request message 5.
This is a serial number assigned to 2.

The inference data type 523 indicates the content of the inference data 525. For example, it indicates whether the inference data 525 is a known fact (a pointer to) 62 or an empirical rule (a pointer to) 64. The inference data length 524 indicates the length of the inference data, that is, the number of data of the known facts 62 and empirical rules 64 transmitted in this message.

FIG. 5 is an example of the format of the inference data message 53.

The data message flag 531 is a flag indicating that the message is an inferred data message 53.
The inference data message 53 supplements the function of the inference request message 52 in the inference request by transmitting the inference data that reaches a certain amount each time when the amount of inference data 525 necessary for inference is large. be. Response request message serial number 53
2 has such a relationship (that is, the inference data message 53 tries to supplement its function by sending in advance the inference data 536 that has reached a certain amount). be.

The data message serial number 533 is a serial number assigned to the inferred data message 53. This is reset to 0 each time the response request message serial number 532 is updated.

Inference data type 534, inference data length 535,
The inference data 536 is exactly the same as that for the inference request message 52 previously described in FIG.

FIG. 6 is an example of the format of the inference response message 54.

The response message flag 541 is a flag indicating that the message is an inference response message 54. The response request message serial number 542 indicates which inference request the inference response message 54 corresponds to, by the serial number 522 of the inference request message 52 corresponding to the inference request. The response processor number 543 indicates the ID (number) of the inference processor 21 that is the sender of this response message. The response message serial number 544 is the inference response message 54.
This is a serial number assigned to each inference request and independently to each inference processor 21.

The response data type 545 indicates the contents of the response data 547 (new facts, termination information, etc.). The response data length 546 indicates the length of the response data 547, for example, the number of new facts.

FIG. 7 is an example of a map of the local memory 12 of the interpreter processor 11.

The list area 75 is a list of facts, empirical rules, etc., that is, a pointer to the storage location of data such as known facts and empirical rules, and its structure (list structure).
This is an area containing a group of pointers indicating. The full word area 78 is an area for storing the data body (for example, known fact data, empirical rule data) pointed to by the list.

The new fact queue 76 is a queue for storing new facts transmitted by inference response messages from each inference processor 21 in the order of arrival.

The inference result record position table 77 shows the new fact queue 76 of the first new fact for the inference request message 52.
This is a table for finding the relative position (rank) within the table.

FIG. 8 is an example of a map of the local memory 22 of the inference processor 21.

The fact group list (area) 61 and the empirical rule group list (area) 63 are lists of facts, empirical rules, etc. (that is, pointers to storage locations for data such as known facts and empirical rules, and their structures). (a group of pointers indicating a list structure).

FIG. 9 shows an example of the structure of the fact group list 61 and the empirical rule group list 63.

The fact group list 61 is a one-way chain of known facts (pointers to data) 62.

The heuristic rule group list 63 is a one-way chain of heuristic rules (pointers to data) 64. Furthermore, each empirical rule 64 consists of a condition part 65 and a conclusion part 66,
The condition part 65 contains conditions (pointer to condition data)
The conclusion part 66 consists of a one-way chain of conclusions (pointers to conclusion data) 661.

FIG. 10 is a configuration diagram of an example of the new facts queue 76.

In the new fact queue 76 (main body), new facts (pointers to them) 761 are queued in the order in which new facts are received by the inference response message 54.

FIG. 11 shows an example of the configuration of the inference result recording position table 77.

The inference result record position table 77 is a collection of pairs of an inference request message number 770 and a relative position 771 of a new fact generated as a result of inference using this message.

FIGS. 12 and 13 show an example of the processing flow of the interpreter processor and the inference processor, respectively.

The operation of the embodiment of the present invention will be explained below.

For simplicity, forward inference will be explained.

Forward inference processing is performed as follows.

(1) Search the empirical rule to find an empirical rule that makes the known facts satisfy the condition part.

(2) Take the conclusion part of the applicable rule of thumb and examine the group of facts to see if it is a known fact, that is, if a new fact has been discovered.

(3) Store the new fact in the new fact group, add it to the fact group as a known fact, and return to (1).

(4) If no new facts are found, or if the conclusion part requests a stop, terminate the process.

The operation of the embodiment of the present invention in forward inference (hereinafter referred to as inference) is as follows (12th
(see Figure 13).

(1) Inference data 5 from inference data input/output device 3
1 is input (step 201), the interpreter processor 11 creates an inference request message 52 from this data (step 202), and sends it to all inference processors 21 at once (step 203). In order to increase inference efficiency by performing inference all at once, it is also permitted to send inference request message 52 after transmitting inference data message 53 several times.

(2) When the inference processor 21 receives the inference data message 53 (step 301), it stores the known facts (pointers thereof) 62 in the fact group list 61 (step 302). Upon receiving the inference request message, the known facts (pointer to) 62
is stored in the fact group list 61, and then inference is started (step 303).

(3) The inference by the inference processor 21 is as follows.

(i) Extract the empirical rules 64 in order from the head of the empirical rule group list 63 (step 304). When the final rule of thumb 64 is reached, process (iv) is performed.

(ii) The condition part 65 of the extracted empirical rule 64 is
Conditions 651 are extracted in order and checked to see if they are true (step 305). That is,
The known facts (pointers) 62 are taken out in order from the beginning of the fact group list 61 and checked to see if they match the conditions (pointers) 651. Which known fact 6 in fact list 61
In both cases, if the condition 651 does not match, the process returns to step (i) (step 304) and the next empirical rule 64 is executed.
Take out. If there is a known fact 62 that matches the first condition 651 (that is, if the first condition 651 is true), all the conditions 651 in the condition section 65 are sequentially checked.

If there is a condition 651 that is not true, the process returns to step (i) (step 304) and the next empirical rule 64 is extracted. If all the conditions in the condition section 65 are true, then the process (iii) is performed.

(iii) All the conclusions 661 are taken out from the conclusion part 66 of the rule of thumb 64 that has completed checking that all the conditions 651 in the condition part 65 are true, and a new fact 547 is found (step 306).

That is, the conclusions (pointers) 661 are taken out in the order of the beginning of the conclusion part 66, and all known facts 62 in the fact group list 61 are checked to see if they match the known facts (pointers) 62. If it does not match, it will be treated as new fact 547.

If no new fact is found, the process returns to step (i) (step 304) and the next empirical rule 64 is extracted. If found, process (iv) (step 308) is performed.

(iv) The found new fact (pointer) 547, its number 546, and the empirical rule (pointer) 64 from which the new fact 547 was derived are set in the inference response message 54 and transmitted (step 308). If no new facts are found, the inference response message 54 is returned with the number of new facts 546 set to 0 (step 307).

(4) The interpreter processor 11 receives the inference response message 54 from each inference processor 21 (step 204), and if there is a new fact, puts it in the new fact queue 76. However, the relative position within the new fact queue 76 of the first new fact 761 for each inference request message 52 is the new fact relative position 77.
1 in the inference result recording position table 77 (step 205).

The inference response message 54 to the sent inference request message 52 is sent to all inference processors 2.
1 (step 206), if there is no new fact 761 corresponding to this inference request, (5)
(step 209).

If there is this new fact, an inference request message 52 is assembled from all the corresponding new facts 761 based on the new fact queue 76 and the inference request corresponding new fact table 77 (step 207), and all inference processors 21
(Step 203).

The simultaneous transmission method of this new fact 761 is as follows.
In order to improve efficiency, when new facts 761 are collected in excess of a specified number, they are sent all at once to the inference processor 21 as an inference data message 53.
When the inference response message 54 to the already sent inference request message 52 has been received from all the inference processors 21, the unsent new fact 7
It is also conceivable to assemble the inference request message 52 from only the messages 61 and send it all at once. However, in this case, the inference processor 21 processes the new fact (i.e., known fact 536) in the inference data message 53 received during the inference request message 52 processing.
The above-mentioned known fact 536 is added to the fact group list 61 after the inference request process is completed, that is, after the inference response message 54 is sent back, without incorporating it into the fact group list 61 as in (2).
Add to.

(5) The interpreter processor 11 sends the inference result message 55 by editing the inference completion status information and, if necessary, the contents of the new fact queue 76.
is output to the inference data input/output device 3 (step 209).

FIG. 14 is a diagram showing another embodiment of the system configuration for realizing the method of the present invention.

1001 is an interpreter processor, 1002
is a processing device called an inference processor. These processors are connected to a message transmission bus 106.
They are connected by 1.

Reference numeral 1009 denotes an input/output device such as a console typewriter, a display, a process input/output device, etc., which is hereinafter referred to as an inference input/output device. The interpreter processor 1001 is an inference input/output device 100.
9 and a bus 1062.

The interpreter processor 1001 has memory 1
Has 003. The memory 1003 consists of an interpreter-only memory block 1030 and a knowledge list block 1041. The interpreter-only memory block 1030 is connected to the dedicated memory access bus 10.
70, it is a memory block that is read and written only by the interpreter processor 1001.

The inference processor 1002 has an inference memory 100
Has 4. The memory 1004 consists of a memory block 1040 dedicated to the inference processor and a knowledge list block 1041.

The knowledge list block 1041 is read as follows.
Although writes are performed locally from each processor through bus 1071, writes are
68, the interpreter processor 1001
This is performed for all inference processors 1002 at the same time. The arbiter 1005 performs contention processing for reading and writing to the knowledge list block 1041 (writing cannot be performed during reading; the reverse is also true). This can be achieved using dual port memory, etc.

The contents of the knowledge list block 1041 of each processor are all the same.

The operation shown in FIG. 14 will be explained below.

When an inference command is input from an input/output device (referred to as an inference input/output device) 1009 such as a console typewriter, display, or process input/output device, the interpreter processor 10
01 creates inference data from this and transfers it to bus 1.
008 (control line) all processors 100
After issuing a simultaneous write request to the knowledge list block 1041 of the processors 1,1002, all the processors 1001, 1002 are sent via the bus 1008 (data line).
After writing all the necessary inference data into the knowledge list block 1041 of the processors, an inference request is output to all the inference processors via (the control line of) the bus 1008.

Note that the inference request is included in the knowledge list block 1041 as a fact (that is, as one of the data).
This may be written as drive start data based on an empirical rule stored in the memory block 1040 dedicated to the inference processor. In addition, common bus 1008
is a DMA bus for the interpreter processor 1001 and the inference processor 1002. Therefore, the transmission overhead from interpreter processor 1001 to each reasoning processor 1002 is extremely small, and performance can be significantly improved.

All reasoning processors are knowledge list blocks 10
41, that is, without competing memory accesses, inferences are performed in parallel and the results are returned as an inference response message.

The interpreter processor 1001 checks all inference responses returned to the inference request message after responses have been returned from all inference processors or after a certain period of time has elapsed, and if it determines that the inference has been completed, it starts the inference process. The result is output to the inference input/output device 1009 as an inference result message. If it is determined that the inference has not been completed, an inference message is created from the inference response message, the inference request to the inference processor is repeated, and necessary information is saved as the inference result.

FIGS. 15 and 16 show an example of the flow of processing in the interpreter processor and inference processor shown in FIG. 14, respectively.

The differences from the processing flows in FIGS. 12 and 13 are as described above, and the other points are the same as those in FIGS. 12 and 13, so a description thereof will be omitted here.

〔Effect of the invention〕

According to the present invention, multiple microcomputers are connected, list-format knowledge data is distributed in the local memory of each processor, and inference processing using this knowledge data is performed in parallel to avoid memory and bus contention. Since it is possible to configure a LISP machine with built-in functions for knowledge bases, high-intelligence information processing such as practical new knowledge base systems (for example, production systems with more than 500 rules of thumb) can: (1) achieve high performance; (10 times more than conventional minicomputers) (2) Flexible and efficient (3) Low cost (less than the price of conventional minicomputers).

[Brief explanation of drawings]

Figure 1 is a schematic diagram of the configuration of an example of a system that implements the present invention, Figure 2 is a diagram of the configuration of an example of a system that implements the present invention, and Figure 3 shows the data on the bus in the system of Figure 1. Figures 4 to 6, which show the flow, respectively show an example format of an inference request message, an inference data message, and an inference response message.
Figures 7 and 8 are maps of an example of the local memory of the interpreter processor and inference processor, respectively. Figure 9 is a configuration diagram of an example of a fact group list and an empirical rule group list. Figure 10 is an example of a new fact queue. 11 is a configuration diagram of an example of an inference result recording position table, and FIGS. 12 and 13 are flowcharts showing an example of the processing flow of the interpreter processor and inference processor of FIG. 2, respectively.
FIG. 14 is a block diagram of another embodiment of a system implementing the present invention, and FIGS. 15 and 16 are flowcharts showing an example of the processing flow of an interpreter processor and an inference processor, respectively. DESCRIPTION OF SYMBOLS 11...Interpreter processor, 21...Inference processor, 12...Local memory of interpreter processor, 22...Local memory of inference processor, 52...Inference request message, 5
3... Inference data message, 54... Inference response message, 61... Fact group list, 62... Immediately known facts, 63... Empirical rule group list, 64... Empirical rule, 65... Condition part, 66... ...Conclusion part, 651...
...Condition, 661...Conclusion, 76...New facts, 77...Inference result record location table.

Claims (1)

[Claims] 1. In a compound computer system consisting of a plurality of bus-coupled processing units and a memory attached to each processing unit, a specific processing unit receives an inference command, and transmits the inference command to other processing units. The inference request is converted into an inference request that is processed in parallel in parallel, and the inference request is sent to multiple other processing devices all at once. Storing at least a part and fact data related thereto in a dedicated memory attached to the processing device, and checking the fact data to search for applicable heuristic data when the inference request is received. processing, processing for inferring whether a new fact will be generated when the searched fact data is applied, and sending the new fact generated during the inference to the above-mentioned specific processing device and a plurality of other processing devices. After that, a plurality of other processing devices that have received the new fact check the new fact data and repeat the searching process, the inference process, and the sending process, so that the specific processing device A parallel inference method characterized in that the repeated processing is terminated when it is determined that no new fact is transmitted by any of the processing devices, and the specific processing device outputs the obtained new fact as the final result of inference. . 2. A parallel reasoning method according to claim 1, wherein at least a portion of the heuristic data and fact data associated therewith are stored in a dedicated memory in the form of a list linked by pointers. 3 The above-mentioned repeated processing involves editing the inference request data based on the new fact in a specific processing device that has received the new fact generated during the above-mentioned inference, and transmitting the inference request data to multiple other processing devices all at once. The parallel inference method according to claim 1, which includes a process of repeating transmission. 4 The dedicated memory includes a memory block that can be read and written only by a processing device equipped with the memory, and a knowledge list that can be read only by the processing device and written to by a specific processing device different from the processing device. 2. A parallel inference method according to claim 1, comprising: a memory block for storing . 5. The parallel reasoning method according to claim 1, wherein the new fact is sent to the specific processing device and a plurality of other processing devices all at once.