Device and method for parallelizing compilation optimizing data transmission

An optimizing compiler method for converting a source program into an object program for use by a parallel computer, which optimizes a number of data transmissions between processing elements for a parallel computer made up of a plurality of processing elements, comprising the following steps:

• an intermediate code generation step for converting a source program into intermediate code;
• a loop retrieval step for retrieving loops from the intermediate code;
• a variable retrieval step for retrieving array variables on the left side and on the right side of the equation in each of the loops;
• a data dependency detection step for detecting whether there is data dependency which extends over iterations of the loop, based on the retrieved left side variable and right side variable;
• a left side variable retrieval step for retrieving information relating to array variables on a left side of an equation, being the array variables which should be distributed to every programming element for a program part coming before a loop, for a loop determined to have no data dependency;
• a data transmission count calculation step for calculating a number of data transmissions generated when parallelizing the loop, based on the information for each right side variable, for the loop determined to have no data dependency;
• a parallelization determination step for determining a loop to be parallelized as a loop with the lowest data transmission count;
• and
• a code generation step for generating the object code which parallelizes the determined loop.

An optimizing compiler apparatus for converting a source program into an object program for use by a parallel computer, which optimizes a number of data transmissions between processing elements for a parallel computer made up of a plurality of processing elements, comprising:

• loop retrieval means for retrieving loop processes from a program;
• data transmission calculation means for calculating a data transmission count generated when each of the loop processes is parallelized including:
• right side variable retrieval means for retrieving a variable on a right side of an equation in each of the loops retrieved by the loop retrieval means;
• variable information storage means for storing information relating to array variables which should be distributed among every processing element for a part of the program which comes before the loop from which the right side variable retrieval means has retrieved the right side variable, including information retrieval means for retrieving the information relating to a left side variable in the loop, for every loop determined to be parallelized by the parallelization determination means, and information storage means for storing the retrieved information, wherein the variable information storage means stores information which includes an array variable name, dimensions of an array, and distribution information which shows with regard to which subscript distribution to every processing element is performed;
• and
• calculation means for calculating a data transmission count based on the variable information for the retrieved right side variable when a variable name stored by the information storage means is the same as the right side variable retrieved by the right side variable retrieval means;
• parallelization determination means for determining a loop to be parallelized as a loop with a lowest data transmission count, out of all of the loops contained in each of the multiple loops;
• and
• code generation means for generating a parallelized object code for the determined loop.

An optimizing compiler apparatus for converting a source program into an object program for use by a parallel computer, which optimizes a number of data transmissions between processing elements for a parallel computer made up of a plurality of processing elements, comprising:

• multiple loop retrieval means for retrieving multiple loops of two or more overlapping loop processes in a program;
• data transmission count calculation means for calculating a data transmission count created when parallelizing a loop process for each of the loop processes contained in each of the retrieved multiple loops including:
• right side variable retrieval means for retrieving a variable on a right side of an equation in each of the multiple loops;
• variable information storage means for storing information relating to array variables which should be distributed among every processing element for a part of the program which comes before the multiple loop from which the right side variable retrieval means has retrieved the right side variable, including information retrieval means for retrieving the information relating to a left side variable in the loop, for every loop determined to be parallelized by the parallelization determination means, and information storage means for storing the retrieved information, wherein the variable information storage means stores information which includes an array variable name, dimensions of an array, and distribution information which shows with regard to which subscript distribution to every processing element is performed;
• and
• calculation means for calculating a data transmission count based on the variable information for the retrieved right side variable when a viable name stored by the information storage means is the same as the right side variable retrieved by the right side variable retrieval means;
• parallelization determination means for determining a loop to be parallelized having a lowest data transmission count out of the loops in each multiple loop;
• and
• code generation means for generating object code parallelizing the determined loop.