• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

Year: 2015, Volume: 8, Issue: 13, Pages: 1-6

Original Article

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 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


Subscribe now for latest articles and news.