JPS603752A - System for problem resolving parallel processing - Google Patents

Abstract

PURPOSE:To perform a problem resolving processing with parallel execution of a scheduler processor and a partial problem resolving processor by providing the partial problem resolving processor, the scheduler processor, and a basic data holding part. CONSTITUTION:In the data processing system which processes a given problem while referring to problem resolving information (for example, geographic information), one partial problem resolving processor 4 which resolves a designated partial problem while accessing problem resolving information is provided at least. Further, a scheduler processor 3 which indicates the processing order of plural partial problems to which the given problem is divided, and a basic data holding part (auxiliary data base) 2 where basic data used for scheduling are held are provided. These scheduler processor 3 and the problem resilving processor 4 execute the resolving processing of the given problem in parallel.

Description

Detailed Description of the Invention (5) Technical Field of the Invention The present invention relates to a problem-solving parallel processing system, particularly a processing system that processes a given problem while referring to problem-solving information. The present invention relates to a problem solving parallel processing system in which a scheduler processor and a partial problem solving processor execute processing in parallel while dividing a problem into a plurality of partial problems.

Background and Problems of IBI Technology Although the present invention is not limited thereto, for example, in solving a makeshift problem in which queries are made to a data pace using the P delog language, for example, "
Countries bordering the Mediterranean Sea and Asian countries (variable C)
In response to the problem of "Meyo".

Anaviar (C)+:1Cosntry (C)
& Bordert (C,mgditar-ra
naakan) & Co5ntry (C+) & A
Problems are given in the form s1an (Ct) & Border (C, Ct). Note that C and C may be considered to be variables, respectively.

When solving such a makeshift problem, it is necessary to use 5
You need to solve subproblems. That is.

■Country (C)...C is the country.

■ Bordsr (Ct tnsditarrane
an)°--C borders the Mediterranean Sea.

■Country (C1)--Ct is the country.

■ As tan (CI)...C1 is from Asia.

■ Border (C2C1)・・・C and C1
is in contact with.

Partial problems such as those mentioned above are solved by referring to, for example, geographic information on a database. For example =
Country (C) finds one country from the geographic information (one of the problem solving information) on the database, and sets the value of variable C to that country. The following subproblem Bordmr (
Regarding C, mgditgrranean), 1 Since the value of C is already tentatively determined, it is solved by checking whether the fact that country C is in contact with the Mediterranean Sea can be found in the problem solving information. . If you can find it, move on to the next partial problem; if you can't find it, go back to the previous partial problem and look for another country C. In this way, we finally find C9Cl that satisfies all subproblems, and let C be the direct solution.

The process proceeds as described above, but the subproblems do not have to be solved in the order described above. Rather, it is inefficient to adopt the above order because it would mean listing nine countries one after another and checking whether they border the Mediterranean Sea or not. For example, it is more efficient to find one country among those bordering the Mediterranean Sea (bordering countries include not only countries but also the Atlantic Ocean, the Suez Canal, etc.). This is because the number of "things" that touch the Mediterranean Sea is small compared to the number of countries in the world.

Strictly speaking, the efficient solution order is determined by the number of solutions for each subproblem. Of course, the actual number of solutions cannot be determined until the problem is solved, but it can be estimated from information (for example, the number of countries) related to the amount (i.e., quantity or number) of the contents (problem solving information) of the data base. In other words, the number of possibilities that must be considered when solving a subproblem is determined as a ``cost,'' and this is assigned to the subproblem. For example, suppose that we know something like the 5th order as basic data for solving the above-mentioned partial problem. That is.

