A Loop Splitting Method of Irregular and Flow Dependence Loops
Sam-Jin Jeong · Indian Journal of Science and Technology · 2015
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 loopswith irregular and flowdependences 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 dependencedistance.Next,wewillproposehowtotile the iterationspace efficientlyaccordingtothe 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. Keywords: Flow Dependence, Irregular Dependence, Loop Transformation, Parallelizing Compiler