Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
1998-12-01
2001-08-28
Powell, Mark R. (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S152000, C717S152000
Reexamination Certificate
active
06282704
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to a method for analyzing array summaries without approximation for a loop containing a loop exit statement.
Parallel compilers execute a variety of transformations for parallelization of programs to improve the execution performance of the programs. The transformations for parallelization are primarily applied to loops. Arbitrary transformations for parallelization are not applicable to the loops, but it must be determined which transformations for parallelization are applicable.
The nucleus of determining whether transformations for parallelization are applicable is reference analysis of data within a loop. Data referenced within a loop include scalar variables and arrays. Each scalar variable always references the same memory area. In contrast to this, in the case of arrays, since different memory areas are referenced depending on the values of subscripts, it is necessary to analyze how which part of which array is referenced within a loop.
Accordingly, for parallel compilers to determine whether transformations for parallelization are applicable, an array summary analysis is developed to analyze the parts of each array referenced within a loop and the characteristics of the references. The array summary analysis is shown in M. Hall, B. Murphy, S. Amarasinghe, S. Liao, M. Lam, “Interprocedural analysis for parallelization, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing”, Springer-Verlag, August 1995.
A program example in
FIG. 4
will be used to describe an array summary analysis for determining whether transformations for parallelization called array privatization are applicable to an array A. The array summary analysis analyzes array reference to obtain an array summary in
FIG. 8
in a bottom-up fashion from the innermost loop toward outer loops while tracing the program in the reverse of program execution order.
In
FIG. 8
, R denotes a statement, a loop body, a loop, and other program parts. The loop body refers to all statements within a loop; for example, the body of a loop L
2
in
FIG. 4
is only a statement S
2
. The loop body of a loop L is hereinafter represented as L(body). The array summary of a loop body is an array summary for one iteration of the loop and the array summary of a loop is an array summary for all iterations of the loop.
An array summary of a statement S
2
becomes as shown in
FIG. 9
(
a
). Since the loop L
2
contains only the statement S
2
, the array summary of the loop L
2
body is the array summary itself of S
2
and becomes as shown in
FIG. 9
(
b
). By eliminating the loop control variable K of loop L
2
from the array summary of the loop L
2
body by using a variable elimination method such as the Fourier-Motzkin variable elimination method, the array summary of the loop L
2
becomes as shown in
FIG. 9
(
c
). By performing the same processing for a statement S
1
and a loop L
1
, the array summary of the loop L
1
becomes as shown in
FIG. 9
(
d
). Next, the array summary of loop L
0
body is obtained as shown in
FIG. 9
(
e
) from the array summaries of the loops L
1
and L
2
.
In
FIG. 9
(
e
), since ExposedRead of an array A becomes a null set in the loop L
0
body, it is appreciated that all parts of the array from which values are read at each iteration of L
0
have already been preset to values within the iteration. Hence, it is appreciated that, at each iteration of the loop L
0
, the values of array elements set in other iterations would not be read. Accordingly, by preparing a different array TA(1:N) for a different iteration of the loop L
0
as substitution of the array A, it is appreciated that the iterations of the loop L
0
can be executed independently of each other. The transformation of thus allocating arrays to memory areas independent of each other for each iteration is called array privatization.
Since array privatization allows the iterations of the loop L
0
to be executed independently, parallelization can be implemented as shown in FIG.
5
. DOALL indicates the beginning of a parallelization loop. A statement SO indicates that the memory area of array TA (1:N) is allocated individually for each iteration of a loop.
The above-described prior art states that an array summary analysis should be conducted with approximation when loop exit exists within a loop. However, no specific approximation method was described in the above-described prior art.
It is generally known that a set that may be referenced can be approximated with a set containing the actual set, while a set that must be referenced can be approximated with a set contained in the actual set. Therefore, an array summary analysis could also be conducted for a loop containing loop exit if, of array summaries for the loop, a set of parts of the array to which values may be written, a set of parts of the array from which values may be read, and a set of parts of the array from which values may be read before a value is written are approximated with array summaries without loop exit, while a set of parts of the array to which values must be written is approximated with a null set.
Thus, a method for conducting an array summary analysis for a loop containing loop exit is possible by expanding the prior art.
However, there was a problem in the above-mentioned expansion of the prior art in that analysis accuracy is degraded by approximation, and transformations for parallelization may be determined to be inapplicable although actually applicable.
For example, since a loop L
1
contains loop exit in a program in
FIG. 6
, a set MustWrite (L
1
) of parts of an array to which values must be written in the loop L
1
is approximated with a null set. For this reason, as shown in
FIG. 10
, a set [ExposedRead(L
0
(body))] of parts of an array from which values may be read before a value is written at each iteration of the loop L
0
body does not become a null set and it could not be determined that the array A can be privatized in the loop L
0
. Consequently, the loop L
0
could not be parallelized.
SUMMARY OF THE INVENTION
An object of this invention is to improve the accuracy of an array summary analysis of a loop containing a loop exit statement, thereby to improve applicability of array privatization.
To achieve the above object, according to a first invention, a method for analyzing array summary in a language processor that generates an object program from a source program, comprises: (a) a syntax analysis step for analyzing the syntax of the source program and generating intermediate code; (b) an array summary analysis step for generating, for each loop within the intermediate code, an array summary comprising a set of parts of an array to which values may be written in the loop, a set of parts of an array to which values must be written in the loop, a set of parts of an array from which values may be read in the loop, and a set of parts of an array from which values may be read before a value is written in the loop; (c) an array privatization step for allocating, based on the array summary, arrays to memory areas independent of each other for the loop within the intermediate code; (d) a loop parallelization step for performing parallelization for the loop within the intermediate code after transformation of the step (c); and (e) a code generation step for generating an object program for the intermediate code after transformation of the step (d). Furthermore, the step (b) includes: (f) a loop-exit-time control variable value array summary analysis step for computing, for a loop containing a loop exit statement and a statement that sets the value of a loop control variable at loop exit to a scalar variable, an array summary with the value of the scalar variable as the upper bound of the loop control variable.
Details of step (f) is that, if a loop exit statement and a statement that sets the value of a loop control variable at loop exit in a scalar variable are contained within a loop, the upper bound of the loop control variable of the loop is r
Booker Kelvin
Hitachi , Ltd.
Mattingly Stanger & Malur, P.C.
Powell Mark R.
LandOfFree
Method for analyzing array summary for loop including loop... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for analyzing array summary for loop including loop..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for analyzing array summary for loop including loop... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463264