JP2739836B2 - Optimal data distribution generation device and compilation processing device - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an optimal data distribution for generating parameters for optimally distributing data in a computer system in which a plurality of systems each comprising a processor and a memory are connected via a connection network. The present invention relates to a generation device and a compilation processing device that converts a sequential program into a parallel program.

[0002]

2. Description of the Related Art In a parallel computer system in which a plurality of devices each composed of a processor and a memory in each of the divided regions of the array to which the present invention is applied are connected via a connection network. The method of arranging in the memory is a data parallel language, High Performance.
Fortran (High Performance F
ortran Forum: High Perform
mance Fortran Language Sp
efficiency, Version 1.0, M
ay 1993. ) And Fortran D (Fox et al .:
Fortran D Language Speci
fication, Tech. Report COMP
TR90079, Dept. of Computer
Science, Rice Univ. , 1991)
Assume that this is done in the manner used in. Hereinafter, a method of arranging an array in a memory of a parallel computer system in which a plurality of devices each composed of a processor and a memory in each of the divided regions are connected via a connection network will be simply described as an array. This is called a distribution method.

FIG. 1 shows a method of distributing arrays in an HPF. In the HPF, first, an element of the array (0101) is associated with an element of another array (0103). Hereinafter, the relationship between the elements of the associated array is called an alignment relationship,
Associating an element of an array with an element of another array is called alignment. By aligning a plurality of sequences with one and the same sequence, a group of sequences representative of one sequence to be aligned is formed. The representative sequence (0103) is not aligned with any other sequence, but can be considered aligned with itself. Next, a method for arranging a plurality of devices each including a processor and a memory of each of the divided regions in a parallel computer system connected to a plurality of devices via a connection network in a memory of the devices is performed. Is defined, and the elements of the array other than the representative array are allocated to the memory of the device to which the corresponding representative element is allocated, and as a result, the distribution of all the arrays belonging to the group represented by this array is defined. You.

FIG. 2 shows a description example of a method of distributing the arrays A, B, and C using the HPF. In the description example, A is B
, B is aligned with C, but as a result, both A and B are aligned with C.

FIG. 3 shows an arrangement A (0301) and an arrangement B (03
02) shows the alignment relationship of sequence C (0303). In the figure, an arrow (0302) from array A to array B indicates each element of A and B
Represents the alignment relationship with each element. The arrow (0304) from the array B to the array C indicates the alignment relationship between each element of B and each element of C. In the figure, l, u, and s are
A parameter (030) representing the alignment relationship from A to C
6), 1 is the element number of C associated with the first element of A, u is the element number of C associated with the last element of A, and s is the element of C associated with the element of A Is the distance between them.

[0006] The above three parameters are referred to as an alignment triple and are represented as [l: u: s]. In the example of FIG. 3, the alignment triple for A with respect to C is [4: 16: 2] and the alignment triple for B with C is [2: 16: 2]. Where array C
Is representative of the sequence group formed by the three sequences A, B, C and is referred to as the final alignment target. Therefore, when the area division of the array C and the method of arranging the divided areas in the memory of the device of the parallel computer system are defined, the distribution of the arrays A and B is determined at the same time. The state of dispersion is shown in FIG. At this time, the elements of the array associated by the alignment are always allocated to the same processor (0407).

A conventional technique will be described with reference to an example program shown in FIG. 6 when an array is dispersed by the above method. In the example program, as shown in FIG.
701) are aligned with sequence A (0702) [1:15:
1]. The array A is divided into regions as shown in FIG. 8, and the divided regions are respectively arranged in four processors, and the elements of the array B corresponding to the elements of the array A also correspond to the elements of the array A. The processor where the element is located is located. As a result, as shown in FIG. 8, array A has a first element to a fourth element arranged in processor 1, a fifth element to an eighth element arranged in processor 2, and a ninth element to 12th element. The th element is located in processor 3, the thirteenth to sixteenth elements are located in processor 2, array B has the first to fourth elements located in processor 1, the fifth element is located in processor 5, The eighth element is located in processor 2, the ninth to twelfth elements are located in processor 3,
The thirteenth element to the fifteenth element are arranged in the processor 2.

