Program generation device, program production method, and program

A program generation apparatus references a source program including a loop for executing a block N times (N≧2) and having such dependence that a variable defined in a statement in the block pertaining to ith execution (1≦i<N) is referenced by a statement in the block pertaining to jth execution (i<j≦N), calculates equivalent representations of variables in the block pertaining to the ith execution and the block pertaining to any other execution than the ith execution, specifies, with respect to each representation of a target variable causing the dependence, a representation of a variable not causing the dependence that is equivalent to the representation of the target variable, and generates a program being for executing the block M times (M≦N) and including a statement including the specified representation in place of each representation of the target variable.

TECHNICAL FIELD

The present invention relates to technology for generating a new program by referencing a source program including a loop.

BACKGROUND ART

There are a known compiler and the like that each generate, by referencing a source program including a loop, a new program to be shared and executed by a plurality of processors to execute predetermined processing to be realized by the loop (e.g. Patent Literature 1).

Here, the loop is for executing a block composed of one or more statements N (N≧2) times.

According to the technology disclosed in Patent Literature 1, it is possible to generate a new program configured to, for example, divide the loop for executing the block N times into two partial loops that are each for executing the block N/2 times and are to be independently executed in parallel by two processors. Therefore, with the technology disclosed in Patent Literature 1, the loop for executing the block N times is executed at high speed.

CITATION LIST

Patent Literature

Summary of Invention

Technical Problem

The method disclosed in Patent Literature 1, however, is inapplicable to a case where the source program includes the loop and has such dependence that a variable defined in a statement in the block pertaining to the ith(1≦i<N) execution is referenced by a statement in the block pertaining to the jth(i<j≦N) execution. That is to say, with the method disclosed in Patent Literature 1, a program to be executed by a plurality of processors to execute predetermined processing to be realized by the loop at high speed is not generated from a source program including the loop and having such dependence.

The present invention has been conceived in view of the above problem. A purpose of the present invention is to provide a program generation apparatus that is useful in generating, by referencing the source program including the loop and having the above-mentioned dependence, the program to be executed by a plurality of processors to execute the predetermined processing to be realized by the loop at high speed.

Solution to Problem

In order to solve the above-presented problem, one aspect of the present invention is a program generation apparatus for generating a program by referencing a source program including a loop for executing a block composed of one or more statements N times (N≧2), the source program having such dependence that a variable defined in a statement in the block pertaining to ithexecution (1≦i<N) is referenced by a statement in the block pertaining to jthexecution (i<j≦N), the program generation apparatus comprising: a calculation unit configured to calculate equivalence relations between representations of variables included in the block pertaining to the ithexecution and the block pertaining to any other execution than the ithexecution; a specification unit configured to specify, with respect to each of representations of any target variable causing the dependence among the variables, a representation of a variable not causing the dependence that is equivalent to the representation of the target variable among the variables, based on the equivalence relations calculated by the calculation unit; and a generation unit configured to generate a program so that the generated program is for executing the block M times (M≦N) and includes a statement including the representation of the variable specified by the specification unit.

Advantageous Effects of Invention

The program generation apparatus of the present invention having the above-mentioned configuration is capable of generating, by referencing the source program including the loop and having the above-mentioned dependence, the program to be executed by a plurality of processors to execute the predetermined processing to be realized by the loop at high speed.

DESCRIPTION OF EMBODIMENT

The following describes an embodiment of the present invention with reference to the drawings.

Embodiment

Outline

FIGS. 2A and 2Brespectively illustrate equivalent partial programs P1and P4from which the same results can be obtained with respect to an array b[k] (0≦k≦99) upon completion of execution.

A program generation apparatus in the present embodiment is obtained by improving a conventional compiler. The program generation apparatus in the present embodiment generates, by referencing a source program including the partial program P1illustrated inFIG. 2A, an assembler program similar to an assembler program that the conventional compiler can generate by referencing a source program including the partial program P4illustrated inFIG. 2B, which is generated in advance by a programmer.

Here, the partial program P1includes a loop R1and has true dependence. Although details of the true dependence are described later, the true dependence is such dependence that a variable defined in a statement in a block B1to be executed when a loop control variable k is i (0≦i<99) is referenced by a statement in the block B1to be executed when the loop control variable k is i+1.

If statements between which there is the true dependence are executed in reverse order, correct results cannot be obtained. Therefore, the block B1is generally sequentially executed with incrementing the loop control variable k by one.

On the other hand, the partial program P4including a loop R4does not have the true dependence as described above. Therefore, the partial program P4is executable by a plurality of processors. For example, the loop R4may be divided into a partial loop to be executed when the loop control variable k is 0 to 49 and a partial loop to be executed when the loop control variable k is 50 to 99, and two processors may independently execute the partial loops in parallel. By the above-mentioned method, the predetermined processing to be realized by the loop is executed at higher speed, compared with a case where a single processer sequentially executes the block B1while the loop control variables k is 0 to 99.

As described above, the program generation apparatus in the present embodiment generates, by referencing a source program including the partial program P1illustrated inFIG. 2A, an assembler program similar to an assembler program that the conventional compiler can generate by referencing a source program including the partial program P4illustrated inFIG. 2B.

Therefore, the program generation apparatus in the present embodiment is effective in generating an assembler program suitable for parallel execution without regenerating a source program, such as the partial program P4, including a loop and not having the true dependence, when a source program, such as the partial program P1, including a loop and having the true dependence has already generated.

Although the partial program P1includes the loop R1and has the true dependence as described above, the partial program P1is more suitable for high-speed execution by a single processor than the partial program P4for the following reason.

It is generally known that a program is executed at higher speed by allocating, to registers, as many variables in the program as possible. This is because access to the register is provided at higher speed than access to a memory.

In a general compiler, it is likely that a specific register is allocated to a simple variable such as a0, a1and a2included in the partial program P1. Therefore, the number of accesses to the memory is reduced when the partial program P1is executed, compared with a case where the partial program P4is executed. That is to say, when a single processor is used, the partial program P1is executed at higher speed than the partial program P4.

