Goal distribution system for parallel type inference computer

[Detailed Description of the Invention]

[Application of the Invention] The present invention relates to a parallel type reasoning computer, and relates to the distribution method of the goal to which the number of processor elements which can operate simultaneously is made to increase by reducing the delivery frequency of the goal between each processor element. [Background of the Invention] With the conventional reasoning computer, successive execution of reasoning is common and it is Oh. The typical processing method is stated to "Edinburgh university artificial intelligence faculty report of research (Dept.of Artificial Intelligence Research Report) No. 39 and No. 40 (1977)" in detail. The problem that processing performance is low in order to perform each reasoning one by one by one processor in such serial type reasoning calculation is Oh. Generally from reasoning of the one goal, a plurality of new goals are derived, and these new goals can be processed in parallel. The international conference concerning the "5th generation computer systems paying attention to this point (1984), Lecture collected papers (Proc.of Int.Conf, on Fifth Generation Computer Systems1984, ICOT), A plurality of processor elements were combined by the network like 479th page - the 489th page" (well-known example), and the proposal of the parallel type reasoning computer that processing performance will be raised has been made by carrying out parallel execution of a plurality of reasoning. With a parallel type reasoning computer, the following two points are a subject and intermediary To have. (1) As many processor elements as possible distribute reasoning, and enlarge the number of the processor elements which carry out parallel operation. (2) Distribute the goal efficiently in the small network of a throughput. (1) and (2) are not unrelated, and since a network throughput is restricted to a certain value in realization, its conquest of the subject of (2) is indispensable to achievement of (1). Now, each processor element is I was sending it. to a pool (it is called Gaul Poole) about the new goal derived as a result of one goal processing as shown to the well-known example by the conventional parallel type reasoning computer, for example. Each processor element accesses Gaul Poole, takes out the goal, and performs reasoning. For this reason, communication between each processor element in a processor element which passes Gaul Poole for every reasoning is needed, and when a network throughput is not enough, the number of the processor elements which can carry out Collating operation will be restricted. Like [ of the example of 30th time of Information Processing Society of Japan national conference proceedings 6C-9 (p. 201) (well-known example) ], It connects with the processor element of the east, the west, south, and north, and forms a reticulated network, The processor element which generated it for the new goal (it is called a self-processor element) -> east processor element -> south processor element -> self-processor element -> By distributing one by one with ........., there is also a conventional example that the network throughput needed will be stopped low. Although the network throughput needed was low stopped by introducing the reticulated network of about 4 connection by the well-known example, a ~1Gb/sec throughput is required and the number of processors which carries out parallel operation was not made greatly enough in the usual network. [Objects of the Invention] The object of the present invention provides the distribution method of the goal which can reduce the frequency of communication between each processor element through a network, and there is in realizing a highly efficient parallel type reasoning computer. [Summary of the Invention] The new goal which arises as a result of goal processing of a processor element is usually 1 or 2 pieces, and there are also many a cases. Therefore, if processing is considered for the generated new goal as the goal for the next processing of a It was done processor element, it is not necessary to deliver the goal to other processor elements via a network. [Example] Hereinafter, one example of the present invention is described in detail. The parallel type reasoning computer can run the program written as an example by a language called Prolog (Prolog) based on first-order predicate logic. The grammar of Prolog, the programming method, and the example program are stated to textbooks, such as Hideyuki Nakajima "Prolog" (Sangyo Tosho Publishing). The example of such a Prolog program is shown in Drawing 2. Drawing 2 of the 1st line reads with a question, saying, "What does Hanako like?" The 2nd line has described a rule. It reads [ "as for X saying / like / Y, X is a child of Z, and I hear that Z likes Y", and ]. ~ of 3rd line the 7th line has described the facts. The program of Drawing 2 is run as follows. Since the 1st-line question is tested by comparison on the fact of ~ of 3rd line the 7th line and the fact to Hanako is not found, the rule of the 2nd line is applied. As a result, the 1st-line question is transposed to "child (Hanako, Z) and liking (Z, Y)", i.e., the question "what Hanako is someone's children and this someone likes." The 1st-line question is called the goal. Next, the new question (goal) of the replaced result compares with Drawing 2 and the fact of ~ of 3rd line the 7th line, and is carried out, and "child (Hanako, Taro) and liking (Taro, baseball)", i.e., "Hanako, are Taro's children, And Taro likes baseball. The result ", and the result "child (Hanako, Kazuko) and liking (Kazuko, book)" are obtained. From the 2nd result, "he liking (Hanako, book)" is obtained for "he liking (Hanako, baseball)" from the 1st result. The example of the present invention is shown in Drawing 1. As a result of passing the goal corresponding to the first question, and "liking (Hanako, A)" to processor element #0 and processing them, "child (Hanako, Taro), liking (Taro, Y)" and "child (Hanako, Kazuko), and the two new goals liking (Kazuko, Y)" are generated. Only the 1st goal is passed to a goal pool between these two new goals, and the 2nd goal is processed by processor element #0. The 1st goal passed to the goal pool is passed to one#n of the processor element under standby, and is processed. The program and data for processing all the goals that can be processed by a system are memorized at a memory place (not shown) common to a system, and each processor accesses this suitably. this example -- the case of a well-known example -- every 2 times -- a line -- transmission to the goal pool from a processor element and the goal pool of the Noodle new goal can decrease transmission of a processor element at a time to one piece, respectively. As a result, since network frequency in use decreases to 3 times from 5 times of a well-known example, only that part can carry out parallel operation of many processor elements. whenever [ of generating of the new goal in a well-known example ] -- a self-processor element -- since the distribution place is cyclically changed with the -> east processor element -> south processor element -> self-processor element, only 1/3 of the new goals which occurred can be confined in a self-processor. namely, network frequency in use -- at most -- it can decrease only to 2/3. Since the one new goal [ at least ] is distributed to a self-processor every one reasoning in the present invention, the confinement rate of the higher goal can be obtained. When generating only the 1 or 2 new goals from one reasoning especially, a difference with a well-known example becomes large, and is effective. [Effect of the Invention] In the example of Drawing 1, although the result was obtained by two goal processings, by the time a result is obtained, ten goal processings or more will usually be needed. In the present invention, one of the new goals generated as a result of goal processing is confined in the processor element which carried out goal processing, without sending to a goal pool via a network. Therefore, in the present invention, network frequency in use can be reduced about [ in conventional ] to 1/10. Therefore, there is an effect which improves performance of a parallel type reasoning computer 10 times.

[Brief Description of the Drawings]

The figure and Drawing 2 where Drawing 1 expressed delivery of the goal between processor elements typically are an example of the program of Prolog. A in Drawing 2 and Drawing 1, X, Y, and X express a variable.