JPH02132525A - How to compile - Google Patents

Abstract

(57) [Abstract] This bulletin contains application data before electronic filing, so abstract data is not recorded.

Description

[Detailed Description of the Invention] [Field of Industrial Application] The present invention relates to a parallel computer system, and in particular to a compilation method for generating object code suitable for parallel execution from a source program written for a single processor. Regarding the method. [Conventional technology] To improve calculation speed, multiple processors are lined up and run simultaneously. Parallel computer systems have been devised. A conventional source program coded for a single processor has data configured assuming a single memory. Even if these are placed in the main memory and executed in parallel, the values are not guaranteed because multiple processors read and write to the same address at any time, and the results may differ from those executed by a single processor. Put it away. To avoid this, it is sufficient to secure a work area for each processor and place a copy for each processor.

Furthermore, a conflict occurs on the main memory, making it impossible to ensure execution performance commensurate with the number of processors. To avoid this, it is necessary to effectively use the local memory provided for each processor.

The most advanced compiler that generates supercomputer (vector parallel computer) objects from source programs written in the FORTRAN language is
A compiler (Parafrase) of the Ceder project centered on the University of Illinois.Detailed paper on this, David A. Padua, Michael.
“Advanced Compiler Optimization for Supercomputers” co-authored by David A. PADUA,
MICHAEL J. 10LFB co-author “ADVANC”
ED COMPILER OPTIMIZATIONS
FORSUPER COMPUTER”) (Com
communications of the ACM, De
cember 1 9 8 6 Vol 2 9 Na
l. 2), but it does not describe the proper use of main memory and local memory, or the division and allocation of data. There is also no discussion of a specific method for a compiler to automatically divide data written in a conventional language and allocate it to main memory or local memory. [Problems to be solved by the invention] In conventional multiprocessor systems, multiple arithmetic units can be operated in parallel, but since there is only one main memory, memory conflicts are likely to occur, resulting in poor execution performance. In addition to impeding improvements in performance, the number of arithmetic units that can be connected has also been limited. On the other hand, in parallel computer systems that have local memory for each processor running in parallel, programs written for conventional single processors are unable to use the local memory effectively enough to improve execution performance commensurate with the number of machines. I can't. In order to bring out the performance of parallel machine execution, the user has to be aware of the local memory of each processor and recode it.

The present invention enables a parallel computer system having local memory for each processor to execute a source program coded for a conventional single processor by effectively utilizing the local memory without the user having to recode the program. The purpose is to generate highly efficient object code.

In addition, in a multiprocessor in which each processor accesses a shared memory, the purpose is to secure a work area in the shared memory according to the processor as appropriate, guarantee calculation results, and avoid conflicts.

[Means to solve the problem]

The above purpose is for the compiler to determine the parallel processing method by ``analyzing the user's parallelization instruction'' or ``automatically detecting parallelism,'' and then, in order not to impair this parallelism, to do the following: This is achieved by implementing the following processing.

First, they are classified as shown in FIG. 3 according to changes in the subscripts of variables and arrays that appear in the parallelization target part, and then the relationships of definitions and references are analyzed and classified as shown in FIG. 4.

Next, according to these classifications, divide variables and arrays and how to allocate them to main memory and local memory, as shown in Figure 5, so as not to impair the parallelism that has already been decided. . This classification follows the following principles:

(1) For an array that is accessed with an index linear to the number of loops, the defined value and the calculation formula that defines the value are placed in the same processor (the data is in its local memory).

(2) If the work is defined and referenced within one processor, it is expanded one dimension by the number of processors.

(3) Array elements that are defined in the middle of a program other than (2) are placed in only one local memory, and other processors access this through communication. (4) Variables and arrays whose values do not change during the program should be placed in the local memory of all processors that may reference them.

Finally, the program is converted into a form that can be executed in parallel according to the parallel processing method and determined data allocation.

In this way, object code with high execution efficiency can be generated by effectively using the local memory of each processor without recoding a conventional source program suitable for a single processor.

In a multiprocessor system where multiple processors access one shared memory, it is divided as shown in Figure 3 according to the changes in the subscripts of variables and arrays that appear in the parallelized part, and the relationships of definitions and references are further analyzed. and classify them as shown in Figure 4.

Next, according to these classifications, we classify whether it is necessary or unnecessary to secure work areas for variables and arrays, so as not to impair the parallelism that has already been decided. This classification principle differs from parallel computers, which store local memory in a distributed manner.

(1) Basically, all variables and arrays are placed in a global area in shared memory that can be accessed by all processors.

(2) If there is a possibility that each processor writes to the same address, such as an array, definition, or variable definition that is accessed with a loop-invariant index, the variable or array (or array element) should be retained for each processor. Place a local work area.