In the prior art, the necessary data transfer between processors is detected in the following procedure. First, each processor executes a loop iteration executed by a method of assigning a loop iteration for updating an element of an allocated array. In the above example program, since the array A is updated in a loop, each processor is assigned a repetition for updating the assigned element of the array A. That is, 3 from the first iteration of the loop
The fourth iteration is assigned to processor 1, the fourth through seventh iterations are assigned to processor 2, the eighth through eleventh iterations are assigned to processor 3, and the twelfth through fifteenth iterations are assigned to processor 4. , And the assigned iteration is executed on each processor.

Next, the accessed element of the array accessed in the loop is determined for each processor. In the above example program, the elements of array B accessed by processor 1 are the first to third elements, the elements accessed by processor 2 are the fourth to seventh elements, and the elements accessed by processor 3 are The eighth element to the eleventh element, and the elements accessed by the processor 4 are the twelfth element to the fifteenth element.

Next, the element accessed by each processor is compared with the element allocated to each processor, and among the elements accessed, the element allocated to another processor is detected.

In the example program, processor 4 accesses the fourth element of array B, but the fourth element of array B is located in processor 1 and processor 3
Accesses the eighth element of array B, the eighth element of array B is located in processor 2, and processor 4 accesses the twelfth element of array B,
Since the twelfth element of array B is located in processor 3, the fourth, eighth, and twelfth elements of array B are detected.

Next, in order to move the detected element from the arranged processor to the processor to be accessed, the fourth element of the array B is moved from the processor 1 to the processor 2, and the array B is moved from the processor 2 to the processor 3. Is generated, and a code for moving the twelfth element of array B from processor 3 to processor 4 is generated.

As described above, in the conventional compile processing apparatus, a necessary data transfer between processors can be detected only when the processor in which each element of the array is arranged is known.

[0014]

In the conventional compile processing apparatus, the analysis method for detecting the required data transfer is complicated, and the method for dividing the array into regions is unknown at the time of compilation. There was a problem that you can not.

[0015]

According to the present invention, there is provided an optimal data distribution generating apparatus, wherein a first array declared in a program including at least one loop composed of a plurality of repetitions is divided into regions, and each of the divided individual regions is divided into regions. In order to allocate an area to the memory of a parallel computer system in which a plurality of systems each including a processor and a memory are connected via a connection network, a constant is set from a lower limit to an upper limit of an element of an iteration space corresponding to the loop. For associating the elements of the iteration space with the elements of the second array accessed by repeating the loop corresponding to the elements of the iteration space, and distributing the data optimally, In the optimal data distribution generation device that generates the parameters of the first array, The distance between the elements of the first array associated with the elements of the second array based on the prime distance and the distance between the elements of the second array accessed in a loop corresponding to the iteration space First means for generating a first array of elements of the first space of the iteration space associated with the first element of the iteration space and a loop corresponding to the first iteration of the iteration space. The element number of the second array, the lower limit of the area of the first array, and the second number generated by the first means.
Second means for generating an element number of the first array associated with a first element of the second array from a distance between elements of the first array associated with elements of the array;
The distance between the elements of the first array associated with the elements of the second array generated by the first means and the second
From the element number of the first array, the lower limit of the area of the first array, and the upper limit of the area of the first array, which are associated with the first element of the second array generated by the means of A third means for generating an element number of the first array associated with the last element of the array, the distance between the elements of the first array associated with the elements of the second array; The element number of the first array associated with the first element of the second array and the element number of the first array associated with the last element of the second array are the parameters. It is characterized by the following.

Further, according to the present invention, there is provided an optimum data distribution generating apparatus, wherein the distance between the elements of the first array associated with the elements of the second array accessed in a loop included in the program, and An element number of the first array associated with a first element of the second array, an element number of the first array associated with a last element of the second array, the parameter, and a second array Means for generating a data transfer pattern between the systems from an access attribute indicating whether or not is referred to or updated in a loop, between the elements of the third array corresponding to the elements of the second array The distance of the first element of the second array, the element number of the third array associated with the first element of the second array, and the element number of the third array associated with the last element of the second array are used as the parameters. Features That.

