JPH0337780A - Relative rank analyzing system for data driving type processor - Google Patents

Abstract

(57) [Summary] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] <Industrial Application Field> The present invention relates to the relative rank of a non-Neumann type data-driven processor that compiles and executes a source program written in a high-level language into a flow graph-format object program. Regarding analysis method.

<Prior art> Recently, in order to meet the demand for high-speed processing of large amounts of data, hardware configurations have been developed that can perform parallel operations on any number of instructions in a program as soon as their inputs are complete, replacing the sequential processing type Neumann type processor. Research into non-Neumann data-driven processors.

It has been developed and is being put into practical use.

This data-driven processor, as shown in FIG.
Multiple source programs divided and written in a high-level language 1,
1. ... is expressed in the form of a flow graph as shown in FIG. 2. An intermediate object program 2.2. . . and compile these intermediate object programs 2, 2 . ... are simultaneously rank-analyzed and linked into one to generate an execution object program 3, and data-driven calculations are performed based on this execution object program 3. That is, as shown in FIG. 2, each intermediate object program 2 has a plurality of nodes X1,
2. ..., xlO, these nodes are arranged vertically in the order of execution, with the input nodes XI and It is constructed by connecting the outputs with each other with an arc and placing a function call node xlO at the end. Then, the input arcs of the input nodes of the plurality of intermediate object programs 2 having such a configuration and the output arcs of the function call nodes are linked together at once, and the absolute ranks of all the nodes are determined at once, One execution object program 3 is generated.

<Problems to be Solved by the Invention> However, in the conventional method for creating an executable object program using a data-driven processor, a plurality of source programs l written in separate parts are compiled into intermediate object programs 2, and these plural intermediate Since rank analysis (execution order determination) of all nodes is performed at once when object programs 2 are linked together, even if only one source program is to be partially modified, only the intermediate object program will be modified. However, it is necessary to perform rank analysis on all other intermediate object programs that are not related to the modification, and there is a drawback that it takes a long time to generate the execution object program 3.

Therefore, an object of the present invention is to provide a relative rank analysis method for a data-driven processor that can generate an executable object program at high speed by performing relative rank analysis on each intermediate object at the time of compiling each source program. The goal is to provide the following.

<Means for Solving the Problems> In order to achieve the above object, the data-driven processor relative rank analysis method of the present invention compiles a plurality of divided source programs into intermediate objects, and compiles the programs into intermediate objects. Constituent nodes that can be executed simultaneously are arranged in the same rank in the horizontal direction and arranged vertically in the order of execution, and each node is 1. ;In a data-driven processor that ranks the flow graph represented by the intermediate objects connected by arcs to determine the execution order of each node, and then links these intermediate objects into one to generate an execution object. , a variable adding means for giving a variable corresponding to the rank value to the first node of the flow graph represented by the intermediate object, and determining the number of arcs to be input to the node after the first node, and when the number of input arcs is I. Or the number of input arcs is 2
When the rank values of the immediately preceding nodes are equal to each other, give that node the value obtained by adding 1 to the rank value of the immediately preceding node,
When the number of input arcs is 2 and the rank values of the previous nodes are not equal to each other, the value obtained by adding 1 to the larger rank value of the previous node is given to that node, and when the number of input arcs is 3 or more , relative rank value assigning means for assigning the rank value of each immediately preceding node to each arc, and when linking intermediate objects, an absolute rank value corresponding to the execution order of the first node of each intermediate object is set as a variable in the variable assigning means. The present invention is characterized in that it is equipped with a number setting means for counting, thereby speeding up execution object generation.

<Operation> A plurality of divided source programs are compiled into intermediate objects represented by flow graphs, and the following processing is performed on each intermediate object. The variable assigning means assigns a variable corresponding to the rank value to the first node of the flow graph represented by the intermediate object.