Finally, the program is converted into a form that can be executed in parallel according to the parallel processing method and determined data allocation.

In this way, object code with high execution efficiency can be generated for a multiprocessor in which shared memory is accessed by multiple processors, without recoding a conventional source program suitable for a single processor.

〔Example〕

Hereinafter, embodiments of the FORTRAN compiler of the present invention will be described with reference to figures and tables.

FIG. 1 shows the overall structure of a compiler to which the present invention is applied. A syntax analyzer 5 in FIG. 1 inputs the source program 2, analyzes the words and syntax, and generates an intermediate code 4.

A parallelization means determination process 6 inputs this intermediate code 4, and if the compiler does not have the ability to extract parallelism, asks the user for a parallelization instruction, and a user instruction analysis 15 determines a parallelization means based on the instruction. Further, if the compiler has sufficient parallelism analysis ability, the automatic parallelism detection processing 16 determines a parallel processing method. Next, the intermediate code 4 is converted into a form in which the parallel processing determined by the parallelization conversion 7 can be executed. And just like compiling for a single processor,
Optimization processing 8, memory allocation/register allocation 9, and code generation 10 are performed in sequence. The present invention relates to parallelization conversion 7, and by appropriately dividing data appearing in a source program into local memories of each processor operating in parallel,
This improves the execution efficiency of the object code 3 that is run in parallel.

A processing overview of parallelization conversion 7 for a program for which a parallel processing method has been determined is shown.

First, analysis 11 of the access state of variables and arrays in Figure 1 analyzes the definition for calculating values from the control flow and data flow, the order of reference using values, and the presence or absence of dependencies carried in loops. do.

Using this analysis result, classify variables and arrays in Fig. 12.
is classified into fields 31, 32, 33, 34, 35, and 36 of the variable/sequence classification table 30 in FIG. 3, and further into fields 41, 4 of the definition/reference table 40 in FIG.
Classified into 2, 43, 44, and 45.

An example of executing each iteration of the iterative process in parallel will be described with reference to FIG. 2. Loop 20 is the loop to be parallelized,
It is determined by parallelization means determination 6 in FIG. 1 that each of these repetitions be executed in parallel. The variables and arrays that appear here are classified as follows. First, they are classified into table 30 in FIG. Control variables I, J, K of loops 20, 21.22, final values N, M, S of statements 24 and 25, statement 2
3 MM is a variable and is stored in the feedle 31.

The arrays B and L of statements 24 and 27, and the subscripts K and J of LL, do not depend on the operation of the loop 20, so they are loop-invariant, and their values change. Therefore, arrays B, L, and LL are stored in field 32. On the other hand, since the subscript MM of array D in sentence 23 remains constant, D is in field 33.
Store in. Array E of sentence 23 and array F of sentence 26 and sentence 28
Since the subscript ■ is linear with respect to the repetition of the loop 20, it is stored in the field 34. Although the subscript of array A in statement 23 changes nonlinearly, the same array element is not accessed in different iterations. Array C in statement 27 is stored in field 36 because if there is an element with the same value in the L or LL array, the same element in array C will be accessed with a different number of loop repetitions. do.

Next, they are classified into table 40 in FIG. loop 20,2
The values of the final values N and M of 1.22, the array E of statement 23, the array D and its subscript MM, and the indirect fingers 41L and LL of array C of statement 27 are not updated in the parallelization target loop 20, It is only a reference and is stored in field 41. loop 20
control variable engineering, A of sentence 23, S of sentence 25, C of sentence 27,
Sentence 24, B, has a definition in only one place. Of these, B
Since a new value is immediately defined in the rube 29, the definition of the statement 24 does not reach the outside, and B is stored in the field 43. The remaining A, S, and C are loop 2 up to loop 29.
Since the value defined in 0 has arrived, field 42
Store it in . Inner loop control variables such as J and K are defined in two places because initial values are set before repetition and incremental values are added within the loop. These are loop 29,
Since a different value is defined without referring to the value, it is stored in field 45. F in two places, sentence 26 and sentence 28
Since there is a definition and the definition has reached up to loop 29, it is stored in field 44.

These table 30 in FIG. 3 and table 40 in FIG.
As input, determine how to divide variables and arrays in Figure 1 1
3 allocates variables and arrays to any of the divided button tables 50 in FIG.