According to the compile processing apparatus of the present invention, a first array declared in a program including at least one loop composed of a plurality of repetitions is divided into regions, and each divided region is constituted by a processor and a memory. Compiling automatically for transferring data between the devices by using the program as input when the system is arranged in the memory of a parallel computer system in which a plurality of systems are connected via a connection network. In the processing device,
Means for performing syntax analysis and lexical analysis of an input program, converting the program to generate internal data to be processed in a compiler, and an access range of an array accessed in a loop in the program from the internal data Means for detecting an access attribute indicating whether access to the array is a reference or an update and adding the access attribute to the internal data; and, from the internal data, an element of an iteration space corresponding to a loop included in a program. Loop dispersing means for associating the first array with a constant interval from a lower limit to an upper limit, and elements of the first array associated with elements of a second array accessed in a loop corresponding to the iteration space The distance between the element number of the first array corresponding to the first element of the second array and the last element number of the second array Optimally associating the element numbers of the first array associated with the primes with the elements of the iteration space and the elements of the second array accessed by repeating the loop corresponding to the elements of the iteration space Means for generating a data transfer pattern between the systems from a parameter for distributing data and an access attribute indicating whether a second array is referred to or updated in a loop; A distance between the elements of the first array corresponding to the elements of the second array, and an element of the first array corresponding to the first element of the second array. A sequential program is converted to a parallel program using a number and an element number of the first array associated with the last element of the second array as the parameter. And wherein the door.

[0018]

DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described with reference to FIGS.

In the present invention, unlike the prior art, in executing a loop in a program, the repetition of the loop executed by each processor is determined by the same method as the array distribution method in the HPF. That is, the elements are associated with the array at regular intervals from the lower limit to the upper limit of the elements of the iteration space, and the alignment relationship between the iteration space and the array is represented by three sets of alignments similarly to the array.

Here, three sets of aligned l_loop, u_lo
where op and s_loop are respectively l_loop: the element of the array of the final alignment target associated with the first element of the iteration space, u
_Loop: element of the array of the final alignment target associated with the last element of the iteration space, s_loop
p: represents the distance between elements of the array of the final alignment target associated with the elements of the iteration space.

In the present invention, it is assumed that the range of the array accessed in the loop is given. This is called an array access range and is represented by l _access , u _access , and s _access, which are the lower limit of the elements of the array to be accessed, the upper limit of the elements of the array to be accessed, and the distance between the array elements to be accessed, respectively. .

The above three sets of loop alignment, access range,
By using the lower and upper bounds of the declared area of the final target array, the processor that executes the loop iteration and the processor to which the elements of the array accessed by the iteration are allocated are the same as follows. It is possible to obtain three sets of aligned arrays to be used as a processor.

First, when three sets of aligned sequences A are used, A
The element of the final alignment target to which (i) is associated can be obtained by the following equation.

F (i) = (i-LBOUND) × s + 1
{I | LBOUND ≦ i ≦ UBOUND} where LBOUND and UBOUND are the declared lower and upper bounds of the sequence to be the final alignment target, respectively. Also, the set of three alignments to be determined is {l_opt. : U_op
t. : S_opt. If｝, the following equation is established.

L _loop = F (l _access ) = (l _access -L
BOUND) × s_opt. + L_opt. u _loop = F (u _access ) = (u _access -LBOUND)
× s_opt. + L_opt. s _loop = s _access × s_opt. Therefore, from the above equation, the array alignment triples in which the processor that executes the loop iteration and the processor to which the elements of the array accessed in the iteration are allocated are the same processor should be obtained by the following equation. Can be.

S_opt. _{= S loop / s access (1} ) l_opt = l loop - (l access -LBOUND) × s_opt. (2) u_opt = (UBOUND−LBOUND) × s_opt. + L_opt (3) FIG. 5 shows a first embodiment of the optimum data distribution generating apparatus of the present invention using the equations (1) to (3). The apparatus includes a distance s_loop (0) between the elements of the first array, which is the final alignment target associated with the elements of the iteration space.
504) and the distance s_a between the elements of the second array accessed in the loop corresponding to the iteration space
access (0505) to the distance s_opt. between the elements of the first array associated with the elements of the second array according to equation (1). Means for generating (0510) (0501)
And an element l_loop (0506) of the first array associated with a first element of the iteration space
And an element number l_access (0507) of the second array accessed in the first iteration of the loop in the loop corresponding to the iteration space;
And the distance s_opt. Between the lower limit LBOUND (0508) of the region of the array of the first array and the element of the first array corresponding to the element of the second array. (0510) to element number l_opt. Of the first array associated with the first element of the second array according to equation (2). (0511) and a distance s_opt. Between the elements of the first array associated with the elements of the second array.
(0510) and the element number l_opt. Of the first array associated with the first element of the second array. (05
11) and the lower limit LBOUND (05
08) and the upper limit UBOUND (05
09) to element number u_op of the first array associated with the last element of the second array according to equations (3).
t. (0512).

