Parallelization of Loops with Variable Distance Data

The extent of parallelization of a loop is largely determined by the dependences between its statements. While dependence free loops are fully parallelizable, those with loop carried de-pendences are not. Dependence distance is a measure of absolute difference between a pair of dependent iterations. Loops with constant distance data dependence(CD3), because of uniform distance between the dependent iter-ations, lead to easy partitioning of the itera-tion space and hence they have been success-fully dealt with. Parallelization of loops with variable distance data dependences(V D3) is a considerably diffi-cult problem. It is our belief that partitioning the iteration space in such loops cannot be done without examining solutions of the correspond-ing Linear Diophantine Equations(LDEs). Fo-cus of this work is to study V D3 and examine the relation between dependent iterations. Our analysis based on parametric solution leads to a mathematical formulation capturing depen-dence between iterations. Our approach shows the existence of reasonable exploitable paral-lelism in V D3 loops with multiple LDEs