JPS6015772A - Processing system for inter-loop array processing vector - Google Patents

Abstract

PURPOSE:To obtain the clear relationship among arrays and to produce an object which is executed at a high speed by replacing a variable in an index equation of an arrey within a loop with a definition equation of such a variable that contains a control variable or a constant of the loop. CONSTITUTION:A sentence structure analysis part 30 analyzes the syntax of a subject to be interpreted of a source module 25 and detects a variable having an unknown movement among those in an index equation through an index scan part 31. Then a definition equation scan part 32 searches a definition equation showning the variable or the constant that decides previously the searched variable to be processed out of a prescribed range. This definition equation is set into the index equation through an index setting part 33 to replace the variable of the processing subject with another variable or constant. After this set-in processing is over, the possibility for vector conversion is decided by a vector conversion priority decision part 34. Then a vector instruction generating part 35 produces an object containing a vector instruction for a sentence to which the possibility for vector conversion is decided.

Description

[Detailed description of the invention] Technical field of invention The present invention is an in-loop array processing vectorization processing method.

Especially when converting high-level languages that use arrays into machine language that can be executed on vector processing devices.

This invention relates to an in-loop array processing vectorization processing method that promotes pectorization to speed up the execution of conversion results.

Background and Problems of fBl Technology When a common processing procedure is applied to a plurality of pieces of data, a so-called vector processing device is used which executes the procedures in parallel. For example, when creating a program in a high-level language such as FORTRAN, the program creator does not need to be aware that the program will be executed by a vector processing device; When converting, the so-called compiler,
Generate vector instructions for what is possible. The more things that can be converted into vector instructions, the faster the execution will be due to parallel processing.

Figure 1 is an explanatory diagram of general vector instruction generation.
FIG. 2 shows a diagram illustrating problems in the prior art.

For example, a group of translated commands 4 input from card read 1
In , the high-level language sentence ■ has a control variable (from 1 to 10
This command instructs to repeat the imperative sentences up to 2 sentences (■) 10 times while changing them up to 2 times.

Statement ■ indicates that the sum of the data in array B and the data in array C should be stored in array A. Control variable i is array A,
It is used as a subscript for B and C.

The translation processing device 2 takes into consideration the intermediate representation 5 as shown in Figure 9 when expanding the translated instruction group 4 into machine language.
Machine language instructions as shown in machine language instruction group 6 are generated. Instruction ■ is a vector instruction that loads the data of array B into the O vector register. Instruction (2) is an instruction for loading the data of array C into the first vector register. Instruction (2) is an instruction to store the sum of the O vector register and the first vector register in the second vector register. Instruction (2) is an instruction to store the contents of the second vector register in array A. These instructions are actually given in binary code. The translation processing device is 9
Generate a machine language instruction group 6 and send it to the magnetic disk device 3, for example.
Store in. By expanding the instructions into vector instructions in this way, it becomes possible to execute 9 processes in parallel, which would normally be repeated 10 times, in one parallel process.

The vectorization process shown in FIG. 1 is not always possible. For example, as shown in Figure 2 A).

In the case of the instruction group 4 to be translated, if the instruction group is correctly executed on the array data 7-1 by sequential processing, the result will be as shown in the array data 7-2. However, if you process it by vectorizing it.

The result is array data 7-3, which is incorrect data. That is, in such a case, pectorization cannot be performed. This means that in the array assignment statement,
This is caused by an overlapping relationship occurring between the data groups indicated by the subscripts on the right and left sides. From this, conventional 1
For example, in the case of the translated instruction group 4 shown in Figure i2 (b), in the assignment statement ■9.

The variable used as a subscript in the array on the right side.

For the control variable i used as the subscript on the left side,
It was not possible to vectorize them because it was unclear what kind of relationship they had, and it was not possible to recognize the overlapping relationship between the sequences.

fcl Object and Structure of the Invention The present invention aims to solve the above-mentioned problems, and replaces the variables in the subscript expression of the array in the loop with the definition expression of the variable that includes the control variable or constant of the loop. The purpose is to clarify the relationship between objects, promote pectorization, and generate objects that execute at high speed.