S_opt. (0510), l_opt.
In the distribution of the array defined by (0511) and u_opt (0512), the processor that executes the loop iteration and the processor to which the elements of the array accessed by the iteration are allocated are the same processor.

FIG. 6 shows an example program. FIG.
The sequence A (0702) and the sequence B in the example program
(0701) shows the alignment relationship. Array B as shown
Are aligned with sequence A in three sets of alignments [1: 15: 1].
FIG. 8 shows how the arrays A and B are dispersed. The variance of array A is defined, which defines the variance of A and B. The elements associated by the alignment are assigned to the same processor (0804).

In the example program shown in FIG. 6, the initial value is 2, the final value is 15, the increment value is 1, and the size of the iteration space is 15 in the loop iteration. In this example, the iteration space (0901) is array A as shown in FIG.
(0702). At this time, three sets of alignments for the sequence A in the iteration space are [2: 16: 1].
It is. The access range of array B in the loop is [1: 15: 1], and the access range of array A is [2: 16: 1]. Therefore, equation (1)-
According to (3), the alignment triple set of array B such that the processor executing loop iteration and the processor to which elements of array B accessed in the iteration are allocated to the same processor is [2: 16: 1 ]. Similarly, the triad of sequence A is [1: 16: 1]. If sequence B is aligned with A by the alignment triad determined here, no matter how A is divided into regions,
Alternatively, even when the method of dividing the area of the array A is unknown, it is guaranteed that the processor executing the loop iteration and the elements of the array B accessed by the iteration are allocated to the same processor.

FIG. 10 shows a second optimum data distribution generating apparatus according to the present invention. (1006) is the distance between the elements of the first array that is the final alignment target associated with the elements of the second array and the elements of the first array that are associated with the first element of the second array The number and the element number of the first array associated with the last element of the second array, the parameter for optimally distributing data, and whether the second array is referenced or updated in a loop A data transfer pattern between the processors is generated from the access attribute that indicates the data. (1007) is equivalent to the device shown in FIG. 5, and the input (1003) is the input (0504) to (0) shown in FIG.
509). Also, the output of (1007) (10
04) are the outputs (0510) to (0512) shown in FIG.
Is equivalent to The input (1002) is the distance between the elements of the first array that is the final alignment target associated with the elements of the second array and the elements of the first array that are associated with the first element of the second array The input (1008) is a number and an element number of the first array corresponding to the last element of the second array, and the input (1008) is an access attribute indicating whether the array is referenced or updated in a loop.

If the attribute of the second array is a reference, the data transfer pattern generated by (1006) indicates that the element of the first array, which is the final alignment target associated with the element of the second array, A program defined by the distance of the first array and the element number of the first array associated with the first element of the second array and the element number of the first array associated with the last element of the second array This is a pattern for changing from the array distribution method declared in the above to the array distribution method determined by the parameter for optimally distributing data generated by the device (1007), and the attribute of the second array is updated. If the attribute of the second array is a reference from the distribution method to the array distribution method determined by the parameter for optimally distributing the data generated in (1007), Wherein a distance between elements of the first array is the final alignment targets associated with the elements of the column second
An array declared in a program defined by an element number of the first array corresponding to the first element of the array of the first array and an element number of the first array corresponding to the last element of the second array This is a pattern to change to the distribution method.

In the example program used in the first embodiment, the array B is a distribution method defined by a declaration in the program, the alignment triple set is [1: 15: 1], and the apparatus (1007)
Since the alignment triplet, which is a parameter for optimally distributing data generated by the above, is [2: 16: 1] and the access attribute is a reference, the data transfer pattern of array B is the alignment triplet [1:15: 1] is a change of the distribution method defined by the alignment triple [2: 16: 1] from the distribution method defined by [1].
This data transfer pattern can be uniquely obtained regardless of how the array A, which is the final alignment target, is divided into regions, or even if the method of dividing the region is unknown.

FIG. 11 shows an embodiment of the compiling apparatus of the present invention.

