Patent ID: 7530069

Claim:
A program parallelizing apparatus for receiving a sequential processing program as input and producing a parallelized program for a multithreading parallel processor, comprising: a fork point determination section for analyzing the sequential processing program to determine a set of fork points in the program; a fork point combination determination section for determining an optimal combination of fork points included in the fork point set determined by the fork point determination section; and a parallelized program output section for creating a parallelized program for a multithreading parallel processor based on the optimal combination of fork points determined by the fork point combination determination section, wherein: in the case where a particular fork point appears n times when the sequential processing program is executed with particular input data, a dynamic boost value for the particular fork point is defined as the sum of C 1 , C 2 , . . . , and C n , where C 1 , C 2 , . . . , and C n , respectively represent the number of execution cycles from a fork source to a fork destination point of the particular fork point at each appearance, and an exclusive fork set of the particular fork point is defined as a set of fork points other than the particular fork point which are not available concurrently with the particular fork point when the sequential processing program is executed with particular input data; and the fork point combination determination section includes: a dynamic fork information acquisition section for obtaining the dynamic boost value and an exclusive fork set for each fork point when the sequential processing program is executed with particular input data; a storage for storing the dynamic boost value and the exclusive fork set for each fork point; a combination determination section for creating, by referring to the storage, a combination of fork points, which are not in an exclusive relationship according to the exclusive fork sets of the fork points, with a maximum sum of dynamic boost values; and a section for creating a weighted graph in which each fork point in the fork point set represents a node, an edge connects fork points in an exclusive relationship, and each node is weighted by the dynamic boost value of a fork point corresponding to the node.