Therefore, the in-loop array processing vectorization processing method of the present invention is as follows.

In a translation processing device into machine language instructions in a vector processing device equipped with a vector unit that executes a vector instruction that processes multiple pieces of data in parallel, and a scashi unit that executes a scashi instruction that processes scashi data. , a subscript scanning means for searching for a subscript of an array that appears in a group of translated instructions expressed in a repeatedly executed form and that includes a variable whose operation is unknown; and a definition for searching for an expression that defines the variable whose operation is unknown. an expression scanning means, a subscript expression embedding means for incorporating the content of the expression found by the definition expression scanning means into the subscript information, and vectorization based on the new subscript information generated by the subscript large embedding means. and a determination means for determining whether or not it is possible.

The present invention is characterized by comprising a vector instruction generation processing section that generates the vector instruction according to the determination result of the determination means. This will be explained below with reference to the drawings.

fD) Embodiment of the Invention FIG. 3 is a configuration diagram of an embodiment of the present invention, FIG. 4 is an explanatory diagram of processing of an embodiment of the invention, and FIG. 5 is an explanatory diagram of processing mode of a specific embodiment of the present invention. shows.

In FIG. 3, numerals 2 and 3 correspond to those in FIG.
O is a vector processing unit, 11 is a vector unit, 1
2 is a storage unit, 22 is a main storage device, 23 is a channel device, 24 is an object module, and 25 is a source module.

30 is a syntax analysis section, 31 is a subscript scanning section, 32 is a definition expression scanning section, 33 is a subscript expression embedding section, 34 is a vectorization possibility determination section, and 35 is a vector instruction generation section.

36 represents a scalar instruction generation section.

The translation processing device 2 is a device that fetches and executes sequential instructions, and inputs a source module 25 consisting of a group of translated instructions written in a high-level language such as FORTRAN, and converts it into binary machine language instructions. Convert it to an object
This is a device that outputs the module 24 to, for example, the magnetic disk device 3.

The translation processing device 2 may be the same device as the vector processing device 10, or may be another processing device.

The vector processing device 10 is a device that processes nine normal search instructions and a vector instruction for processing multiple pieces of data simultaneously in parallel, and is composed of a vector unit 11 and a search unit 12. The scashi unit 12 includes a buffer storage 19 and a scalar arithmetic unit 21, loads data on the main storage device 22 into a register 20, and uses the scashi arithmetic unit 21 to sequentially process scashi instructions. Vector unit 11 is activated when the instruction fetched from main memory 22 is a vector instruction. 1 with multiple load/store pipelines 13.13'
For example, it has 256 mask registers 14 consisting of 32 words x 1 bit and 256 vector registers 14' consisting of 32 words x 64 bits. Mask circuit 1
5 specifies the data for which the condition is true, in order to include a procedure including an IF statement in a FORTRAN program as a target for vectorization.

Addition/logic operator 169, multiplier 17, and divider 18 each process data groups in vector register 14' in parallel according to vector instructions.

Since large amounts of data are processed simultaneously, high-speed data processing is possible. In the main storage device 22.

An object module 24 containing vector instructions or a load module that is an edited version of the object module 24 is loaded in advance via the channel device 23.

Due to the configuration of the vector processing device 10 as described above.

As long as the processing contents are the same, it is preferable that vector instructions be used as many as possible. Therefore, the translation processing device 2 according to the present invention particularly has the following configuration.

The W sentence M analysis section 30 analyzes the syntax of the target to be translated in the source module 25.

The subscript scanning unit 31 performs a process of searching for variables in the subscript expression whose movements are unknown. Note that the subscript may be considered to indicate a position within an array consisting of a plurality of pieces of data. In particular, the subscript scanning unit 31 scans the subscripts of the array.
Process variables other than the control variables of all loops including that statement. Here, the loop is 2 For example, FORTRAN DO
It is a group of instructions that are repeatedly processed by a statement.

A control variable is a variable whose value depends on the number of repetitions of the loop.

