Delinearization: An Efficient Way to Break Multiloop Dependence Equations

Abstract

Exact and efficient data dependence testing is a key to success of loop-parallelizing compiler for computationally intensive programs. A number of algorithms has been created to test array references contained in parameter loops for dependence but most of them are unable to answer the following question correctly: Are references C(i1 + 10j1) and C(i2 + 5), 0 ≤ i1, i2 ≤ 4, 0 ≤ j1,j2 ≤ 9 independent? The technique introduced in this paper recognizes that i1, i2 and j1, j2 make different order contributions to the subscript index, and breaks dependence equation i1 + 10j1 = i2 + 10j2 + 5 into two equations i1 = i2 and 10j1 = 10j2 which then can be solved independently. Since resulting equations contain less variables it is less expensive to solve them. We call this technique delinearization because it is reverse of the linearization much discussed in the literature.