The following describes data dependence including the above-mentioned true dependence, with use ofFIG. 3.

As illustrated inFIG. 3, a variable “a” defined in a statement ST100is referenced by a statement ST200to be executed after the statement ST100is executed. In such a case, there is “true dependence” of the statement ST200on the statement ST100.

Also as illustrated inFIG. 3, the variable “a” referenced by the statement ST200is defined in a statement ST300to be executed after the statement ST200is executed. In such a case, there is “anti-dependence” of the statement ST300on the statement ST200.

Also as illustrated inFIG. 3, the variable “a” defined in the statement ST100is redefined in the statement ST300. In such a case, there is “output dependence” of the statement ST300on the statement ST100.

Hereinafter, a variable causing the true dependence, the anti-dependence and the output dependence is referred to as a “dependence-causing variable”. In an example illustrated inFIG. 3, the variable “a” is the dependence-causing variable.

It is known that the “anti-dependence” and the “output dependence” are removed by renaming the dependence-causing variable so that representations of the dependence-causing variable are different from each other in statements between which there is the dependence (see, for example, page 113 of Non-Patent Literature 1). Therefore, the “anti-dependence” and the “output dependence” are sometimes called “name dependence”.

The data dependence is specifically described below by taking the loop R1included in the above-mentioned partial program P1as an example.

FIGS. 4A and 4Billustrate the data dependence in the loop R1illustrated inFIG. 2A.

Hereinafter, a block in a loop to be executed when the loop control variable is m (m is a given value that the loop control variable can take) is referred to as an “iteration m”, generating the iteration m is referred to as “expanding the iteration with respect to m”, and the value m is referred to as an “iteration number”.

FIG. 4Aillustrates the block B1to be executed when the loop control variable k in the loop R1illustrated inFIG. 2is 0, i.e. an iteration0.FIG. 4Billustrates an iteration1.

That is to say, there is the true dependence of the statement ST21on the statement ST12caused by the variable a0. Also, there are the true dependence of the statement ST21on the statement ST13caused by the variable a1and the true dependence of ST22on the statement ST13caused by the variable a1. Furthermore, there are the true dependence of the statements ST21on the statement ST14caused by the variable a2and the true dependence of the statement ST23on the statement ST14caused by the variable a2.

Also, the variable a0defined in the statement ST12in the iteration0illustrated inFIG. 4Ais redefined in the statement ST22in the iteration1illustrated inFIG. 4B.

That is to say, there is the output dependence of the statement ST22on the statement ST12caused by the variable a0. Similarly, there are the output dependence of the statement ST23on the statement ST13caused by the variable a1and the output dependence of the statement ST24on the statement ST14caused by the variable a2.

Also, the variables a0, a1and a2referenced by the statement ST21in the iteration1illustrated inFIG. 4Bare respectively defined in the statements ST22, ST23and ST24. That is to say, there are the anti-dependence of the statement ST22on the statement ST21caused by the variable a0, the anti-dependence of the statement ST23on the statement ST21caused by the variable a1, and the anti-dependence of the statement ST24on the statement ST21caused by the variable a2.

Similarly, there is the anti-dependence caused by the variables a0, a1and a2in the iteration0.

Note that, hereinafter, the dependence of a statement in a given iteration on a statement of another iteration of the loop is also referred to as “dependence between iterations”.

FIG. 1is a block diagram illustrating a configuration of a compiler system1000including a program generation apparatus100in the present embodiment.

The compiler system1000generates, by referencing a source program11, such as the partial program P1described above, including a loop and having the true dependence between iterations, an object program14to be executed in parallel by a plurality of processors to execute the predetermined processing to be realized by the loop.

The compiler system1000is embodied as a computer (e.g. PC (Personal Computer)) including a processor (not illustrated), a memory (not illustrated) and a storage device10such as a hard disk.

As illustrated inFIG. 1, the compiler system1000includes the storage device10, the program generation apparatus100, an assembler210and a linker220. Note that functions of the program generation apparatus100, the assembler210and the linker220are implemented by the above-mentioned processor reading, into the above-mentioned memory, a program (not illustrated) stored in the storage device10and executing the read program.

Here, the program generation apparatus100is obtained by improving a conventional compiler. The program generation apparatus100has a function of generating an assembler program12by referencing the source program11stored in the storage device10and written in a high-level language such as the C language and the C++ language. The program generation apparatus100stores the generated assembler program12in the storage device10.

That is to say, the program generation apparatus100generates, by referencing the source program11including the loop and having the true dependence between iterations, the assembler program12that is for executing the predetermined processing to be realized by the loop and does not have the true dependence.

The assembler210has a function of generating, by referencing the assembler program12stored in the storage device10by the program generation apparatus100, a relocatable binary program13written in a machine language. The assembler210stores the generated relocatable binary program13in the storage device10.

The linker220has a function of generating the object program14executable by a computer, by determining a location of an address and the like of unresolved data in the relocatable binary program13stored in the storage device10by the assembler210, and linking a necessary library and the like with the relocatable binary program13in which the location of an address and the like of unresolved data are determined. The linker220stores the generated object program14in the storage device10.

The following describes a configuration of the program generation apparatus100in more detail, with use ofFIG. 1.

As illustrated inFIG. 1, the program generation apparatus100includes a storage unit110, an acquisition unit120, a calculation unit130, a specification unit140and a generation unit150.

The storage unit110is a memory area for storing therein the source program11and results of processing performed by the calculation unit130, the specification unit140and the generation unit150.

That is to say, the results of processing are exchanged among the calculation unit130, the specification unit140and the generation unit150via the storage unit110, although this is hereinafter not specified.

The acquisition unit120has a function of reading the source program11from the storage device10and storing the read source program11in the storage unit110.

The calculation unit130has a function of calculating equivalence relations between representations of variables with respect to a given iteration and other one or more iterations of the loop included in the source program11stored in the storage unit110by the acquisition unit120. The calculation unit130includes an iteration expansion unit131, a name dependence removal unit132and an equivalence relation calculation unit133.

