JP2809073B2 - Array memory allocation method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a compiler for generating a target program from a source program, and more particularly to an array defined or referred to in an executable statement in the source program, each of which constitutes a distributed memory multiprocessor system. The present invention relates to a memory allocation method for arrays, which is allocated on distributed memories corresponding to different processors.

[0002]

2. Description of the Related Art In a compiler such as a FORTRAN compiler, for an array defined or referred to by an executable statement in a source program, an array area for storing the array is allocated to a continuous area on a memory. ing. This is the same for a compiler for a multiprocessor system composed of a plurality of processors.

[0003]

In a multiprocessor system, besides a system in which a plurality of processors can access all memories equally with almost the same access time, for example, as shown in FIG. It has distributed memories M1 to Mn and each distributed memory M1
Mn and a switch network SW connected to the processors P1 to Pn. Each of the processors P1 to Pn can directly access the distributed memories M1 to Mn corresponding to its own processor at high speed. There is a system that can only be accessed indirectly through the SW, that is, a distributed memory multiprocessor system of a so-called virtual shared memory system.

In general, in a multiprocessor system, 1
Since the processing for one array is shared by multiple processors, according to the method of allocating the array area to a continuous area on the memory, in the case of a multiprocessor system in which multiple processors can access the entire memory equally, Although there is no particular problem, in the case of the distributed memory multiprocessor system described above, a processor in which the array area is allocated on its own distributed memory can access array elements at high speed, whereas other processors have high speed. There is a problem that the access cannot be performed, the load becomes unbalanced, and the parallelization performance is reduced.

SUMMARY OF THE INVENTION An object of the present invention is to allocate arrays to memories in a distributed memory multiprocessor system so that the processing of the arrays is shared among the processors so that there is no load imbalance among the processors. An object of the present invention is to provide an array memory allocation method.

Japanese Unexamined Patent Publication No. 63-127340 discloses an enlarged dimension of the array so that accesses to array elements in a predetermined order are not concentrated on a specific memory bank or a specific buffer. Although a technique for providing a gap between array dimensions has been proposed, this technique is not applied to a compiler for a distributed memory multiprocessor system. Also, applying this technology to a distributed memory multiprocessor system, for example, A (16,16)
Is enlarged to the size of the distributed memory equal to the size of the distributed memory, and as shown in FIG.
If assigned to 2,..., The area of the distributed memory indicated by * in the figure becomes a useless area that cannot be used for other purposes, and the memory efficiency is extremely deteriorated.

It is another object of the present invention to eliminate the imbalance in the load on the array processing of each processor without increasing the dimension of the array.

[0008]

According to the present invention, in order to achieve the above object, a source program is input, a distributed memory is provided for each processor, and each processor can directly access the distributed memory corresponding to its own processor. In a compiler for generating a target program executable in a distributed memory multiprocessor system of a virtual shared memory system configured so that a distributed memory corresponding to a processor can be indirectly accessed through a switch network, an execution statement in the source program Memory allocation of an array that divides an array to be defined or referred to and allocates each on distributed memory allocated to different processors constituting the distributed memory multiprocessor system
In the method, the array declaration is taken from the source program.
The array fetching means to be fetched and the
Division size determinant for finding the division size for such arrays
And the array according to the array declaration is the source program.
Appeared as an array defined or referenced in an executable statement in the program
In the case, the array is divided by the obtained division size.
Then, as the code corresponding to the obtained individual sequence portion,
Individual array parts are assigned to different processors
Virtual shared memory that can be allocated on
Address conversion that generates code represented by memory addresses
Conversion code generation means, and the address conversion code
The code generation means calculates base + N {int (i / b) × (p−b) + i} for the array element of index i, where: base; address b serving as a base of the array ; division size p; The size N of the distributed memory allocated to the memory ; a code converted to a virtual shared memory address indicated by the number of storage units on the memory occupied by one array element
It is generated .

[0009]

