JPS58149566A - Processing system of optimization for parallel execution of vector operation - 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 (A) Technical Field of the Invention The present invention relates to a parallel execution optimization processing method for vector operations, and in particular to a vector processing processor equipped with a plurality of parallel operation units. In a compiler that generates and supplies a target program from
The present invention relates to a parallel execution optimization processing method for vector operations in which parallel operation units are allocated to minimize the occurrence of empty states in the 61IILt column operation units.

(B) Technical background and problems An example is shown in Figure 1 CA) (elements a1, a2, ... belonging to vector A and elements b1, b2, ... belonging to vector B). By adding each element with..., element C,,C2,...
There are vector processing processors that execute vector instructions such as generating a vector C with . (FIG. 1 FA) In the illustrated case, mask elements m+, mz determine whether or not to perform mutual addition of the first elements.

. . , and the processing shown in FIG. 1(B) as a film is performed.

A data processing system having a vector processing processor that performs the above processing has a system configuration as shown in FIG. 2 as an embodiment.

In the figure, 1 is a main storage device, 2 is a memory control device, 3 is a vector processing processor, 4 is a channel processor,
5 is a large storage device, 6 is a scalar processing circuit section, 7 is a vector processing circuit section, 8-0. 8-1° . . . are floating point data registers, 9-0° 9-1.・・・・・・
10-0.10-1. are vector registers each capable of storing a plurality of pieces of data (element data);・・・
. . . are mask registers each capable of storing a plurality of pieces of mask data (mask element data); 11;
is a vector length register in which information on the number of elements stored in each vector register is set;
Reference numerals 12-0 and 12-1 represent memory access pipelines, 13 an addition/subtraction pipeline, 14 a multiplication processing pipeline, 15 a division processing pipeline, and 16 a mask processing pipeline.

When a vector processing processor as described above executes a process, a given source program is compiled into a form suitable for execution by the processor to generate a target program. The configuration of the compiler that performs the compilation will be described later with reference to FIG.
In compiling processing by the compiler, it is desirable to compile in such a way that when the vector processing processor actually executes processing, the free state of each pipeline operation unit is minimized as much as possible.

(q Purpose and structure of the invention The purpose of the present invention is to solve the above points,
(i) Based on the given intermediate code, each part φ...
Examine the manner in which the parallel processing unit is used, and (ii) each part...
- Extract the unique weight information of one calculation unit and the path weight information related to the mode in which the parallel calculation unit can be used, and sequentially calculate the parallel calculation units based on the (mountain) path information. A feature of the present invention is that an optimized target program is generated by allocating usage patterns.1, which will be explained below with reference to the drawings.

ID) Embodiment of the Invention FIG. 3 shows the configuration of an embodiment of a compiler used in the present invention, FIG. 4 is an explanatory diagram illustrating the manner in which a source program is transferred to intermediate code in the present invention, and FIG. 5 shows a source program.・
An explanatory diagram illustrating how a program is vectorized. Figures 6 to 10 are explanatory diagrams illustrating the processing according to the present invention. Figure 11 is a part of the intermediate code optimization section that is directly related to the present invention. Example flowchart, 12th
The figure shows an explanatory diagram related to processing in the pipeline calculation section.

In FIG. 3, 17 is a source program stored in the large storage device, 18 is a compiler, 19 is a target program that is compiled and stored in the large storage device, and 2
0 represents a source interpretation section, 21 a storage allocation section, 22 a vectorization section, 23 an intermediate code optimization section, 24 a register use determination section, and 25 a target program output section.

A compiler 18 takes in a source program 17 from a large storage device and generates a desired target program 19. At this time, each of the illustrated units performs the following processing.

That is, the source interpreter 20 loads the source program 17 from the large storage device, performs sentence interpretation, and develops it into intermediate code (text).
In the case shown on the left side of the figure, the condolence code is developed as shown on the right side of the figure. The storage area allocation unit 21 allocates addresses in the storage area corresponding to each piece of data that appears in the program. The vectorization unit 22 examines the loop structure in the program, recognizes parts that can be executed in parallel, and changes/changes the intermediate code as shown in FIG. The intermediate code optimization section 23 performs optimization at the intermediate code level to effectively utilize a vector processing processor as shown in FIG. The register use determining unit 24 allocates resources (registers) on the vector processing processor to data appearing in the intermediate code. Then, the target program output unit 25 outputs the machine instruction words to the large storage device and performs optimization at the instruction word level.

