Compiler device, compiler program, and loop parallelization method

摘要

According to the conventional loop parallelization method, when a loop in which a value of a loop-carried dependency variable can be calculated in all of the iterations without sequentially executing the loop from the start, it is determined that DOALL parallelization is not applicable due to the loop-carried dependency variable. Accordingly, the loop is sequentially executed or parallelized by using DOACROSS parallelization that executes a loop including a loop-carried dependency variable. That is, there is a problem that an expression including a loop-carried dependency cannot be parallelized and efficiently processed with use of a multi-processor. By generating initial value calculating codes, the loop-carried dependency in a source code prior to parallelization can be solved, and by dividing a loop included in the source code into subloops that can be executed in parallel, the multi-processor can efficiently process the source code.

主权项

1. A loop parallelization method for generating an object program for parallel execution from a source program for sequential execution, the loop parallelization method comprising the steps of:
analyzing whether a loop included in the source program includes one or more loop-carried dependency variables, each loop-carried dependency variable being a variable whose value substituted thereto in one iteration of the loop is referred to in another iteration that is executed after the one iteration; determining whether the loop is a parallelizable loop without synchronization when the loop is analyzed to include the one or more loop-carried dependency variables, the parallelizable loop without synchronization being a loop including one or more loop-carried dependency variables whose values are calculable in all iterations of the loop regardless of whether the loop is sequentially executed; and determining, in order to divide the loop into a plurality of subloops, start positions of the plurality of subloops when the loop is determined as the parallelizable loop without synchronization, generating, for each start position, an initial value calculating code for executing one or more statements in the loop at least once to calculate values of the one or more loop-carried dependency variables at the corresponding start position, dividing the loop into the plurality of subloops based on the start positions, and generating the object program such that each initial value calculating code is executed prior to the corresponding subloop.