According to the present invention, a compiler divides an array defined or referred to in an executable statement in a source program and allocates each array part to a different distributed memory, thereby reducing the load on array processing of each processor. Eliminate imbalance. Specifically,
Extraction means extracts array declaration from source program
And the division size determination means
The division size for the array
The generating means determines that the array according to the array declaration is the source program.
Appear as an array defined or referenced in an executable statement in a ram
The array is divided by the calculated division size.
Then, as the code corresponding to the obtained individual sequence portion,
Individual array parts are assigned to different processors
Virtual shared memory that can be allocated on
Generates the code represented by the memory address.

[0010]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS Next, embodiments of the present invention will be described in detail with reference to the drawings.

FIG. 1 is a configuration diagram of an embodiment of a compiler to which the present invention is applied. The compiler 1 of the present example receives a source program 2 and sequentially generates a first intermediate text 3 and a second intermediate text 4 during a compilation process.
Finally, it has a function of generating and outputting a target program 5 for a distributed memory multiprocessor system.

The compiler 1 inputs a source program 2, performs lexical analysis, syntax analysis, semantic analysis, and the like, and outputs a first intermediate text 3. The compiler 1 receives the first intermediate text 3 and performs optimization. Processing unit 12 that outputs the second intermediate text 4 by performing a process related to data and vectorization, a memory allocation process, and the like, and a target program that inputs the second intermediate text 4 and outputs a target program 5 described in a machine language And a generating unit 13.

As a functional means relating to memory allocation of the array, an array fetching means 1 is provided in the analyzing unit 11.
11, a division size determination unit 112 and a distributed memory size extraction unit 113, and an address conversion code generation unit 121 in the processing unit 12.

Hereinafter, the compiler 1 configured as described above will be described.
Will be described.

The analysis unit 11 of the compiler 1 inputs the source program 2 and performs lexical analysis,
Performs syntax analysis and semantic analysis. At this time, when an array declaration appears in the source program 2, the array fetching means 11
1 retrieves the array declaration and stores information on the array such as the array name, array type, number of dimensions, and array length in a table (not shown) or the like.

When a description designating the division size related to the declared array appears in the source program 2, the division size determining means 112 obtains the division size related to the array from the description and stores it in a table (not shown). Hold.

Although this embodiment employs a method in which the user describes the array division size in the source program, the division size determination means 112 includes the number of processors of the target distributed memory multiprocessor system. The size of the array part distributed to each processor is checked to be equal, or if the array size is divided by the number of processors, and there is a remainder, the division size is automatically set to be equal except for at least one processor. The function required may be provided.

Further, when a description designating the size of the distributed memory of each processor appears in the source program 2, the distributed memory size extracting means 113 obtains the size of the distributed memory from this description and stores it in a table (not shown). I do.

Although this embodiment employs a method in which the size of the distributed memory is described in the source program by the user, the size may be specified by a compiler option. Further, the distributed memory size extracting means 113
In this case, a code for extracting the size of the distributed memory may be generated, and the size of the distributed memory may be acquired at the start of execution of the target program by executing this code. At this time, the address conversion code generation unit 121 described later performs the distributed memory size extraction unit 113
A configuration for generating a code including a variable to which the size of the distributed memory extracted by the code generated in step (1) is substituted is adopted. Here, the size of the distributed memory is generally determined by the address mechanism controlled by the operating system according to the machine architecture.

When the source program 2 is processed by the analysis unit 11 to generate the first intermediate text 3, the processing unit 12 inputs the first intermediate text 3 and performs processing such as optimization, vectorization, and memory allocation. The second intermediate text 4 is output.

At this time, the address conversion code generation means 1
Reference numeral 21 denotes an array extracting means 11 for an array defined or referred to in an executable statement in the source program 2.
1, the array is divided in consideration of the division size, distributed memory size, and the like held in a table or the like (not shown) by the division size determination unit 112 and the distributed memory size extraction unit 113, and each is divided into target distributed memory multiprocessors. Allocate them on distributed memories allocated to different processors constituting the system.

When the second intermediate text 4 is generated by the processing unit 12, the target program generation unit 13 converts the second intermediate text 4 into a machine language to generate the target program 5.

