A Loop Splitting Method of Irregular and Flow Dependence Loops

A 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 efficient method of splitting and transforming nested loops with irregular and flow dependences for maximizing parallelism. Our approach is based on the Convex Hull theory that has adequate information to handle irregular dependences, and also based on minimum dependence distance tiling methods. We will first show how to find the incrementing minimum dependence distance. Next, we will propose how to tile the iteration space efficiently according to the incrementing minimum dependence distance. Finally, we will show how to achieve more parallelism by loop interchanging and how to transform it into parallel loops. Comparison with some other methods shows more parallelism than other existing methods.