(a) Regarding Country (C), the number of pieces in one country (
Suppose that the size (size) is r150J, and there can be 300 arguments when selecting one of the 150 countries.

(Regarding 6J As1an (Ct), assume that the number (size) of countries in Asia is rloOJ, and the size of the corresponding argument is r300J as above.

(C) Regarding Border (*i, *z),
Assume that the size is 1900J, the size of the argument corresponding to *l above is r180J, and the size of the argument corresponding to *2 above is r180J.

In this case, the cost related to (α) above is l 150J, and the cost related to (b) above is rlooJ.

Regarding 1c) above, if both *1 and *2 above are unknown (remain variables), the cost is r900.
J, and either *l or *2 above is, for example, US
If it is known like A or Mediterranean, the cost is r900
/180=5J, and if both *l and *2 above are known, the cost is r900/180X180=1
/36J.

(C1 Object and Structure of the Invention The present invention aims to solve a problem while executing the scheduler processor and the partial problem solving processor in parallel while taking the above points into consideration. The problem-solving parallel processing system of the present invention is a data processing system that processes a given problem while referring to two problem-solving information, and at least one sub-problem that solves a specified sub-problem while accessing the problem-solving information. The above-mentioned system is equipped with a solution processor, a scheduler processor that instructs the processing order of each sub-problem that divides the above-mentioned problem into a plurality of parts, and a basic data storage section that holds basic data used for scheduling. The present invention is characterized in that the scheduler processor and the partial problem solving processor execute the given problem solving process in parallel.The following is an example of how to solve the makeshift problem with reference to the drawings. I will explain.

IDI Embodiment of the Invention FIG. 1 shows the configuration of an embodiment of the present invention, and FIG. 12 V%J
1131 tel indicates an example processing mode according to the present invention.

In the N-1 diagram, ■ represents a database in which problem solving information is stored, 2 represents a basic data holding unit according to the present invention, 3 represents a scheduler processor, and 4 represents a partial problem solving processor. There is. , and 5 is a one-part question classification processing function unit, which operates to perform a process of dividing the asked question into a plurality of partial questions.

Reference numeral 6 is a basic data reading unit, which operates to read basic data such as (α), (b), and (61) described above from the basic data holding unit 2. Reference numeral 7 is a cost calculation processing unit.

Works to calculate costs. Reference numeral 8 denotes an interrupt request generating unit 9, which is used when, as a result of the above cost calculation, the partial problem solving processor 4 should select a partial problem different from the partial problem that is currently failing.

This is notified by an interrupt. Further, 9 is a solution notification processing unit which issues an instruction to select a sub-problem to be executed first upon receiving a notification from the 1-sub-problem solving processor 4 that one sub-problem has been solved.

Further, numeral 10 is a list holding unit, which has partial problems that are considered to be executed at the moment in the form of a list.

11 is a 9 problem processing function section.

It operates to solve each partial problem while accessing the database 1. 12 is.

It is an interrupt reception processing section, and operates in response to an interrupt from the scheduler processor 3 to start solving the partial problem to be executed next. Reference numeral 13 denotes a solution notification sending unit, which works to notify the scheduler/processor 3 when one partial problem has been solved.

Hereinafter, a processing mode of an embodiment according to the present invention will be described with reference to "A-2 Figure A), inl, and icl."

(1) For example, when given a makeshift problem as described in 1 in the Background and Problems of Bl Technology column of this specification, the 0-part problem classification processing function unit 3 can solve multiple problems as described in the above column. Extract partial problems.

(2) The basic data holding unit (auxiliary data base) 2 stores basic data as shown in FIG. A basic data reading unit 6 in the scheduler processor 3 reads basic data related to each partial problem.

(3) Then, the cost calculation processing unit 7 calculates the costs corresponding to each of the above partial problems (1), ■, ■, ■, ■, as shown in Figure 2.

The cost of subproblem (2) is r150J. The cost of subproblem (ri) is 15 because the Mediterranean Sea is known. The cost of subproblem ■ is r150J. Subproblem ■
The cost of is rloOJ.

The cost of subproblem (2) is r900J.

(4) Meanwhile, in the two-part problem solving processor 4, the processing order of the nine-part problems is tentatively given to the list holding unit 10 as ■, ■, ■, ■, ■. For Kono,
The problem processing function unit 11 of the processor 4 starts processing to solve the one-part problem. Names of countries such as Afghanistan, Albania, Argentine, etc.
In the same way, we will extract the country.

(5) However, in the above process (3), it is found that the partial problem with the minimum cost is problem (2), and the interrupt request generation unit 8 notifies the processor 4 of this fact.

(6) The processor 4 sends this to the interrupt reception processing unit 12.
Stop the execution of the reception 1 partial problem ■ by .

Start execution of partial problem ■. And list holding unit 1
The contents of 0 are updated.

(7) When the partial problem ■ is solved, the solution notification sending unit 1
The processor 3 is notified of the 3-cigarette.

(3) As a result, the solution notification processing unit 9 in the processor 3 activates the cost calculation processing unit 7.

(9) In this case, the new cost of the 1-part problem ■ is [15
0/300 = l/2J, and the new cost of the 1-part problem (2) is r900/180 = 5. As a result, it can be seen that the one-part problem (2) has the minimum cost. At this time, the processor 4 is executing the two-part problem (1).

Let the execution continue.

0q When subproblem ■ is solved in processor 4,
You will be notified of this.

It can be seen that in the aυ processor 3, the two-part problem ■ has the minimum cost. At this time, since the processor 4 is executing the 9-part problem (2) based on the contents of the list holding unit 1O, the processor 3 issues an interrupt request.

@ As a result, the processor 4 starts the partial problem (■).

When the α-side subproblem ■ is solved, this fact is sent to the processor 3.
will be notified.

0 勺 The cost of this result is r15 in the 1-part problem ■
0/300=V'l, J, and in the 1-part problem ■, r
Since 100/300=1/3J, it can be seen that the cost of the two-part problem (2) is the minimum.

With the Q-resitter force, processor 3 causes processor 4 to execute interrupt 1 partial problem (■).

After processor 4 executes one-part problem (4).

Execute partial problem ■.

Processing is performed as described above. )--In the above description, solving the 9-adjustment problem was explained as an example, but the present invention is not limited thereto.

For example, it goes without saying that the scheduler processor monitors the processing of the 9-part problem solving processor, infers the cause of failure in solving a 2-part problem, and performs control such as providing guidance. The same is true when monitoring whether a partial problem solving processor continues to process only a single problem for a long period of time.

tE) As described in detail, according to the present invention ('i1), for example, when solving a makeshift problem, it becomes possible to execute partial problems in the most efficient order.

In the above explanation, the scheduler processor 3 and the partial problem solving processor 4 have been explained as separate devices, but it goes without saying that they may be executed by a single device in the form of multi-program gamer 1-ming processing. .

[Brief explanation of drawings]

Figure 1 shows one embodiment of the present invention.Figure 12 shows V%J
113+ tel indicates one example processing mode according to the present invention. In the figure, 1 is the database, 2 is the foundation data holding unit, and 3 is the data base.
is a scheduler processor, 4 is a partial problem solving processor, 5 is a partial problem classification processing function unit, 6 is a basic data reading unit, 7 is a cost calculation processing unit, 8 is an interrupt request generation unit, 9 is a solution notification processing unit, 10 is a list holding section, and 11 is a problem processing function section. 12 represents an interrupt reception processing section, and 13 represents a resolution notification transmission section. Patent applicant Fujitsu Limited

Claims (1)

Claims: A data processing system that processes a given problem while referring to problem-solving information, including at least one partial problem-solving processor that solves a designated partial problem while accessing the problem-solving information. A scheduler processor that instructs the processing order of each sub-problem divided into a plurality of parts, and a basic data holding unit that holds basic data used for scheduling, the scheduler processor and the sub-problem A problem-solving parallel processing system characterized in that a problem-solving processor executes the given problem-solving process in parallel.