The iteration expansion unit131has a function of expanding iterations based on the loop included in the source program11.

The name dependence removal unit132has a function of removing the name dependence (i.e. the output dependence and the anti-dependence) between two iterations having been expanded by the iteration expansion unit131and having consecutive iteration numbers.

Here, the name dependence is removed by a method similar to a conventional method of renaming the dependence-causing variable so that representations of the dependence-causing variable are different from each other in two statements between which there is the dependence.

The equivalence relation calculation unit133has a function of calculating equivalence relations between representations of variables with respect to statements in the two iterations from which the name dependence has been removed by the name dependence removal unit132. Here, the equivalence relations between representations of variables are calculated by a method similar to the method disclosed in Patent Literature 2.

The specification unit140has a function of judging whether nor not all true dependence can be removed by replacing all true dependence-causing variables in the two iterations with other equivalent variables not causing the true dependence or expressions, based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133.

The specification unit140also has a function of, based on results of the judgment, controlling the calculation of the equivalence relations between representations of variables performed by the calculation unit130, and judging whether or not a block of the loop included in the source program11can be replaced with a candidate modified iteration (described later) generated by the generation unit150.

The generation unit150has a function of generating, when the specification unit140judges that all true dependence between the two iterations can be removed, the candidate modified iteration based on the iteration from which all true dependence has been removed.

Although details of the candidate modified iteration are described later (seeFIGS. 13A and 13B), the candidate modified iteration is obtained by generalizing the above-mentioned iteration from which all true dependence has been removed so that the iteration from which all true dependence has been removed can be applied to other iterations having greater iteration numbers.

The generation unit150has a function of generating the assembler program12when the specification unit140judges that the block of the loop included in the source program11can be replaced with the candidate modified iteration. The assembler program12is generated based on a source program obtained by replacing the block of the loop included in the source program11with the candidate modified iteration.

The following describes operations of the program generation apparatus100.

FIGS. 5,6and7are each flow charts showing program generation processing performed by the program generation apparatus100.

The acquisition unit120included in the program generation apparatus100reads the source program11from the storage device10and stores the read source program11in the storage unit110. The iteration expansion unit131included in the calculation unit130expands the iteration with respect to i, which is a given value that the loop control variable in the loop included in the source program11can take, and i+1 (step S1inFIG. 5).

The name dependence removal unit132included in the calculation unit130specifies the dependence between statements in the iteration i and the iteration i+1 (step S2). The name dependence removal unit132also removes the name dependence (i.e. the output dependence and the anti-dependence) by changing a representation of the name dependence-causing variable (step S3).

The equivalence relation calculation unit133included in the calculation unit130calculates equivalence relations between representations of variables with respect to statements in the iteration i and the iteration i+1 from which the name dependence has been removed (step S4).

Since being similar to the method disclosed in Patent Literature 2 as described above, the method of calculating the equivalence relations between representations of variables is briefly described below. As a result of the calculation, a set of equality expressions as illustrated inFIGS. 10A and 10Bis obtained.

Here, inFIGS. 10A and 10B, one or more expressions enclosed in the parentheses “{” and “}” are collectively referred to as the “set of equality expressions”, and an expression included in the set of equality expressions and enclosed in the parentheses “(” and “)” is referred to as the “equality expression”. Elements included in each of the equality expressions and separated by commas are equivalent to one another.

First, the equivalence relation calculation unit133performs the following processing for statements in the iteration i and the iteration i+1 one by one.

That is to say, the equivalence relation calculation unit133judges whether or not the equality expression including a variable or an expression on the right or left side of each statement is already included in the set of equality expressions.

When judging that the equality expression is not included in the set of equality expressions, the equivalence relation calculation unit133adds a new equality expression for the statement to the set of equality expressions.

When judging that the equality expression including a variable or an expression on the right side of the statement is already included in the set of equality expressions, the equivalence relation calculation unit133adds a variable or an expression on the left side of the statement as an element of the equality expression.

When judging that the equality expression including the variable or the expression on the left side of the statement is already included in the set of equality expressions, the equivalence relation calculation unit133adds, in place of the equality expression, a new equality expression for the statement to the set of equality expressions.

The following describes subsequent steps of the program generation processing (seeFIG. 5).

Upon completion of the processing in the step S4, the specification unit140judges whether or not all true dependence can be removed based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133(step S5).

More specifically, the specification unit140judges that all true dependence can be removed when all true dependence-causing variables can be replaced with equivalent variables other than the dependence-causing variables specified in the step2and variables introduced to remove the name dependence in the step S3, or expressions, based on the equivalence relations between representations of variables calculated in the step S4(step S5: YES).

Here, the true dependence-causing variables are replaced with neither the dependence-causing variables specified in the step2nor variables introduced to remove the name dependence in the step S3, because such variables can cause new dependence in other iterations. That is to say, even when the true dependence-causing variables are replaced with such variables, there is a possibility that the dependence between iterations is not eventually removed.

When judging that all true dependence can be removed (step S5: YES), the specification unit140sets the value of m to “1” in the iteration i+m from which all true dependence has been removed (step S6), and processing proceeds to a step S15inFIG. 6.

When judging that all true dependence cannot be removed (step S5: NO), the specification unit140sets the value of m to “2” (step S7inFIG. 6).

The specification unit140then judges whether or not the value of m is smaller than a value obtained by subtracting a minimum value (hereinafter, a “kmin”) that the loop control variable included in the source program11can take from a maximum value (hereinafter, a “kmax”) that the loop control variable included in the source program11can take (step S8).

When the value of m is equal to or greater than the value obtained by subtracting the kmin from the kmax (step S8: NO), the program generation apparatus100terminates the program generation processing for failing to remove the true dependence (seeFIG. 7).

On the other hand, when the value of m is smaller than the value obtained by subtracting the kmin from the kmax (step S8: YES), the specification unit140notifies the calculation unit130of the value of m to instruct the calculation unit130to perform processing. The iteration expansion unit131included in the calculation unit130having been instructed to perform processing expands the iteration with respect to i+m, similarly to the processing in the step S1(step S9).