The definition formula scanning unit 32 scans a definition formula that indicates what kind of variable or constant is used to predetermine the variable to be processed that has been found by the subscript scanning unit 31.

It executes the following search process from a predetermined range. The blocks to be scanned by the expression are the block in which the variable to be processed appears, then the block that must pass through on the bus to the block where the variable to be processed appears in the loop where the variable to be processed appears, and the block in which the above variable appears. This is the initialization block of the loop where the variable to be processed appears. In addition,
A block is a processing unit of translation, and refers to a part where the flow of processing is uniquely determined.

The subscript expression incorporation section 33 performs processing of incorporating the expression found by the definition expression scanning section 32 into the subscript expression, and replacing the variable to be processed with another variable or constant. If the expression that defines the variable is an expression containing only constants, or if the expression includes any one of the control variables of the loop that includes the statement to be processed.1 An expression in which the variable to be processed does not appear in the expression If so, perform the embedding. For example, the control variables of a loop are i and J, and the assignment statement for array A is:

In the same block, the variable K is given by A (J) = A (j + K).

Assuming that K=J+10 is defined, the above assignment statement is executed by the subscript expression embedding unit 33.

Replaced with A (J) = A (s+J+10).

After the subscript expression embedding unit 33 completes the embedding process, the vectorization possibility determining unit 34 compares the subscript expressions appearing on the right side and the left side of the array assignment expression, and determines whether vectorization is possible based on whether there is a one-overlap relationship. This is what determines the If the array names are different, it is assumed that no overlap occurs in that part, but even if there is an overlap in the assigned data, as in the case of assignment by moving the data from backward to forward, If the processing results when processing by vectorization and when processing by sequential processing are the same, it is determined that vectorization is possible.

The vector instruction generation unit 35 includes a vectorization possibility determination unit 34.
Regarding sentences that are determined to be vectorizable.

The scalar instruction generation unit 36 generates an object consisting of vector instructions, and the scalar instruction generation unit 36 executes a process of expanding into scalar instructions those that cannot be vectorized.

With the above-mentioned planting, the translation processing device 2 performs processing as shown in FIG. 214, for example. Note that the description will focus on two processes related to the present invention, but other processes will be described.

It can be considered that it is the same as before. First, subscript information is created by the "A-4 diagram illustration process 40. Subscript information according to the subscript formula in the source is extracted. Next, by process 41,
Structural analysis is performed according to a predetermined grammar. Next, until it is confirmed by the determination in process 42 that the processing for all texts has been completed, process] j, l! Steps 43 to 50 are repeated. Process 43 searches for variables in the subscript expression whose movement is unknown. If there is a subscript whose operation is unknown, a process 44 searches for an expression that defines a variable used in the subscript to be processed in the same block B1. As a result of the determination in process 45, if it is found, the process moves to process 49. In process 46,
In the DO loop in which the variable K to be processed appears, there is a block that always passes through, for example, B2. Search for the defining formula for B3. Branching block B4. B5 is not guaranteed to pass.

Remove from search targets. If it is found in process 47, the process moves to process 49. In process 48, initialization block B6.
A search is made to see if there is a definition expression outside the DO loop in which the variable to be processed appears, such as B7.

If it is determined in step 49 that the definition expression is not found, or if it is determined that it does not match the built-in condition even if it is found, the process returns to step 42 with the variable whose behavior is unknown as is.

Move on to processing the next text. If the incorporation is possible, the definition expression is incorporated in step 50.

Replace the variable with something whose behavior is known, such as a loop control variable. Thereafter, control is transferred to process 42.

After performing the processing from step 43 on all texts,
The process moves to process 51. In process 51, the overlapping relationship of subscripts is checked. If it is determined by the process 52 that vectorization is possible, the process 53 expands it into a vector instruction.

If vectorization is not possible, process 54 is performed.

Create an object using normal scalar instructions.

Next, in process 55, it is determined whether or not the translation of all texts into machine language has been completed, and if not, 8
Processes 51 to 54 are repeated for the next text content.

