Indian Journal of Science and Technology

Abstract

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