The name dependence removal unit132specifies the dependence between statements in the iteration i+m−1 and the iteration i+m, similarly to the processing in the step S2(step S10), and removes the name dependence, similarly to the processing in the step S3(step S11).

The equivalence relation calculation unit133calculates equivalence relations between representations of variables with respect to statements in the iteration i+m−1 and the iteration i+m from which the name dependence has been removed, similarly to the processing in the step S4(step S12).

The specification unit140then judges whether or not all true dependence can be removed based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133in the step S12, similarly to the processing in the step S5(step S13).

Here, the specification unit140uses, as the representations of variables for replacing the representations of the true dependence-causing variables, neither the dependence-causing variables specified in the steps S2and S10nor variables introduced to remove the name dependence in the steps S3and S11, for a similar reason as that described regarding the step S5.

When judging that all true dependence cannot be removed (step S13: NO), the specification unit140increments the value of m by one (step S14) and repeats the processing in the step S8onward.

When the specification unit140judges that all true dependence can be removed (step S13: YES), the generation unit150generates the candidate modified iteration based on the iteration i+m from which all true dependence has been removed (step S15).

Here, the value i is a given value that the loop control variable in the loop included in the source program11can take. Therefore, the fact that all true dependence can be removed in the iteration i+m indicates that all true dependence can be removed in the iterations having iteration numbers equal to or greater than kmin+m.

The generation unit150thus generates the candidate modified iteration that is obtained by generalizing the iteration i+m from which all true dependence has been removed so that the iteration i+m from which all true dependence has been removed can be applied to other iterations having iteration numbers from kmin+m to kmax.

The specification unit140then notifies the calculation unit130of the values of kmin and m−1 to instruct the calculation unit130to perform processing. The iteration expansion unit131included in the calculation unit130having been instructed to perform processing expands the iterations with respect to kmin to m−1, similarly to the processing in the step S1(step S16inFIG. 7).

Also, the name dependence removal unit132specifies the dependence between statements in the iterations kmin to m−1, similarly to the processing in the step S2(step S17), and removes the name dependence, similarly to the processing in the step S3(step S18).

The equivalence relation calculation unit133calculates equivalence relations between representations of variables with respect to statements in the iterations kmin to m−1 from which the name dependence has been removed, similarly to the processing in the step S4(step S19).

The specification unit140then judges whether or not all true dependence can be removed based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133in the step S19, similarly to the processing in the step S5(step S20).

When the specification unit140judges that all true dependence cannot be removed (step S20: NO), the program generation apparatus100terminates the program generation processing for failing to remove the true dependence when the loop control variable is kmin to m−1.

When judging that all true dependence can be removed (step S20: YES), the specification unit140judges whether or not the iterations kmin to m−1 from which all true dependence has been removed are the same as the iterations kmin to m−1 applied to the candidate modified iteration generated in the step S15(step S21).

When the specification unit140judges that they are not the same (step S21: NO), the program generation apparatus100terminates the program generation processing. This is because, in this case, (i) the program that includes the loop applicable when the loop control variable is kmin to m−1 and does not have the true dependence and (ii) the program that includes the loop applicable when the loop control variable is m to kmax and does not have the true dependence cannot be put together into a program including a single loop.

On the other hand, when the specification unit140judges that they are the same (step S21: YES), the generation unit150generates the assembler program12in the following manner (step S22). That is to say, the generation unit150generates the assembler program12by optimizing and parallelizing a program that is obtained by replacing the block of the loop included in the source program11with the candidate modified iteration.

The optimization and the parallelization are achieved by a method conventionally used. Therefore, detailed descriptions thereof are omitted, and a specific example of the program obtained after the optimization and the parallelization is described later (seeFIG. 18).

The generation unit150stores the generated assembler program12in the storage device10, and thus the program generation apparatus100terminates the program generation processing.

Specific Example

The following describes operations of the program generation apparatus100in accordance with the flow charts ofFIGS. 5,6and7by taking, as an example, a case where the source program11includes the partial program P1illustrated inFIG. 2A.

The acquisition unit120included in the program generation apparatus100reads the source program11from the storage device10and stores the read source program11in the storage unit110. The iteration expansion unit131included in the calculation unit130expands the iteration with respect to i, which is a given value that the loop control variable (k in this example) in the loop (R1in this example) included in the source program11can take, and i+1 (step S1inFIG. 5).

FIGS. 8A and 8Brespectively illustrate the iteration i and the iteration i+1 of the loop R1illustrated inFIG. 2A.

The name dependence removal unit132included in the calculation unit130specifies the dependence between statements in the iteration i and the iteration i+1 (step S2). The name dependence removal unit132also removes the name dependence (i.e. the output dependence and the anti-dependence) by changing the representation of the name dependence-causing variable (step S3).

In the example illustrated inFIGS. 8A and 8B, there are the true dependence of the statement ST51on the statement ST42, the output dependence of ST52on the statement ST42, the anti-dependence of the statement ST42on the statement ST41and the anti-dependence of the statement ST52on the statement ST51. All the dependence is caused by the variable a0.

Also, there are the true dependence of the statement ST51on the statement ST43, the output dependence of ST53on the statement ST43, the anti-dependence of the statement ST43on the statement ST41and the anti-dependence of the statement ST53on the statement ST51. All the dependence is caused by the variable a1.

Furthermore, there are the true dependence of the statement ST51on the statement ST44, the output dependence of ST54on the statement ST44, the anti-dependence of the statement ST44on the statement ST41and the anti-dependence of the statement ST54on the statement ST51. All the dependence is caused by the variable a2.

The name dependence caused by the variable a0can be removed by replacing the representation of the variable a0in the statement ST42with “a0_i” and by replacing the representation of the variable a0in the statement ST52with “a0_i1”.