A compiler for operating a vector processing processor has a configuration as shown in FIG. 3, and compiles a source program. During this time, the above-mentioned intermediate code optimization section, as described later, uses the given intermediate code ( Performs processing to rearrange the order of text).

That is, a source program as shown in FIG. 6(A) is given, and an intermediate code as shown in FIG. 6(B) is supplied to the intermediate code optimization unit 23 shown in FIG. 3. Suppose that if the above-mentioned pipeline calculation units 12 to 15 are divided based on the intermediate code shown in FIG. 6 (CB), the configuration as shown in FIG. In order to solve this problem that causes an undesired empty state during use, when an intermediate code as shown in FIG. 6(B) is given, the code as shown in FIG. Create a "tree".

That is, the code "Vil-..." or "Vt2-..."
. . ”, therefore, a section marked with a circle (corresponding to processing by one of the pipeline calculation units) is prepared in a manner corresponding to the load shown in FIG. 7. Since addition is performed in response to the code "vt3-...", a clause is prepared in a form corresponding to the addition. In the same manner, a tree as shown in FIG. 7 is created.

Needless to say, the tree must be expanded and created on a table.

At this time, unique weight (individual weight) information is given to each node as shown in the lower right corner, and path grace information is given to each node as shown in the lower right corner. . These weight information are given as follows. In other words, the unique weight information is determined based on the calculation execution time, for example, when loading/unloading.
A weight of "1" is assigned to the store pipeline operation section, an addition/subtraction pipeline operation section, or a multiplication pipeline operation section, and a weight of "3" is assigned to the division pipeline operation section. . VT6.
A weight of "3" is given as unique weight information to the clause corresponding to vts, vt]o, and this is based on the fact that "division" is performed three times.