Next, the processing mode will be explained according to a specific example with reference to Fig. 5. For example, a group of translated instructions 4 as shown in FIG.
Suppose that is given. Sentence S1. S3°85.86 are assignment statements that instruct to assign 66 in the expression on the right side to the variable on the left side. especially.

Regarding sentence S6, array data is handled.

Sentences S2 and B4 are statements that instruct a so-called Do loop, and indicate that the command statements up to the second sentence S7 should be repeatedly executed. There are multiple loops for loop control variables J and L.

The subscript scanning unit 31 searches the translated instruction group 4 for an array subscript that includes a variable whose operation is unknown. In this example, there is an array in the 9th sentence S6, and its subscript information is as shown in FIG. 5(b).

The relationship between the subscripts ■ and the subscripts ■ is clear, but the relationship between the subscripts ■ and the subscripts ■ is unclear. Note that array A is a different array from array B to which 9 is assigned, so
Does not affect whether vectorization is possible. Conventionally, when there is a relationship between subscripts ■ and ■ whose behavior is unknown, it has been thought that it cannot be vectorized. In the case of the present invention, vectorization is promoted by clarifying the subscript relationship as follows.

The definition formula scanning unit 32 searches for definition formulas for variables iB and iA whose operations are unknown. In this example, one sentence S3 and one sentence S5 are found. The subscript type embedding part 33 is one sentence S
3 and the definition expression given by statement S5 are incorporated into the subscript information. by this.

The subscript information regarding the sentence S6 is replaced with subscripts ω', ■', and ■' as shown in FIG. 5(C).

Here, if you check the relationship between the subscripts, there is no problem with the left side and vectorization. The relationship between the subscript (-) and the subscript ω' is clarified by examining the loop control variables and the operating range of J. That is, by the ninth sentence S4.

1≦L≦J O≦L−1 each J−1 is obtained, and from this it can be seen that N≧N−L+1≧N−J+1. Therefore, the relationship between the subscripts is as shown in Figure 5), where the subscripts are at least "N-J+I
Since it is larger than J, it can be seen that there is no single overlap. As a result, the vectorization of the in-loop array that appears in the translated instruction group 4 becomes nJ-capable.

(E) As described in detail, according to the present invention, the vectorization rate can be increased, and parts that could not be vectorized in the past are vectorized, thereby improving the execution performance of the generated object. improves.

[Brief explanation of drawings]

Figure 1 is an explanatory diagram of general vector instruction generation.
Fig. 2 is an explanatory diagram of problems in the prior art, Fig. 3 is a configuration diagram of an embodiment of the present invention, Fig. 4 is an explanatory diagram of processing of an embodiment of the present invention, and Fig. 5 is a concrete implementation of the present invention. An explanatory diagram of an example processing mode is shown. In the figure, 2 is a translation processing device, and 4 is a group of instructions to be translated. 10 is a vector processing device, 11 is a vector unit,
12 is a search unit, 22 is a main storage device, 23 is a channel device, 24 is an object module, 25 is a source module, 30 is a syntax analysis section, 31 is a subscript scanning section, 32 is a definition expression scanning section, 33 is a Subscript type built-in part, 3
Reference numeral 4 represents a vectorization propriety determination section, 35 a vector instruction generation section, and 36 a scalar instruction generation section. Patent applicant Fujitsu Limited

Claims (1)

[Claims] In a translation processing device into machine language instructions in a vector processing device, which is equipped with a vector unit that executes a vector instruction that processes multiple pieces of data in parallel, and a scan unit that executes a scan instruction that processes scan data, A subscript scanning means that searches for a subscript of an array that appears in a group of translated instructions expressed in a repeatedly executed form and that includes a variable whose behavior is unknown, and a definition expression that searches for an expression that defines the variable whose behavior is unknown. a scanning means, a subscript expression incorporating means for incorporating the contents of the expression found by the definition expression scanning means into the subscript information, and whether or not vectorization is possible based on the new subscript information generated by the subscript expression incorporating means. 1. An in-loop array processing vectorization processing method, comprising: a determining means for determining the above-mentioned vector instruction; and a vector instruction generation processing section for generating the vector instruction according to the determination result of the determining means.