Closing value guarantee is for the variables and arrays used throughout the program to be used in calculations after executing the loop in parallel, so that the arrays and variables retain the same values as when executed sequentially. This is to adjust the value at the end of the process. The value at this time is called the closing price. The closing price is stored in the main memory (M
It can be secured in the local memory (abbreviated as LS) or in the local memory (abbreviated as LS). However, do not store both the final values of all elements of the array and the work area in local memory.

FIG. 6 shows a determination rule for creating the table 50 in FIG. 5 from the tables 30 and 40 in FIGS. 3 and 4, in which the variable/array division method determination 13 creates the table 50 in FIG. Judgment 60 divides the variables into arrays, 7
1 prepares all variables in LS. According to decision 61, if the definition arrives outside the loop, 72 places a final value in the MS, otherwise no final value is needed. That is, if a variable in field 31 of table 30 in FIG. 3 is in field 42 or 44 in table 40 in FIG. 4, it is stored in field 54 of table 5o in FIG. 5. In the example of Figure 2, S is this 6 Fields 41, 43.4 in Figure 4
5, it is stored in field 59 in FIG. Second
In the example shown in the figure, these are N, M, MM, I, J, and K.

For arrays, if the determination 62 is only reference access, a determination 63 determines whether the subscript can be analyzed at compile time, and if it cannot be analyzed, a process 73 places all elements in all LSs. If analysis is possible, L of the reference processor
Place the element on S.

That is, the array in field 41 of table 40 in FIG. 4 is the same as fields 32, 33, . . . in table 30 in FIG.
34 corresponds to field 53 of table 50 in FIG. 5 by processing 74. In the example of Figure 2, L, LL, D, E
is this.

These depend on the form of definition in completely different parallel processing loops. Since the subscript of array D is always constant, D (M)
Place it in the work area of all LS. How D is used in other loops determines how the final value of D is divided. If D is linearly accessed in another loop, it is stored in field 58 of table 50.

Since the array E is accessed with a linear loop variable subscript and has no definition, no work area is required on the LS, and the final value is divided into each LS so that the processor only needs to refer to its own LS. This is field 53 of table 50.
Store in. Since all elements of arrays L and LL may be accessed by one processor, all elements are placed in all LSs. Also, other parallelized loops may refer to elements of L and LL, so this is not a work area.
It is stored in field 52 of table 50 as the final price. If the defined array is recognized as a loop-invariant subscript by the determination 64, a process 75 secures a work area in the LS. Further, if this definition reaches outside the loop, processing 75 secures the final value, but whether it is placed in MS or LS depends on the form of the definition of a completely different loop. Among the arrays in fields 32 and 33 of table 30 in FIG. 3, those in fields 42 and 44 of table 4o in FIG. 4 are stored in fields 56, 57, and 58 of table 50 in FIG. . The arrays in fields 43 and 45 of FIG. 4 are stored in field 59 of FIG. 5, and in the example of FIG. 2, this is B.

For loop-variable index arrays, decision 6o determines whether the index can be parsed at compile time, and if possible, if 67 determines that there is one definition, processing 77 determines whether the index is parsable at compile time. Divide so that each element is placed in LS. If there are multiple definitions, the output dependence is analyzed and the definition is divided so that each element is placed in the LS of the processor that calculates the definition of the end point. In the arrangement of field 34 of table 30 in FIG. 3, if it is in fields 42 and 44 of table 40 in FIG. 4, it is stored in field 52 of table 50 in FIG. , field 44 is divided by process 78.

Array F has two locations, sentence 26 and sentence 28 in FIG. Since the end point of output dependence is statement 26, it is divided according to this definition. For F, the definition of the starting point of output dependence (statement 26
) is unnecessary except when I=H, so no work area is required on the LS, and it is stored in the field 53 of the table 50 in FIG.

For arrays with subscripts that cannot be analyzed at compile time, a decision 68 determines whether an element is always defined with the same number of loops, and if it is always defined only with the same number of loops, a process 79 determines whether or not an element is always defined with the same number of loops. Divide so that each element is placed in the LS of the processor that performs the calculation. If a different number of loops are defined for one element, it cannot be executed in parallel, so the entire array is placed in the MS and executed sequentially.

The arrangement of field 35 of table 30 of FIG. 3 is equivalent to field 53 of FIG. 5, which is A in the example ' of FIG. Field 36 in FIG. 3 is replaced by field 51 in FIG.
In the example of FIG. 2, it is C.

After determining the data allocation method in this manner, the intermediate code conversion 14 in FIG. 1 is converted into a form that can be executed in parallel. As a result, the data of the source program shown in FIG. 2 becomes as shown in FIG. Data as shown in 9o is placed in the main memory.

Each LS stores data that will be used for a completely different purpose during the next parallel execution of work, as shown in 91.93, and 92.9.
As shown in 4, the data is divided into data to be held through one job and stored.

On the other hand, similar processing is also effective for multiprocessor systems in which multiple processors share one memory. However, since there is no local memory that is physically independent of main memory, there is a global area (97 in Figure 8) that is accessed by all processors in the main memory (96 in Figure 8), and a global area (97 in Figure 8) that is accessed by all processors. Prepare a local work area for each processor (Figure 8
8.99).

The final values of variables and arrays do not need to be divided, so they are stored together in the global area. Basically, the work variables and arrays shown in 91 and 93 in Figure 7 are placed in the local work area. However, among these... If the values of each LS are all the same, such as N, M, L, LL, D (M), which are used only for reference, there is no need to prepare them for the number of processors, so only one LS can be stored in the global area. put. The data of the program shown in FIG. 2 is as shown in FIG.

〔Effect of the invention〕

According to the present invention, it is possible to generate object code that is executed in parallel using local memory as effectively as possible, so when multiple processors are lined up and executed in parallel, data is stored in the main memory. It is possible to reduce the causes of deterioration in execution performance due to the occurrence of conflicts and improve the execution efficiency of objects running in parallel.

Additionally, since the compilation automatically divides and allocates data, it has the effect of easing the burden on users who try to run a program coded for a single processor on a parallel computer.

[Brief explanation of drawings]

FIG. 1 is an overall configuration diagram of a compiler according to an embodiment of the present invention.
Figure 2 is an example of a source program for explaining the embodiment, Figure 3 is a classification table of variables and arrays, and Figure 4 is a definition and
The reference table, Figure 5 is the division button table, Figure 6 is an overview of the process of determining the division method for variables and arrays, and Figure 7 is the second
FIG. 8 is a diagram showing the result of dividing the source program data of FIG. 2 into a shared memory type parallel machine. 1... FORTRAN compiler, 2... Source program, 3... Object code, 4... Intermediate code, 5... Syntax analysis, 6... Parallelization means determination process, 7... Parallelism conversion, 8... optimization processing, 9...
・Memory allocation/register allocation, 1o...Code generation, 11...Analysis of variable/array access status, 12.
...Classification of variables/arrays, 13...Determination of allocation method of variables/arrays, 14...Intermediate code conversion, 2o...Loop to be parallelized, 21, 22...Loop, 23, 24,
25, 26, 27. 28... Executable statement, 29... Loop, 30... Variable/array classification table, 31, 32
, 33, 34, 35. 36... Each field of the variable/array classification table, 40... Constant/reference table,
41, 42, 43, 44, 45...Each field of definition/reference table, 50...Divided button table, 5
1, 52, 53, 54, 55, 56, 57, 58, 59
...Each field of the split button table. 60,61
, 62, 63, 64, 65, 66, 67. 68... Judgment process for determining division method, 71, 72, 73, 74
, 75, 76, 77, 78, 79, 80... Division/allocation processing, 9o... Main memory, 91, 92, 93,
94...Local memory, 96...Memory (shared)
Memory, 97...Global area, 98.99...
・Local work area for each processor. Fig. 1L0 Y Fig.

Claims (1)

[Claims] 1. For a parallel computer composed of a plurality of processors each having a local memory corresponding to each processor,
Performs syntax analysis on a user-written source program coded for a conventional single processor with one memory space, generates intermediate code,
Using this intermediate code as input, it determines the parallel processing method by analyzing the user's parallelization instructions or by automatically detecting parallelism of the compiler, and converts the intermediate code to parallelism so that it is executed on each processor according to this decision. , After this, in the compilation method that performs optimization, allocates computer resources, allocates memory and allocates registers, and generates object code, when performing parallelization conversion on the intermediate word after the above determination, variables are Analyze the access status of variables and arrays, classify them into several types, and decide whether to place variables and arrays in main memory, local memory, or just one place according to this classification.
A compilation method characterized by determining whether there are multiple locations, determining the division of data (variables and arrays) according to this, and converting intermediate code into a form that can be executed by each processor. 2. A source program coded for a conventional single processor with only one memory space written by the user, as opposed to a multiprocessor consisting of multiple processors running in parallel and one shared memory that can be accessed by them. , performs syntax analysis to generate intermediate code, uses this intermediate code as input, determines the parallel processing method by analyzing the user's parallel instructions or automatically detects parallelism during compilation, and generates the intermediate code according to this parallelization method. After the above decision, in the compilation method that parallelizes the code so that it is executed on each processor, performs optimization, allocates computer resources, allocates memory and registers, and generates object code. When performing parallelization conversion on intermediate words, we analyze the access status of variables and arrays, classify them into several types,
In line with this, all or part of variables and arrays are arrayed for the number of processors, and it is decided whether to have copies or not, and according to this, data (variables and arrays)
A compilation method characterized by determining the allocation of the code and converting the intermediate code into a form that can be executed on each processor.