Next, the operation of this embodiment will be described more specifically with reference to specific examples.

Assume that an array declaration 21 as shown in FIG. 2 exists in the source program 2 and a DO loop 22 including a reference statement of the array A exists in an execution statement. It is also assumed that the division size is designated as “86” for this array A, and the size of the distributed memory is p.

For such an array A, the address conversion code generation means 121 converts the array A into a first array portion having 86 elements, a second array portion having 86 elements, and a third array portion having 84 elements. As shown in FIG. 3, each of the distributed memories M1, M2, and M3 (the addresses are continuously distributed over the entire distributed memory with the distributed memory M1 at the top) is divided into array portions. The first array portion 32 is allocated to the memory M1, and the second array portion 32 is allocated to the distributed memory M2.
, And a code for allocating the third array portion 33 to the distributed memory M3 is generated.

That is, the address conversion code generation means 121
Generates a code converted to a virtual shared memory address represented by base + N {int (i / b) × (p−b) + i} for the array element at index i of array A. Here, base is the base address of the array, and if the value of the subscript does not start from 0, it is shifted so that it starts virtually from 0. Also, b is the division size, p is the size of the distributed memory, N is the number of storage units on the memory occupied by one array element (1 in this case), in
t () is an integer conversion function that extracts only the integer part of the value of ().

Therefore, the image of the code generated by the compiler 1 for the loop 22 including the array A in FIG.
It becomes as shown in. However, FIG. 4 shows compiler 1 for explanation.
Is the source code in the form of the generated code, not the actual object code.

By doing so, the array A can be almost evenly distributed among the distributed memories corresponding to the respective processors, so that each processor constituting the distributed memory multiprocessor system has the distributed memory M corresponding to its own processor.
By sharing the processing of the array portions on M1, M2, and M3, the imbalance of the load on the array processing of each processor is equalized, and the work amount of each processor in the parallel processing is reduced uniformly, so that the parallel processing is reduced. Efficiency is improved.

In the above embodiment, an object code as shown in the image of FIG. 4 is generated for the linear array used in the DO loop as shown in FIG. 2, that is, the array whose index i is a linear expression. As is clear from FIG. 4, the index is not linear after the conversion. In general, if the indices of the array are not linear,
Since optimization and vectorization of the generated code are hindered, it is desirable that the index be linear in consideration of optimization and the like.

In order to maintain the linearity of the index, the following may be performed. That is, the address conversion code generation unit 121 sets a DO loop including an array whose index i is a linear expression as an initial value, a final value,
By appropriately setting the increment value, an object code is generated after the array index is transformed into a double loop of an inner loop represented by a linear expression and an outer loop including the inner loop.

According to such a method, for the loop 22 including the array A in FIG. 2, a code as shown in FIG. 5, which is expressed by replacing it with the image of the source program, is generated. Loop control variable (i2)
Can be kept linear with respect to. Here, the outer loop is a loop that crosses the distributed memory corresponding to each processor, and the inner loop is a loop that extends from the beginning to the end of the array portion in the distributed memory corresponding to each processor.

An array that does not appear in the loop or an array that is originally linear even if it appears in the loop needs to generate an object code by the method illustrated in FIG.

[0033]

As described above, according to the present invention, the array is divided into a plurality of parts, and the individual array portions are allocated to different distributed memories, respectively. By sharing the processing of the array part on the distributed memory corresponding to the own processor, it is possible to eliminate the imbalance in the load on the array processing of each processor, and it is possible to speed up the parallel processing on the array. .

Further, since the dimension of the array is not enlarged, the remaining portion of the distributed memory where the array portion is allocated can be effectively used for allocation of other array portions.

Further, when an array appears in a loop and its index is expressed by a linear expression, the loop is divided into an inner loop whose array index is expressed by a linear expression and an outer loop containing the inner loop. By generating object code after transforming into a loop, a loop including an array can be a target of optimization or vectorization.

[Brief description of the drawings]

FIG. 1 is a block diagram illustrating an example of a compiler to which the present invention is applied.

