JPS6319908B2 - - Google Patents

Description

[Detailed Description of the Invention] (A) Technical Field of the Invention The present invention relates to a parallel processing method using scalar arraying, particularly to a vector processing processor equipped with a plurality of parallel calculation units. In a compiler that generates and supplies a target program from the above, for loops with simple variables, the busy states of the simple variables at the entrance and exit of the loop are examined and classified, and based on the classification, each of the loops is classified for parallel processing. The present invention relates to a parallel processing method using scalar array processing, which performs the following processing.

(B) Technical background and problems For example, as shown in Figure 1A, if the elements a ₁ , a ₂ , ... belonging to vector A and the elements b ₁ , b ₂ , ... belonging to vector B are By adding, vector C with elements c ₁ , c ₂ ,...
There are vector processing processors that execute vector instructions, such as those that generate . In the case shown in FIG. 1A, mask elements m ₁ , m ₂ , . . . indicate whether or not to perform mutual addition of the i-th element. The processing shown 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 the main memory, 2 is the memory control device, 3 is the vector processing processor, 4 is the channel processor, 5 is the large storage device, 6 is the scalar processing circuit, 7 is the vector processing circuit, 8-0 ,8-
1,... are floating point data registers, 9-
0, 9-1, ... are vector registers that can each store multiple pieces of data (element data),
10-0, 10-1,... are multiple masks/
a mask register capable of storing data (mask element data); 11 a vector length register in which information on the number of elements stored in each vector register is set; 12-
0 and 12-1 are memory access pipelines, 13 is an addition/subtraction pipeline, 14 is a multiplication processing pipeline, 15 is a division processing pipeline,
16 represents 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 this compilation will be described later with reference to FIG. It is desirable to compile it in a form that can be executed in parallel so that it can be effectively utilized.

However, traditionally, simple variables (also called scalar variables)
If the simple variable is busy at the entrance or exit of the loop for a loop with (Classification “1” according to the present invention)
) were treated as not being able to be executed in parallel. That is, the vector processing processor was compiled in a form that processed using scalar instructions.

Regarding the busy status, let us take as an example the case where there is a process as shown in Fig. 19.
That is, in the illustration, data X is defined, then data X is referenced in , data X is referenced in , and data
For example, in the case where is defined, the value of data X defined in is referenced in , so data X is said to be busy from the time shown in the figure to . On the other hand, between the diagram and , if the data do not have. This makes it less busy.

(C) Purpose and Structure of the Invention The purpose of the present invention is to proceed with consideration of the above points and to promote parallel execution of simple variables whose existence mode falls under predetermined classifications. , (i) Check the busy state of simple variables at the entrance and exit of the loop, (ii) Classify the state of existence of the simple variables, and (iii) Arrange simple variables in each form according to the classification results. The feature is that it is designed to be executed in parallel. This will be explained below with reference to the drawings.

(D) Embodiment of the Invention Figure 3 shows the configuration of an embodiment of the compiler used in the present invention, Figure 4 is an explanatory diagram illustrating the manner in which a source program is transferred to intermediate code in the present invention, and Figure 5 is An explanatory diagram illustrating how a source program is vectorized. Figure 6 is an example of a loop that has conventionally been considered to be able to be executed in parallel. Figure 7 is an implementation of a portion directly related to the present invention in the vectorization section. Example flowchart, Figure 8 is an explanatory diagram explaining the existence mode of simple variables, Figures 9 to 1
3 each shows an embodiment of the processing according to classification according to the present invention. Further, FIGS. 14 to 15 sequentially show examples of modifications corresponding to classifications "1" to "5" according to the present invention, respectively.

In FIG. 3, 17 is a source program stored in a large storage device, 18 is a compiler,
19 is an object program which is compiled and stored on a large storage device; 20 is a source interpretation section; 21 is a storage allocation section; 22 is a vectorization section; 23 is an intermediate code optimization section; 24 is a register use determination section;
25 represents 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 takes in the source program 17 from the large storage device, performs sentence interpretation, and develops it into intermediate code (text). For example, if the source program is as shown on the left side of FIG. 4, it is developed into intermediate code shown on the right side of the figure. The storage area allocation unit 21 allocates addresses within the storage area corresponding to various data appearing within the program. The vectorization unit 22 detects loop structures in the program, recognizes parallel executable parts, and 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.

The compiler for operating the vector processing processor has the configuration shown in Figure 3.
The vectorization unit vectorizes (parallel execution) what can be executed in parallel according to the present invention.
I will do it.

However, conventionally, for loops that have a simple variable and the simple variable is in a busy state at the entrance and/or exit of the loop, other than those that have a predetermined form as shown in Figure 6, , it was believed that parallel execution was not possible.

In the present invention, the vectorization unit 22 shown in FIG. 3 performs the processing shown in FIG. They are arrayed in each format and compiled as something that can be executed in parallel. That is, (1) Corresponding to a given source program,
Detects the existence of a DO loop, and (2) detects the existence of a simple variable defined within the loop and retrieves it.