Next, the relative rank value assigning means determines the number of arcs to be input to the node after the first node, compares the rank value of the immediately preceding node, and assigns a relative rank value to that node or arc. That is, when the number of input arcs is 1. If the number of input arcs is 2 and the rank values of the previous nodes are equal, add I to the rank value of the previous node to that node, and if the number of input arcs is 2 and the rank values of the previous nodes are equal to each other. If not, the value obtained by adding I to the larger rank value of the immediately preceding node is assigned to that node, and when the number of input arcs is 3 or more, the rank value of the immediately preceding node is assigned to each arc as a relative rank. Give it as a value. thus,
The relative rank value given to each node in the flow graph of each intermediate object includes the above variables, but when linking intermediate objects, the numeral means assigns the absolute rank value corresponding to the execution order of the first node to the above variable. Since the number is set,
Absolute rank values for all nodes are immediately determined. Therefore, when only one source program is partially modified, rank analysis is not necessary because the relative rank values of nodes of intermediate objects in other source programs remain unchanged, and rank analysis is only required for intermediate objects in that source program. Therefore, execution objects can be generated quickly.

<Example> Hereinafter, the present invention will be explained in detail with reference to illustrated embodiments.

FIG. 1 shows an example of a procedure for generating an execution object program for a data-driven processor employing the relative rank analysis method of the present invention. This data-driven processor differs from the conventional example shown in FIG. 5 in which the linking and rank analysis of multiple intermediate object programs are performed simultaneously and collectively.
(abbreviated as source) 1,1. An intermediate object program (hereinafter abbreviated as intermediate object) 2,2. ...
, respectively, and at this point after performing a relative rank analysis of each intermediate object individually, these intermediate objects 2, 2 . ... are linked to one execution object 3.

The data-driven processor has a variable assigning means 9, a relative rank value assigning means, and a number setting means as software in the form of a driving program in order to perform relative rank analysis.

The variable assigning means assigns variables ylly2 and y4 corresponding to the rank values to the first input nodes X1 and 2 in the flow graph of FIG. 2 represented by the intermediate object 2 obtained by compilation, as shown in FIG. give. Further, the relative rank value assigning means applies nodes xl, x3 . ..., determines the number of arcs input to that node for XIO, compares the rank value of the immediately previous node, and gives a relative rank value to that node or arc as follows. That is, when the number of input arcs is 1 or when the number of input arcs is 2 and the rank values of the immediately preceding nodes are equal, the value obtained by adding 1 to the rank value of the immediately preceding node is assigned to that node (see Figure 3.4). nodes X3, X4
, x5 , x6 , x8 , x9), when the number of input arcs is 2 and the rank values of the immediately preceding nodes are not equal to each other, the value obtained by adding 1 to the larger rank value of the immediately preceding node is to the nodes (nodes xl, y in Figure 3.4)
3.X7. y5), when the number of input arcs is 3 or more, the rank value of each immediately preceding node is given to each arc (see node XIO in Figure 3.4) as the relative rank value. Note that the node xlO at the end of FIG. 3 where the number of input arcs is 3 or more is a function call node that outputs the final calculation result, and y3=yl:y in the relative rank value column of FIG.
2 is the larger value on the right side! represents that the value added is the value on the left side, which is the relative rank value. The above-described processing by the variable assigning means and the relative rank assigning means is as shown in the flowchart of FIG.

Furthermore, the above-mentioned numeral setting means can be used for intermediate objects 2, 2 . . . shown in FIG. When linking..., the absolute rank value corresponding to the execution order of the first node (XI, X2) of each intermediate object is set to the variable (yl, y2, y4
). Then, by this number, the third
Based on the table of relative rank values shown in the figure, the absolute rank values of all swords can be quickly determined by simple calculations.

The m-pair rank analysis method using the data-driven processor 1 having the above configuration will be described below with reference to the flowchart shown in FIG.

In step S2, the divided source is compiled and translated into an intermediate object described by a flow graph as shown in FIG. 2, which shows the execution order of each node. Next, in step S2, the first input node X1 is taken out, and the variable adding means gives variables yl and y2 (see FIG. 2.3) as relative rank values to the two input arcs. Then, in step S3, the relative rank value assigning means judges yes because the number of input arcs is 2, and in step S4 judges negative because both input arcs do not have the same rank value, and sets the relative rank value of the input node xl to an unknown value. Determined relative rank value y3 = yl
:Register as y2. Subsequently, in step S9, the result is negative because the node has not been completed, and the process returns to step S2, where the next input node
A variable y4 is assigned as a relative rank value. Furthermore, in step S2, the next node X3 is retrieved, and the node
3, the number of input arcs is 1, so the relative rank value assigning means performs step S3. S6. Proceeding to S7, 1 is added to the rank value y3 of the previous node xl to node X3, and this is set as the relative rank (ffl(y3+1)) of node Relative rank values are given using a similar procedure.

