A Loop Splitting Method of Irregular and Flow Dependence Loops

AbstractA lot of work has been done in parallelizing nested loops with uniform dependences, from dependence analysis to loop transformation. Loops with non-uniform dependences are not so uncommon in the real world. This paper proposes an efficientmethodofsplittingandtransformingnestedloopswithirregularandflowdependencesformaximizingparallelism. Ourapproach isbasedontheConvexHull theorythathasadequate informationtohandle irregular dependences,and alsobasedonminimumdependencedistancetilingmethods.Wewillfirstshowhowtofindtheincrementingminimum dependencedistance.Next,wewillproposehowtotiletheiterationspaceefficientlyaccordingtotheincrementingminimum dependence distance. Finally, we will show how to achieve more parallelism by loop interchanging and how to transform it intoparallelloops.Comparisonwithsomeothermethodsshowsmoreparallelismthanotherexistingmethods