A program parallelizing apparatus, a program parallelizing method and a
program parallelizing program capable of creating a parallelized program
of better parallel execution performance at a high speed. A fork point
determination section extracts all fork points in a sequential processing
program, and removes fork points with a static boost value satisfying a
static rounding condition. A fork point combination determination section
obtains a dynamic boost value and an exclusive fork set for each fork
point that appears when the sequential processing program is executed
with input data, and removes fork points with a dynamic boost value
satisfying a dynamic rounding condition. As a maximum weight independent
set problem, the fork point combination determination section obtains an
initial combination of fork points, which are not in an exclusive
relationship, with the maximum sum of dynamic boost values, and retrieves
an optimal combination based on an iterative improvement method.
According to the optimal fork point combination, a parallelized program
output section creates a parallelized program for a multithreading
parallel processor from the sequential processing program.