On the other hand, node X7 has 2 input arcs and 3. Since the rank value of 5 is different from y3 + I and y4 + 1, the relative rank value assigning means performs step S3,
S4. Proceed to S5 and undetermined relative rank value y5 = y3
+I: Give y4 + 1 to node X7. what if,
If the input arc of node X7 were connected to node X4 instead of node X5, the rank values of the immediately preceding nodes would both be y3+t, so step S3. S4
．． Proceeding to S7, the relative rank value of this node becomes y3+2. Since the last node xlO is a function calling node with the number of input arcs being 3 or more, the relative rank value assigning means performs step 53S6. Proceed to S8 and each previous node
6, X7, X8X9 rank value y3 + 2, y
5, y3 + 2, and y4 + 2 are registered as relative rank values of each input arc. In this way, the relative rank values of all nodes of each intermediate object are determined as shown in FIG. 3, and the rank analysis of FIG. 1 is completed.

Finally, when linking intermediate objects in Figure 1 at once,
The numeral means is the first node XI, X2 of each intermediate object.
By setting the absolute rank values corresponding to the execution order to the variables y I , y2 , and y4 given to determined quickly.

In this way, in the above embodiment, at the time when the multiple divided sources are compiled into intermediate objects,
After analyzing the relative rank of each intermediate object, these intermediate objects are easily ranked in absolute terms and linked together to create an execution object, so when only one source is partially modified,
Since the relative rank value of the intermediate object of the pond source remains unchanged, rank analysis is not necessary, and only the rank analysis of the intermediate object of the source is required, so the execution object can be generated much faster than in the conventional example. I can do it.

It goes without saying that the present invention is not limited to the illustrated embodiment.

<Effects of the Invention> As is clear from the above explanation, the relative rank analysis method of the data-driven processor of the present invention adds a variable corresponding to the rank value to the first node of the flow graph represented by the intermediate object obtained by compiling each source. a relative rank value assigning means for assigning a rank value to nodes after the first one based on a predetermined algorithm; and a relative rank value assigning means for assigning a rank value to nodes after the first one based on a predetermined algorithm, and an absolute rank value assigned to the above variable corresponding to the execution order when linking each intermediate object Since intermediate objects on both sides are relative indexed in advance, rank analysis of intermediate objects of other sources is no longer necessary when only a specific source is partially corrected. , execution objects can be generated quickly.

[Brief explanation of drawings]

Fig. 1 is a diagram showing an example of an execution object generation procedure using the relative rank analysis method of the present invention, Fig. 2 is a flow graph of an intermediate object, and Fig. 3 is a relative rank value table of each node of the intermediate object. 4 is a flowchart showing the flow of the second generation procedure, and FIG. 5 is a diagram showing the conventional execution object generation procedure. ■ Source program, 2... Intermediate object program, 3... Execution object program. Patent applicant: Sharp Corporation Agent
Patent attorney Maeda Hao and 1 other person Figure 2 Figure 3

Claims (1)

[Claims] (1) Compiling multiple source programs created by dividing each into intermediate objects, arranging the nodes that make up the program that can be executed simultaneously in the same rank horizontally, and arranging them vertically in the order of execution; A data-driven type that determines the execution order of each node by rank-analyzing the flow graph represented by the above-mentioned intermediate objects that connect nodes with each other with arcs, and also generates an execution object by linking these intermediate objects into one. In the processor, a variable assigning means for assigning a variable corresponding to the rank value to the first node of the flow graph represented by the intermediate object, and determining the number of arcs to be input to the node after the first node, and determining whether the number of input arcs is 1. or when the number of input arcs is 2 and the rank values of the previous nodes are equal, the value obtained by adding 1 to the rank value of the previous node is given to that node, and the number of input arcs is 2 and the rank value of the previous node is given to that node are not equal to each other, the value obtained by adding 1 to the larger rank value of the immediately preceding node is given to that node, and when the number of input arcs is 3 or more, the rank value of each immediately preceding node is assigned to each arc. a means for assigning a relative rank value to the
When linking intermediate objects, speeding up execution object generation is achieved by providing a setting means for setting an absolute rank value corresponding to the execution order of the first node of each intermediate object as a variable in the variable adding means. Features a relative rank analysis method for data-driven processors.