Patent ID: 8214818

Claim:
A method comprising: constructing a data dependency graph (DDG) for a loop to be transformed, the DDG representing each statement in the loop as a node and dependences between statements as edges with corresponding weights; performing statement shifting to transform the loop into a first transformed loop according to a first algorithm; determining whether the first transformed loop meets predetermined criteria, and performing statement shifting to transform the loop into a second transformed loop according to a second algorithm if the first transformed loop does not meet the predetermined criteria; performing a unimodular transformation and an echelon transformation of a selected one of the first or second transformed loops, and partitioning the selected transformed loop into a plurality of sub-loops to obtain maximum outer level parallelism (MOLP); and storing the plurality of sub-loops in a storage medium, wherein the predetermined criteria for the first algorithm include whether an inequalities group of a second unimodular matrix (U 2 ) multiplied by an integer matrix (C 2 ) and a second echelon matrix (B 2 ) has an integer solution.