FIG. 2 is a diagram illustrating an example of an array declaration and an executable statement including an array appearing in a source program.

FIG. 3 is a diagram showing an example of allocation of arrays to distributed memories.

FIG. 4 is a diagram in which an example of a code generated by an address conversion code generation unit is replaced with a representation format of a source program.

FIG. 5 is a diagram in which another example of the code generated by the address conversion code generation means is replaced with an expression format of a source program.

FIG. 6 is a block diagram illustrating a configuration example of a distributed memory multiprocessor system.

FIG. 7 is an explanatory diagram of a conventional problem.

[Explanation of symbols]

 DESCRIPTION OF SYMBOLS 1 ... Compiler 11 ... Analysis part 111 ... Array extraction means 112 ... Division size determination means 113 ... Distributed memory size extraction means 12 ... Processing part 121 ... Address conversion code generation means 13 ... Object program generation part 2 ... Source program 3 ... First Intermediate text 4 ... Second intermediate text 5 ... Objective program

Continuation of the front page (56) References JP-A-3-256129 (JP, A) JP-A-5-290,000 (JP, A) IPSJ Technical Report (92-ARC-97), 92-97! (1992-12.), P. 41-48 Information processing, 34-9! (1993-9); 1150-1157, "Automatic parallelizing compiler" (58) Fields investigated (Int. Cl. ⁶ , DB name) G06F 9/45 G06F 15/16 JICST file (JOIS)

Claims (7)

(57) [Claims] A distributed memory is provided for each processor when a source program is input, and each processor can directly access the distributed memory corresponding to its own processor and indirectly access the distributed memory corresponding to another processor through a switch network. In a compiler for generating a target program executable in a distributed memory multiprocessor system of a virtual shared memory system configured as described above, an array defined or referred to in an execution statement in the source program is divided, and each is divided into the distributed memory Memory allocation of arrays to be allocated on distributed memory allocated to different processors constituting a multiprocessor system
Fetching an array declaration from the source program
Output means and split size for the array associated with the fetched array declaration
And an array according to the array declaration in the source program
When it appears as an array defined or referenced in an executable statement
Then, the array is divided by the obtained division size,
The code corresponding to the individual array part
Array parts were assigned to different processors
A virtual shared memory that can be allocated on distributed memory
Address conversion code that generates a code
And the address conversion code generating means has an index i.
For the array element, base + N {int (i / b) × (p−b) + i} where base; address b as the base of the array ; division size p; size N of distributed memory allocated to each processor A code converted into a virtual shared memory address indicated by the number of storage units on the memory occupied by one array element;
An array memory allocation method characterized by generation . 2. The address conversion code generation means, when the array appears in a loop and its index is represented by a linear expression, defines the loop as an inner loop whose array index is represented by a linear expression. arrangement of the memory allocation system according to claim 1, wherein the generating the code after having deformed the double loop and outer loop encompassing an inner loop. 3. The address conversion code generation unit generates a DO loop including an array whose index i is a linear expression by DO i1 = 1, int ((n + b−1) / b) DO i2 = i1 × p + 1, min 3. The array memory allocation method according to claim 2, wherein (i1 * p + b, int (n / b) * (p-b) + n) a (i2) is used to form a double loop. 4. The array memory allocation method according to claim 2, wherein said division size determination means recognizes a division size of an array described in a source program to obtain a division size. 5. The division size determining means checks the number of processors of a target distributed memory multiprocessor system and determines a division size such that the size of an array portion distributed to each processor is uniform except for at least one processor. 4. The array memory allocation method according to claim 2, wherein 6. The array memory allocation method according to claim 4, wherein the size of the distributed memory corresponding to each processor is specified in a source program or by a compiler option. 7. A distributed memory size extracting means for generating a code for extracting the size of the distributed memory corresponding to each processor, wherein the address conversion code generating means is extracted by the code generated by the distributed memory size extracting means. 6. The array memory allocation method according to claim 4 , wherein a code including a variable to which the size of the distributed memory is substituted is generated.