Hereinafter, the processing of each device will be described in detail using the program shown in FIG. 6 as an example program (1101) input to the compiling device.

The device (1103) performs syntax analysis / lexical analysis of the input program, converts the result, and generates an internal data format (1108) to be processed in the compiler. Details of syntax analysis / lexical analysis are described in the reference document “Programming Language Processing System” (Masataka Sasa, Iwanami Koza Software Science).

The internal data format generated here is shown in FIG.
Shown in Table for statements in the program (1216), table for loops (121
8), a table (1201) for variables is generated. (1216) is linked in statement order, and (1218) has pointers to the tables for the statements at the beginning and end of the loop. (120
1) has a variable name and a pointer to a table (1202) indicating the declaration range of each dimension only when the variable is an array. Also, tables (1206) and (1211) for storing the array shared information are generated for each variable, and linked from the table for the variable. (1206),
(1211) are three sets (1207) and (12
12) and division sizes (1208) and (1213). Further, it has pointers (1309) and (1314) to the conversion table of the array to be the final alignment target. The final alignment target for both sequence A and sequence B is sequence A
Therefore, it has a pointer to the table for the variable of A.

Next, the device (1104) is connected to the device (110).
With the data generated in 3) as input, an access attribute and an access range of an array accessed in the loop are obtained, added to the input data, and the data shown in FIG. 13 is output. ( ^* ) And (f) in the figure indicate that the lines are connected. The access attribute indicates whether the access of the array is reference or update in the loop, and is determined by whether the array appears on the left side or the right side of the statement.

In the example program of FIG. 6, the access attribute of array A is updated (1304), and the access attribute of array B is reference (1308). Also, since the subscript expression in the loop of array A is i, the lower limit of the loop is 2, and the upper limit is 16,
The access range of array A is [2: 16: 1] (130
5) Similarly, the access range of array B is [1: 15: 1]
(1309).

Next, the device (1105) is connected to the device (110).
Using the output data of 4) as input, the method of allocating each iteration of the loop to the processor is determined by the method shown in FIG. 9 using the first embodiment, and the result is added to the input data. The data shown in is output. The table (1402) representing the allocation result of the loop iteration is linked from the table (1218) corresponding to the loop (1414).
01), a pointer (1405) to a variable table serving as a final alignment target, an alignment triple (1403) for the final alignment target, and a division size (1404).

Next, the device (1106) is connected to the device (110).
The output data (1110) of 5) is input, and the input data is transformed in order to generate a required code for data transfer between processors. FIG. 15 shows the configuration of the device (1106). The input (1501) in the figure corresponds to the output of the device (1105).

The device (1106) includes a device (1503) for detecting the data transfer pattern shown in FIG. 10, and a device (1505) for generating a code for performing data transfer.
Consists of The input (1501) of the device (1503) is shown in FIG.
0 corresponds to the inputs (1001) to (1003). The device (1505) determines a code for performing data transfer to be generated and a position in the program where the code is to be inserted, from the data transfer pattern and the access attribute of the array detected by the device (1503). The code is inserted immediately before the loop when the access attribute is a reference, and immediately after the loop when the access attribute is an update. Further, a table corresponding to the statement of the code to be generated is generated and inserted into the determined position. FIG. 16 shows an example of internal data modified to insert a code for data transfer. A table (1601) is a group of tables corresponding to statements inserted to perform data transfer.

The device (1107) is the modified internal data of the compiler. This is a device that receives output data (1111) of the device (1106) as input, converts it, and outputs a parallel program (1102) that has been parallelized. FIG. 17 shows an output example of the device (1107). This is the code for performing data transfer with the call statement immediately before the loop inserted. In this case, the subroutine comm_pattern1 called by this call statement is constructed by a library for low-level interprocessor communication that is usually provided for each computer system.
That is, data transfer between processors is performed in this subroutine. In this case, a call statement that directly calls a library for low-level interprocessor communication may be generated.

[0043]

As described above, according to the present invention,
In a computer system in which devices having a processor and a memory are connected by a connection network, when a compile processing device converts a sequential program into a parallel program, even if the array distribution method is unknown at compile time, the array distribution is not Analysis of data transfer can be performed in the same way as is known at the time of compiling, and the analysis method is also facilitated.

[Brief description of the drawings]