Similarly to the case of the variable a0, the name dependence caused by the variable a1can be removed by replacing the representation of the variable a1in the statement ST43with “a1_i” and by replacing the representation of the variable a1in the statement ST53with “a1_i1”. Also, the name dependence caused by the variable a2can be removed by replacing the representation of the variable a2in the statement ST44with “a2_i” and by replacing the representation of the variable a2in the statement ST54with “a2_i1”.

FIG. 9Aillustrates the iteration i illustrated inFIG. 8Afrom which the name dependence has been removed.FIG. 9Billustrates the iteration i+1 illustrated inFIG. 8Bfrom which the name dependence has been removed.

Note that, since only the name dependence is removed in the step S3, there is the true dependence remaining. That is to say, in the example illustrated inFIGS. 9A and 9B, there is the true dependence of the statement ST55on the statement ST46caused by the variable a0_i, the true dependence of the statement ST55on the statement ST47caused by the variable a1_i, the true dependence of the statement ST55on the statement ST48caused by the variable a2_i, the true dependence of the statement ST56on the statement ST47caused by the variable a1_i and the true dependence of the statement ST57on the statement ST48caused by the variable a2_i.

The equivalence relation calculation unit133included in the calculation unit130calculates equivalence relations between representations of variables with respect to statements in the iteration i and the iteration i+1 from which the name dependence has been removed (step S4).

The following describes the equivalence relations between representations of variables with respect to statements (ST45, ST46, ST47, ST48and ST55, ST56, ST57, ST58) in the iteration i and the iteration i+1 respectively illustrated inFIGS. 9A and 9Bfrom which the name dependence has been removed.

Assume that no equality expression is included in a set of equality expressions at the beginning of the following description.

When the equivalence relations between representations of variables with respect to the statement ST45are calculated, the equality expressions including a variable or an expression on the right and left sides of the statement ST45are not included in the set of equality expressions. Therefore, the equality expressions with respect to the statement ST45are added to the set of equality expressions as illustrated in a set of equality expressions E45illustrated inFIG. 10A.

That is to say, the set of equality expressions E45indicates that the variable “b[i]” and the expression “a0+a1+a2” are equivalent immediately after the statement ST45is executed.

As for the statements ST46, ST47and ST48illustrated inFIG. 9A, and the statement ST55illustrated inFIG. 9B, the equivalence relations between representations of variables are calculated similarly to the case of the statement ST45(see sets of equality expressions E46, E47and E48illustrated inFIG. 10A, and the set of equality expressions E55illustrated inFIG. 10B).

When the equivalence relations between representations of variables are calculated with respect to the statement ST56illustrated inFIG. 9B, the equality expression ((a1_i, a2) in this example) including a variable (“a1_i” in this example) on the right side of the statement ST56is already included in the set of equality expressions E55. Therefore, a variable (“a0_i1” in this example) on the left side of the statement ST56is added to the equality expression (see a set of equality expressions E56illustrated inFIG. 10B).

As for the statement ST57illustrated inFIG. 9B, the equivalence relations between representations of variables are calculated similarly to the case of the statement ST56(see a set of equality expressions E57illustrated inFIG. 10B).

Also, as for the statement ST58illustrated inFIG. 9B, the equality expression with respect to the statement ST58is added to the set of equality expressions E57similarly to the case of the statement ST45(see a set of equality expressions E58illustrated inFIG. 10B).

The specification unit140then judges whether or not all true dependence can be removed based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133in the step S4(step S5).

As described above, in the example illustrated inFIGS. 9A and 9B, there is true dependence caused by the variables a0_i, a1_i and a2_i.

According to the set of equality expressions E48illustrated inFIG. 10A, the true dependence-causing variable “a2_i” is equivalent to a variable “a[i+3]”. The variable “a[i+3]” is neither the dependence-causing variable specified in the step S2nor the variable introduced to remove the name dependence in the step S3. Accordingly, the representation of the variable “a2_i” can be replaced with the representation of the variable “a[i+3]”.

Also, according to the set of equality expressions E48, the true dependence-causing variables “a0_i” and “a1_i” are respectively equivalent to the variables “a1” and “a2”. The variables “a1” and “a2”, however, are the dependence-causing variables specified in the step S2, and thus the representations of the true dependence-causing variables “a0_i” and “a1_i” cannot be replaced with the representations of these variables.

The specification unit140therefore judges that all true dependence cannot be removed (step S5: NO).

The specification unit140sets the value of m to “2” (step S7inFIG. 6), and notifies the calculation unit130of the value of m (“2” in this example) to instruct the calculation unit130to perform processing because the value of m is smaller than the value obtained by subtracting the kmin (“0” in this example) from the kmax (“99” in this example) (step S8: YES).

The iteration expansion unit131expands the iteration with respect to i+m (“i+2” in this example), similarly to the processing in the step S1(step S9).

The name dependence removal unit132included in the calculation unit130removes the name dependence with respect to the iteration i+m−1 (“i+1” in this example) and the iteration i+m, similarly to the processing in the step S3(step S11).

The equivalence relation calculation unit133included in the calculation unit130calculates equivalence relations between representations of variables with respect to statements in the iteration i+m−1 and the iteration i+m from which the name dependence has been removed, similarly to the processing in the step S4(step S12).

FIG. 11Aillustrates the iteration i+2 from which the name dependence has been removed.FIG. 11Billustrates calculation results of equivalence relations between representations of variables with respect to statements in the iteration i+2 from which the name dependence has been removed.

Here, a set of equality expressions E65illustrated inFIG. 11Bis obtained by adding an equality expression “(b[i+2], a0_i1+a1_i1+a2_i1)” to the set of equality expressions E58illustrated inFIG. 10B, based on the statement ST65illustrated inFIG. 11A.

The specification unit140judges whether or not all true dependence can be removed based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133in the step S12, similarly to the processing in the step S5(step S13).

In the example illustrated inFIGS. 9B and 11A, there is true dependence caused by the variables a0_i1, a1_i1and a2_i1.

According to the set of equality expressions E58illustrated inFIG. 10B, the true dependence-causing variables “a2_i1” and “a1_i1” are respectively equivalent to variables “a[i+4]” and “a[i+3]”. The variables “a[i+4]” and “a[i+3]” are neither the dependence-causing variables specified in the steps S2and S10nor the variables introduced to remove the name dependence in the steps S3and S7.