(3) Regarding the retrieved simple variables, as shown in FIG. 8, the busy state at the entrance or exit of the loop is checked, and the simple variables are classified based on the state of existence of the simple variables.

(4) For loops that cannot be classified, it is assumed that the loop cannot be executed in parallel, and compilation proceeds by executing processing using scalar instructions.

(5) For items that can be classified, create simple variable arrays according to each classification as shown in Figures 9 to 13. That is, processing by classification is performed.

(6) Once classification processing is performed on one simple variable, if there is a simple variable to check next,
The process is repeated for this.

(7) And for the above classifiable loops,
By the processing function in the vectorization unit 22,
It is vectorized.

FIG. 8 shows an explanatory diagram explaining the existence of simple variables, and depending on whether one simple variable is busy at the entrance or exit of a loop, one of the four boxes shown in the diagram It can be investigated.
Then, (i) those that are busy at the entrance and busy at the exit are classified into category ``1'', category ``2'', category ``3'', and ``other...unclassifiable''; (ii) entrance (iii) those that are not busy at the entrance and are busy at the exit are classified as "4"; (iv) those that are not busy at the entrance and busy at the exit are classified as "4"; If there is no exit and the exit is not busy, it is classified as "5".

In addition, in the above-mentioned classification "2", "position of artefacturing" means a part that must be passed through when executing a loop. Assuming that a processing loop as shown in FIG. 20 exists, the hatched area in the diagram is the articulation position. The portions indicated by the arrows in the drawings are not referred to as articulation positions because they may or may not be executed depending on the conditions.

In the case of classification "1", as shown in FIG. 9, no arraying is performed.

In the case of classification "2", as shown in Figure 10,
Prepare an array VT corresponding to the simple variable, and depending on the position of the first definition, set the simple variable to VT(I) or
Replace with VT(I+1), etc. Note that the above array VT is an array vector temporary, so to speak, array vector data placed in a storage area.
Note that it can be assumed that no vector register is allocated to the array VT during compilation or the like.

Further, the subscript I shown in the explanation is a control variable (DO variable) of the DO loop given in the form of, for example, DO 10 I=1, N : : (DO loop body) : : 10 CONTINUE. Also, the subscript K is a simple variable temporarily introduced to control the array VT, for example, K=1 DO 10 I=1, N: : VT(K)=...... K=K+1 : : 10 CONTINUE, etc. It is used in

In the case of classification "3", as shown in Figure 11,
VT a simple variable depending on the position of the first definition
(K) or VT (K+1), etc.

In the case of classification "4", as shown in Figure 12,
Replace simple variables with VT(I), etc.

In the case of classification "5", as shown in Figure 13,
Replace simple variables with VT(I).

Note that FIGS. 14 to 48 show examples of modifications corresponding to the above classifications "1" to "5", respectively.

(E) Effects of the Invention As described above, according to the present invention, it is possible to promote parallel execution of loops containing simple variables, and it is possible to increase the speed of processing executed by a vector processing processor.

[Brief explanation of the drawing]

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 explaining the manner in which the source program is transferred to intermediate code, FIG. 5 is an explanatory diagram explaining the manner in which the source program is vectorized, and FIG. 6 is the conventional configuration. Aspects of loops that can be executed in parallel; FIG. 7 is a flowchart of an example of a portion directly related to the present invention in the vectorization section; FIG. 8 is an explanatory diagram illustrating the existence of simple variables; FIG. 9 The figures to FIG. 13 each show an embodiment of the processing according to classification according to the present invention. Further, FIGS. 14 to 18 are examples of modified aspects corresponding to classifications "1" to "5" according to the present invention, respectively, FIG. 19 is an explanatory diagram for explaining the busy state, and FIG. 20 is It is an explanatory view explaining artefacturing. 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, 10 is a mask register, 11 to 16 are pipeline operation units, 17 is a source program, 18 is a compiler, 19 is a target program, 20 is a source interpretation section, 21 is a memory allocation section,
Reference numeral 22 represents a vectorization section, 23 an intermediate code optimization section, 24 a register use determination section, and 25 a target program output section.

Claims (1)

[Claims] 1. 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 processing units and at least a plurality of registers and executes vector instructions, A source interpretation unit that interprets program statements and develops them into intermediate code; a storage allocation unit that allocates storage addresses to various data that appears in a program; and a storage allocation unit that detects loop structures in a program and recognizes parts that can be executed in parallel. a vectorization unit that performs the process 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 an intermediate code optimization unit that allocates actual resources to the data appearing in the intermediate code. The vectorization unit includes a register usage determination unit and a target program output unit, and the vectorization unit detects the existence of a loop and the existence of a simple variable defined within the loop, and then detects the existence of a simple variable defined within the loop, and then is configured to classify the state of existence of the simple variable based on the busy state at the entrance and exit of the system, and performs simple variable arraying in a form corresponding to each classification based on the state of existence of each classified simple variable. A parallel processing method using scalar arraying, characterized in that processing is performed by classification to promote parallel execution.