FIG. 1 is a diagram showing an array distribution method in the HPF language.

FIG. 2 is a diagram showing an example program used to explain a description of an array distribution method in the HPF language.

FIG. 3 is a diagram showing a method of arranging arrays in an array distribution method in the HPF language.

FIG. 4 is a diagram showing an array division method in an array distribution method in the HPF language.

FIG. 5 is a diagram showing an embodiment of a first optimum data distribution generation device of the present invention.

FIG. 6 is a diagram showing an example program used to explain the present invention.

FIG. 7 is a diagram showing a method of distributing arrays in the example program of FIG. 6;

FIG. 8 is a diagram showing a method of distributing arrays in the example program of FIG. 6;

FIG. 9 is a diagram showing an iteration space.

FIG. 10 is a diagram showing an embodiment of the second optimal data distribution generation of the present invention.

FIG. 11 is a diagram showing an embodiment of a compile processing device of the present invention.

12 is a diagram showing input / output of each device of the compile processing device of FIG. 11;

FIG. 13 is a diagram showing input and output of each device of the compile processing device of FIG. 11;

FIG. 14 is a diagram showing input and output of each device of the compile processing device of FIG. 11;

FIG. 15 is a diagram showing a configuration of an apparatus 1106 in FIG. 11;

FIG. 16 is a diagram showing input and output of each device of the compile processing device of FIG. 11;

FIG. 17 is a diagram showing a program generated by the compile processing device of FIG. 11;

[Explanation of symbols]

0101 Array 0102 Array alignment 0103 Representative array 0104 Array distribution 0105 Processor 0301 Array A 0302 Alignment relationship between array A and array B 0303 Array B 0304 Alignment relationship between array B and array C 0306 Represents alignment relationship between array A and array C Parameter 0401 Method of dividing array C 0402 Method of dividing and arranging arrays A, B, and C on a processor 0501 Apparatus for calculating increment value of three sets of alignments 0502 Apparatus for calculating lower limit of three sets of alignments 0503 Device for calculating the upper limit 0504 The increment value of the alignment triple for the array in the iteration space 0505 The increment value of the access range of the array 0506 The initial value of the alignment triple for the array of the iteration space 0507 The lower limit of the access range of the array 0508 Declaration of the array 0509 Array access Upper limit of range 0510 Increment value of generated alignment triplet 0511 Lower limit of generated alignment triplet 0512 Upper limit of generated alignment triplet 0701 Array B 0702 Array A 0801 Partition size of arrays A and B 0901 Iteration space 0902 Processor allocation of loop iterations 1002 Alignment triad of declared array 1007 Device of FIG. 5 1003 Input of device of FIG. 5 1004 Device output of FIG. 5 1006 Device for detecting data transfer pattern 1005 Data transfer pattern 1008 Array is An access attribute 1101 indicating whether to be updated or referred to 1101 An input program 1102 of the compile processing device shown in FIG. 11 1102 Converted parallel program 1103 by the compile processing device into an internal data format processed inside the compile 1104 Apparatus for determining the access attribute and access range of an array accessed in a loop 1105 Apparatus for determining a loop repetition allocation method 1106 Apparatus for generating a code for performing data transfer 1107 Internal processing inside a compile A device that converts a data format into a source program and generates a parallel program 1103 to 1111 Input / output of each component of the compile processing device 1201 Variable table of array A 1202 Range of declared area of array A 1203 Conversion table of array B 1204 Range of declared area of array B 1205 Pointer for linking a plurality of variable tables 1206 Table for storing distributed information of array A 1207 Alignment triplet of array A 1208 Partition size of array A 1209 Final alignment target of array A 1210 Pointer to a table that stores shared information from the variable table of array A 1211 Table that stores shared information of array B 1212 Alignment triples of array B 1213 Partition size of array B 1214 last of array B Pointer to a variable table that is an alignment target 1215 Pointer to a table that stores distributed information of array B from a variable table of array B 1216 A table corresponding to the statement of the input program 1217 A pointer that links the statement table in the order of appearance of the statement 1218 loop 1219 Pointer to the table corresponding to the first statement of the loop 1220 Pointer to the table corresponding to the statement corresponding to the last statement of the loop 1301 Text of the loop Pointer to a table that stores the access information of the array that appears in the loop from the table 1302 Pointer that stores the access information of the array A 1303 Pointer from the table that stores the access information of the array A to the variable table of the array A 1304 Array A Access attribute 1305 Access range of array A 1306 Pointer storing access information of array B 1307 Pointer from table storing access information of array B to conversion table of array B 1308 Access attribute of array B 1309 Access range of array B 1401 Pointer to a table for storing the distributed information of the iteration space from the table of the loop 1402 Table for storing the distributed information of the iteration space 1403 Three sets of alignment of the iteration space 1404 Minutes of the iteration space Size 1405 Pointer to variable table of final alignment target from table storing distribution information of iteration space 1501 Data equivalent to FIG. 14 1502 Data equivalent to 1001 to 1003 1503 Data equivalent to device 1504 1005 in FIG. Device for Generating Transfer Code 1506 Data Equivalent to 1111 1601 Code for Performing Data Transfer Generated by Device of FIG.