Accordingly, the representations of the variables “a2_i1” and “a1_i1” can be respectively replaced with the representations of the variables “a[i+4]” and “a[i+3]”.

Also, according to the set of equality expressions E58, the true dependence-causing variable “a0_i1” is equivalent to the variables “a1_i” and “a2”. The variables “a1_i” and “a2”, however, are respectively the variable introduced to remove the name dependence in the step S3and the dependence-causing variable specified in the step S2. Accordingly, the representation of the true dependence-causing variable “a0_i1” cannot be replaced with the representations of these variables. The specification unit140therefore judges that all true dependence cannot be removed (step S13: NO).

In this example, the specification unit140increments the value of m by one to “3” (step S14), and notifies the calculation unit130of the value of m to instruct the calculation unit130to perform processing because the value of m is smaller than the value obtained by subtracting the kmin (“0” in this example) from the kmax (“99” in this example) (step S8: YES). The calculation unit130having been instructed to perform processing performs the processing in the steps S9, S10, S11and S12, similarly to the above.

FIG. 12Aillustrates the iteration i+3 from which the name dependence has been removed.FIG. 12Billustrates calculation results of equivalence relations between representations of variables with respect to statements in the iteration i+3 from which the name dependence has been removed.

In the example illustrated inFIGS. 11A and 12A, there is true dependence caused by the variables a0_i2, a1_i2and a2_i2.

According to the set of equality expressions E68illustrated inFIG. 11B, the true dependence-causing variables “a2_i2”, “a1_i2” and “a0_i2” are respectively equivalent to variables “a[i+5]”, “a[i+4]” and “a[i+3]”. The variables “a[i+5]”, “a[i+4]” and “a[i+3]” are neither the dependence-causing variables specified in the steps S2and S10nor the variables introduced to remove the name dependence in the steps S3and S7.

Accordingly, the representations of the variables “a2_i2”, “a1_i2” and “a0_i2” can be respectively replaced with the representations of the variables “a[i+5]”, “a[i+4]” and “a[i+3]”.

The specification unit140therefore judges that all true dependence can be removed (step S13: YES). The generation unit150generates the candidate modified iteration based on the iteration i+m (“i+3” in this example) from which all true dependence has been removed (step S15).

FIG. 13Aillustrates the iteration i+3 from which all true dependence has been removed.

In the example illustrated inFIG. 13A, the generation unit150generates the candidate modified iteration by setting the value “i+3” to “k” and respectively replacing variables “a0_i3”, “a1_i3” and “a2_i3” with variables “a0_k”, “a1_k” and “a2_k”.

FIG. 13Billustrates the candidate modified iteration generated by the generation unit150.

The candidate modified iteration is applicable to iterations kmin+m (“3” in this example) to kmax (“99” in this example). That is to say, when at least 3≦k<kmax is satisfied, the block B1of the loop R1illustrated inFIG. 2Acan be replaced with an equivalent block having no dependence between iterations.

The specification unit140then notifies the calculation unit130of the values of kmin (“0” in this example) and m−1 (“2” in this example) to instruct the calculation unit130to perform processing. The iteration expansion unit131included in the calculation unit130having been instructed to perform processing expands the iterations with respect to kmin to m−1, similarly to the processing in the step S1(step S16inFIG. 7).

Also, the name dependence removal unit132specifies the dependence between statements in the iterations kmin to m−1, similarly to the processing in the step S2(step S17inFIG. 7), and removes the name dependence, similarly to the processing in the step S3(step S18).

The equivalence relation calculation unit133calculates equivalence relations between representations of variables with respect to statements in the iterations kmin to m−1 from which the name dependence has been removed, similarly to the processing in the step S4(step S19).

FIG. 15illustrates calculation results of equivalence relations between representations of variables with respect to the statements ST1, ST2and ST3illustrated inFIG. 14B, and statements in the iterations0and1also illustrated inFIG. 14Bfrom which the name dependence has been removed.

FIG. 16illustrates calculation results of equivalence relations between representations of variables with respect to statements in the iteration2illustrated inFIG. 14Bfrom which the name dependence has been removed.

The specification unit140then judges whether or not all true dependence can be removed based on the equivalence relations between representations of variables calculated by the equivalence relation calculation unit133in the step S19, similarly to the processing in the step S5(step S20).

According to the set of equality expressions E3illustrated inFIG. 15, the true dependence-causing variables “a0”, “a1” and “a2” are respectively equivalent to variables “a[0]”, “a[1]” and “a[2]”. The variables “a[0]”, “a[1]” and “a[2]” are neither the dependence-causing variables specified in the step S17nor the variables introduced to remove the name dependence in the step S18.

Accordingly, the representations of the variables “a0”, “a1” and “a2” in the statement ST15illustrated inFIG. 14Bcan be respectively replaced with the representations of the variables “a[0]”, “a[1]” and “a[2]”.

Similarly, the representation of the variable “a1” in the statement ST16illustrated inFIG. 14Bcan be replaced with the representation of the variable “a[1]”, based on the set of equality expressions E15illustrated inFIG. 15. Also, the representation of the variable “a2” in the statement ST17illustrated inFIG. 14Bcan be replaced with the representation of the variable “a[2]”, based on the set of equality expressions E16illustrated inFIG. 15.

Similarly, the representations of the variables “a0_0”, “a1_0” and “a2_0” in the statements ST25, ST26and ST27illustrated inFIG. 14Bcan be replaced, based on the sets of equality expressions E18, E25and E26illustrated inFIG. 15. Also, the representations of the variables “a0_1”, “a1_1” and “a2_1” in the statements ST35, ST36and ST37can be replaced, based on the set of equality expressions E28illustrated inFIG. 15and the sets of equality expressions E35and E36illustrated inFIG. 16.