When the unique weight 4 information is given to each node in this way, the unique value 1 of the node is given as path weight information to a node that does not have a path in the upper part of the diagram. In the case shown, X(
A weight of "1" is given as path weight information to the clauses corresponding to →, Z H, and Y (*). Then, for example,
The node corresponding to vta that has a path to the node corresponding to (→) is extracted, and the path weight information is tentatively determined for the node. By adding the unique weight "1" of the vta node, the path weight of the Vt3 node is tentatively determined to be "2".
Clause and Vt6. Path weights are similarly tentatively determined for the vts and VtlO nodes. In the case of the illustrated vta clause, v
Since it also has a path for the tn and vtta nodes, and the corresponding path weight is set to "4," the side with the larger path weight is determined as the path weight for the Vt3 node.

The path weights of each node shown in FIG. 7 are determined as described above.

When the path weights are determined as shown in FIG. 7, the usage of each pipeline operation unit is assigned in order from the path weight to the one with the largest path weight, as shown in FIG.
When the t1 node and the Vt2 node are assigned to the load/store pipeline operation capitals, the illustrated time t! In, A(→
After the loading of the first elements of and B((a) is completed, it becomes possible to activate the pipeline calculation unit for addition and subtraction corresponding to clause 4vt3 from the time t1. In this way, the usage mode of each pipeline calculation unit is sequentially assigned, and it can be seen that the processing speed is improved by about 65% compared to the case shown in FIG. 8. As shown in FIG. 9, the result of rearranging the order of each intermediate code is shown.

FIG. 11 shows a flowchart of an embodiment of the portion directly related to the present invention in the intermediate code optimization section shown in FIG. 3 in order to execute the above-described processing.

The processes in the illustrated take/dependency understanding unit 26, tree structure creation unit 27, and node weight calculation unit 28 are as follows:
It corresponds to the explanation given in relation to Figures 6 and 7,
The bus weight of each node is extracted. Next, a vector calculation head pressure determination process is entered, and the pipeline determination unit 30. Vector calculation determining unit 31. The vector operation output unit 32 determines how each pipeline operation unit is used, as described in connection with FIGS. 9 and 10.

The pipeline determining unit 30 has the following processing functions. That is, it is determined which pipeline operation unit is more preferable to use for the operation to be output next. To this end, two aspects are examined. That is, the point in time when one operation is in a so-called ready-to-start state and the point in time when the pipeline operation section in which the operation will be used becomes idle are checked. Then, the later point in time between the two points is determined as the "instruction transmittable position" for the pipeline operation unit. Such a position where an instruction can be issued is determined for each pipeline operation unit, and the pipeline operation unit that has the “instruction enable position” at the earliest point in time is determined to use the pipeline operation unit. It will be decided.

The vector calculation determining unit 31 shown in FIG. Determine which operation to perform among the operations in . The following algorithm is used for this determination. In other words, ``a plurality of operations in the pipeline operation section that are in a start ready state before the above-mentioned instruction issuing position are extracted, and among them, the operation with the largest padding weight information is determined.''

As described above, when it is determined that the vector operation output section 32 shown in FIG. (1) Command transmission start position, (il
The command transmission end position, (iii) command execution start position (or start-up completion position), and (+V) command execution start position are simulated. Then, the instruction transmission stop position for each pipeline, which occurs due to the fact that the calculation uses one pipeline calculation unit, is reset,
Preparations are made to determine the Europe of the pipeline operation unit for the remaining operations.

12-1) As described in detail, according to the present invention, intermediate code is created so that undesirable vacant states are less likely to occur in each parallel processing unit when a vector processing processor executes processing. It becomes possible to compile in an appropriate form while converting the processing order of

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram conceptually explaining processing corresponding to vector instructions, FIG. 2 is an example of a processing system having a vector processing processor according to the present invention, and FIG. 3 is an example of a compiler used in the present invention. Embodiment configuration, FIG. 4 is an explanatory diagram illustrating the manner in which a source program is transferred to intermediate code, and FIG.
6 to 10 are explanatory diagrams illustrating processing according to the present invention. FIG. 11 is a flowchart of an embodiment of a portion directly related to the present invention in the intermediate code optimization section. The figure shows an explanatory diagram related to processing in the pipeline calculation section. In the figure, 1 is a main storage device, 2 is a memory control device, 3 is a vector processing processor, 4 is a channel processor, 5 is a large storage device, 9 is a vector register, and 10 is a mask processor.
Registers 11 to 16 are pipeline operation units, respectively;
17 is a source program, 18 is a compiler, 19 is an objective program, 20 is a source interpretation section, 21 is a storage allocation section, 22 is a program processing section, 23 is an intermediate code optimization section, and 24 is a register use determination section. A section 25 represents a target program output section. Patent applicant Fujitsu Ltd. Representative Patent Attorney Mori 1) Hiroshi (1 other person) 1 figure 74 figure 4 201 + τ2 5 figure Do 10 Z=7. too
vi-ENe=to. 6 Figure (A) Do 10 1= 1,100 X(υ= A(I) 10B(I) Y(I)= C(I) 60(1) HE(Z) Arrow F
(01m = X(Z) +Y(I)suA(1)l B
mlo CoNTIN (JE CB) 2 examples) = 7/-t13 Fig. 12 ``--I S Ryo t toy 7 beginning I y θga [``--Irann every 3 j 5 I Yoshihiragi ry 4 left mo Sai meat

Claims (1)

[Claims] In a compiler that generates and supplies a target program from a given source program to a vector processing processor that is equipped with a plurality of parallel operation units and at least an augend register and executes vector instructions, the source program The source interpretation section interprets program statements and develops them into intermediate code, the storage allocation section allocates storage locations for various data that appears in the program, and the A vectorization unit that performs recognition and changes the intermediate code, an intermediate code optimization unit that performs optimization to effectively utilize the vector processing processor at the intermediate code level, and a vectorization unit that performs optimization to effectively utilize the vector processing processor at the intermediate code level; and a target program output condition, and the intermediate code optimization unit determines how each parallel operation unit in the vector processing processor is used based on the given intermediate code. The processing unit is provided with a processing unit that examines and extracts the unique type information of each parallel processing unit and path weight information related to the manner in which the parallel processing unit can be used, and based on the path weight information. and a vector operation order determination processing unit that executes a simulation in which usage patterns are sequentially allocated to parallel operation units in a vacant state, and the processing order of the intermediate code is exchanged so as to optimize the processing by the vector processing processor. A parallel execution optimization processing method for vector performance.