Claims (3)

(57) [Claims] A first array declared in a program including at least one loop consisting of a plurality of repetitions is divided into regions, and a system in which each divided region is constituted by a processor and a memory forms a connection network. A plurality of parallel computer systems connected to each other via the memory in correspondence with the first array at regular intervals from the lower limit to the upper limit of the elements of the iteration space corresponding to the loop; And an element of the second array accessed by repeating a loop corresponding to an element of the iteration space to generate a parameter for optimally distributing data. A loop corresponding to the inter-element distance of the first array associated with an element of the iteration space and the iteration space First means for generating a distance between elements of the first array associated with elements of the second array from a distance between elements of the second array accessed in The element of the first array associated with the first element of the space and the element number of the second array accessed in the first iteration of the loop in the loop corresponding to the iteration space; The first element of the second array corresponds to the lower limit of the area of the first array and the distance between the elements of the first array associated with the elements of the second array generated by the first means. Second means for generating an element number of the first array to be attached; and a distance between elements of the first array corresponding to the elements of the second array generated by the first means. The second
From the element number of the first array, the lower limit of the area of the first array, and the upper limit of the area of the first array, which are associated with the first element of the second array generated by the means of A third means for generating an element number of the first array associated with the last element of the array; and a distance between the elements of the first array associated with the elements of the second array. The element number of the first array associated with the first element of the second array and the element number of the first array associated with the last element of the second array are the parameters. An optimal data distribution generation device, characterized in that: 2. A distance between elements of the first array associated with elements of a second array accessed in a loop included in the program and a first element of the second array. The element number of the first array, the element number of the first array, the parameter, and the second array corresponding to the last element of the second array are referenced or updated in a loop. Means for generating a data transfer pattern between the systems from an access attribute indicating whether or not the distance between the elements of the third array corresponding to the elements of the second array and the first of the second array The element number of the third array associated with the element of the third array and the element number of the third array associated with the last element of the second array are used as the parameters. Optimal data distribution generator Place. 3. A system in which a first array declared in a program including at least one loop consisting of a plurality of repetitions is divided into regions, and a system in which each divided region is constituted by a processor and a memory forms a connection network. When arranging in the memory of the parallel computer system which is connected to a plurality of devices via a computer, the compile processing device automatically generates a code for transferring data between the devices by using the program as an input. Means for performing syntax analysis and lexical analysis of the program, converting the program to generate internal data to be processed in a compiler, and an access range and an array of an array accessed from the internal data in a loop in the program An access attribute that indicates whether access to the device is a reference or an update is detected and added to the internal data. Loop dispersing means for associating an element of an iteration space corresponding to a loop included in a program from the internal data with a first array at fixed intervals from a lower limit to an upper limit; and a loop corresponding to the iteration space The distance between the elements of the first array associated with the elements of the second array accessed in and the element number of the first array associated with the first element of the second array; An element number of the first array corresponding to the last element of the second array, and an element of the iteration space and a second array accessed by repeating a loop corresponding to the element of the iteration space The system is determined from parameters for optimally distributing data by associating elements and access attributes indicating whether the second array is referenced or updated in a loop. Means for generating a data transfer pattern between programs, and means for generating a source program from the internal data, wherein a distance between elements of the first array corresponding to elements of the second array; The element number of the first array associated with the first element of the second array and the element number of the first array associated with the last element of the second array are used as the parameters. A compilation processing device for converting a program into a parallel program.