The specification unit140therefore judges that all true dependence can be removed (step S20: YES), and further judges whether or not the iterations kmin (“0” in this example) to m−1 (“2” in this example) from which all true dependence has been removed are the same as the iterations kmin to m−1 applied to the candidate modified iteration generated in the step S15(step S21).

Iterations I11, I21and I31illustrated inFIG. 17Aare respectively iterations obtained by removing the true dependence from the iterations0,1and2(I10, I20and I30) illustrated inFIG. 14Bfrom which the name dependence has been removed.

The iterations0,1and2applied to the candidate modified iteration illustrated inFIG. 13Bare respectively the same as the iterations I11, I21and I31illustrated inFIG. 17A. In this example, the specification unit140therefore judges that they are the same (step S21: YES). The generation unit150generates the assembler program12by optimizing and parallelizing a program that is obtained by replacing the block B1of the loop R1included in the source program11with the candidate modified iteration (step S22).

FIG. 17Billustrates a partial program P2obtained by replacing the block B1of the partial program P1illustrated inFIG. 2Awith the candidate modified iteration illustrated inFIG. 13B.

In the partial program P2, the variables “a0”, “a1” and “a2” respectively defined in the statements ST1, ST2and ST3, and the variables “a0_k”, “a1_k” and “a2_k” respectively defined in the statements ST92, ST93and ST94are not referenced by the statements in the partial program P2. Therefore, on the condition that these variables are not referenced by a part other than the partial program P2of the source program11, it is possible to generate an optimized partial program P3(seeFIG. 18) by removing the statements ST1, ST2and ST3, a statement ST4that declares the variables “a0”, “a1” and “a2”, and the statements ST92, ST93and ST94.

The generation unit150also generates a partial program P4(seeFIG. 2B) by parallelizing the partial program P3. The generation unit150also stores, in the storage device10, the assembler program12generated based on a source program including the partial program P4, and the program generation apparatus100terminates the program generation processing.

Note that an instruction for the parallelization in the partial program P4illustrated inFIG. 2Bis written according to a writing format of OpenMP.

Although having been described based on the above embodiment, the program generation apparatus pertaining to the present invention may be modified as shown below, and it is obvious that the present invention is not limited to the program generation apparatus described in the above embodiment.

(1) The program generation apparatus100pertaining to the embodiment is described by taking, as an example, a case where the assembler program12is generated from the source program11including the loop and having the true dependence between iterations having consecutive iteration numbers. The assembler program12, however, may be generated from the source program11including a loop (e.g. a loop R5illustrated inFIG. 19Aand a loop R7illustrated inFIG. 19C) and having the true dependence between iterations having inconsecutive iteration numbers.FIG. 19Billustrates a loop R6that is equivalent to the loop R5and is included in the source program11having no true dependence.FIG. 19Dillustrates a loop R8that is equivalent to the loop R7and is included in the source program11having no true dependence.

To this end, when there is no true dependence as a result of the specification of the dependence in the step S2inFIG. 5, processing to specify two iterations between which there is the true dependence is performed.

That is to say, the iteration is expanded with respect to s (i+2≦s<N) to specify the dependence between statements in the iteration i and the iteration s. When there is no true dependence, the value of s is incremented by one and the above-mentioned iteration expansion and specification of the dependence are repeated. When there is the true dependence, the processing in the steps S3and S4is performed by replacing the iteration i+1 in the steps S3and S4with the iteration s.

In addition, the value of m in the step S6is changed so as to be set to “s”, and the value of m in the step S7inFIG. 6is changed so as to be set to “s+1”. The processing in the step S8onward is performed in a similar manner to the manner described in the embodiment.

As described above, the program generation apparatus pertaining to the present modification can generates, by referencing a source program including the loop such as the loop R5illustrated inFIG. 19Aand the loop R7illustrated inFIG. 19C, an assembler program similar to the assembler program that a conventional compiler can generate by referencing a source program including the loop such as the loop R6illustrated inFIG. 19Band the loop R8illustrated inFIG. 19D.

(2) The program generation apparatus100pertaining to the embodiment terminates the program generation processing without generating the assembler program12when the iterations kmin to m−1 from which all true dependence has been removed in the step S21inFIG. 7are not the same as the iterations kmin to m−1 applied to the candidate modified iteration generated in the step S15inFIG. 6(step S21: NO). The program generation apparatus100, however, may divide the loop into a partial loop X in which the loop control variable k is kmin to m−1 and a partial loop Y in which the loop control variable k is m to kmax to generate the assembler program12configured to be executed by a plurality of processors to execute the partial loop Y in parallel.

(3) The program generation apparatus100pertaining to the embodiment generates the assembler program12by referencing the source program11. The program generation apparatus, however, may be modified to include the assembler210and the linker220, and the program generation apparatus pertaining to the present modification may generate the object program14by referencing the source program11.

The linker220pertaining to the embodiment links a necessary library and the like with the relocatable binary program13in which a location of an address and the like of unresolved data are determined. The linker220, however, may naturally link a plurality of relocatable binary programs13with one another.

(4) The equivalence relation calculation unit133in the calculation unit130included in the program generation apparatus100pertaining to the embodiment calculates the equivalence relations between representations of variables using a method similar to the method disclosed in Patent Literature 2. This is just one example of the calculation of the equivalence relations between representations of variables, and the equivalence relations between representations of variables may be calculated using another method.

For example, the equivalence relations between representations of variables may be calculated using a method of repeatedly replacing representations of statements by utilizing the relation that the same value is stored in values x and y in a statement “x=y”, i.e., x and y are equivalent (hereinafter, the method is referred to as “copy propagation”).

The method is briefly discussed below.

For example, by performing the copy propagation with respect to the statement ST44“a2=a[i+3]” in the iteration i illustrated inFIG. 8A, the representations of the statements ST51and ST53in the iteration i+1 illustrated inFIG. 8Bare respectively replaced with representations of the statements “b[i+1]=a0+a1+a[i+3]” and “a1=a[i+3]”.

Furthermore, by performing the copy propagation with respect to the statement ST53after the replacement and the statement ST54, a representation of a statement ST61in the iteration i+2 illustrated inFIG. 20Ais replaced with a representation “b[i+2]=a0+a[i+3]+a[i+4]”. Also, representations of statements ST62and ST63are respectively replaced with representations “a0=a[i+3]” and “a1=a[i+4]”.

Furthermore, by performing the copy propagation with respect to the statements ST62and ST63after the replacement and a statement ST64, representations of statements ST71, ST72and ST73in the iteration i+3 illustrated inFIG. 20Bare respectively replaced with representations “b[i+3]=a[i+3]+a[i+4]+a[i+5]”, “a0=a[i+4]” and “a1=a[i+5]” (seeFIG. 20C).

(5) A program for causing a processor to perform the program generation processing described in the embodiment (seeFIGS. 5,6and7) may be recorded on a recording medium or distributed via various communication channels. Examples of the recording medium are an IC card, an optical disc, a flexible disk, a ROM and a flash memory. The distributed program is stored in a memory and the like capable of being read by the processor included in an apparatus and is provided for use. By the processor executing the program, various functions of the program generation apparatus described in the embodiment are achieved.

(6) Part or all of the above modifications (1) to (5) may be combined and applied to the program generation apparatus100in the embodiment.

(7) The following describes a configuration and modifications of the program generation apparatus pertaining to one embodiment of the present invention, along with their effects.

(a) A program generation apparatus pertaining to one embodiment of the present invention is a program generation apparatus for generating a program by referencing a source program including a loop for executing a block composed of one or more statements N times (N≧2), the source program having such dependence that a variable defined in a statement in the block pertaining to ithexecution (1≦i<N) is referenced by a statement in the block pertaining to jthexecution (i<j≦N), the program generation apparatus comprising: a calculation unit configured to calculate equivalence relations between representations of variables included in the block pertaining to the ithexecution and the block pertaining to any other execution than the ithexecution; a specification unit configured to specify, with respect to each of representations of any target variable causing the dependence among the variables, a representation of a variable not causing the dependence that is equivalent to the representation of the target variable among the variables, based on the equivalence relations calculated by the calculation unit; and a generation unit configured to generate a program so that the generated program is for executing the block M times (M≦N) and includes a statement including the representation of the variable specified by the specification unit.

According to the program generation apparatus pertaining to one embodiment of the present invention having the above configuration, by referencing the source program including the loop and having so-called true dependence between the statement in the block pertaining to the ithexecution and the statement in the block pertaining to the jthexecution, it is possible to generate the program being for executing the block M times and including the statement that includes, in place of each of the representations of the target variable causing the true dependence, the representation of the variable not causing the true dependence that is equivalent to the representation of the target variable.

The generated program can be independently executed in parallel by a plurality of processors to execute processing corresponding to processing of executing the block M times, and thus the predetermined processing to be realized by the loop is executed at high speed.

Accordingly, the program generation apparatus is useful in generating, by referencing the source program including the loop and having the true dependence, the program to be executed by a plurality of processors to execute the predetermined processing to be realized by the loop at high speed.

(b) Also, the representation of the variable specified by the specification unit may be different from any of the representations of the target variable.

According to the program generation apparatus having the above configuration, by referencing the source program including the loop and having the true dependence, it is possible to generate the program being for executing the block M times and including the statement that includes the representation of the variable not causing the true dependence that is equivalent to the representation of the target variable.

That is to say, the program generation apparatus generates, by referencing the source program including the loop and having the true dependence, the program to be independently executed in parallel by a plurality of processors to execute the processing corresponding to the processing of executing the block M times at high speed.

(c) Also, the block pertaining to the any other execution than the ithexecution may be the block pertaining to (i+1)thexecution, and until the specification unit specifies the representation of the variable not causing the dependence that is equivalent to the representation of the target variable, the calculation unit may repeatedly increment the value of i by one and calculate the equivalence relations.

According to the program generation apparatus having the above configuration, when the representation of the variable not causing the true dependence that is equivalent to the representation of the target variable causing the true dependence is specified in the case where the value of i is n (n<N), it is possible to generate the program being for executing the block N−n times at least from n to N and including the statement that includes the representation of the variable not causing the true dependence that is equivalent to the representation of the target variable causing the true dependence.

Accordingly, it becomes possible to execute the predetermined processing to be realized by the loop at high speed by a plurality of processors independently executing processing corresponding to processing of executing the block at least N−n times in parallel.

(d) Also, the source program may be a program to be executed by a single processor, and the program generated by the generation unit may be a program to be executed in parallel by a plurality of processors.

According to the program generation apparatus having the above configuration, by referencing the program to be executed by the single processor, it is possible to generate the program to be independently executed in parallel by the plurality of processors. Therefore, for example, when there has been a program that is created by a programmer and is to be executed by the single processor, it is unnecessary to regenerate the program to be executed in parallel by the plurality of processors. Accordingly, it is possible to save the trouble of creating the program.

(e) Also, when M<N is satisfied, the generation unit may modify the generated program so that the program after modification is for executing the block N−M times in addition to the M times, and judge whether processing of the program after the modification is equivalent to processing of the source program, and when judging affirmatively, the generation unit may replace the program before the modification with the program after the modification.

According to the program generation apparatus having the above configuration, on the condition that, even when the generated program for executing the block M times (M<N) is modified so as to be the program for executing the block N times, the processing of the program after the modification is equivalent to the processing of the source program, the program for executing the block N times is eventually generated.

The program for executing the block N times is the program including the statement that includes the representation of the variable not causing the true dependence that is equivalent to the representation of the target variable causing the true dependence. Accordingly, it becomes possible to execute the predetermined processing to be realized by the loop at high speed by the plurality of processors independently executing processing corresponding to processing of executing the block N times in parallel.

INDUSTRIAL APPLICABILITY

The program generation apparatus of the present invention is used to generate, by referencing the source program including the loop and having the so-called true dependence, a new program to be shared and executed in parallel by a plurality of processors to execute predetermined processing to be realized by the loop.

REFERENCE SIGNS LIST