## Heuristics for Solving Integer Linear Programs

**Introduction:** The data dependence problem requires many simple integer linear programs be solved. We now discuss several techniques to handle simple inequalities and a technique to take advantage of the similarity found in data dependence analysis.

**Independent - Variables Test: **Many of the integer linear programs from data dependence consist of inequalities that involve only one unknown. The programs can be solved simply by testing if there are integers between the constant upper bounds and constant lower bounds independently.

**Example**: Consider the nested loop

for (i = 0; i <= 10; i )

for (j = 0; j <= 10; j )

Z[i,j] = Z[j 10,i 9] ;

To find if there is a data dependence between Z[i, j] and Z[j 10, i 9], we ask i f there exist integers i , j , i', and j ' such that

0<t,j,«',j'<10

i=j' 10

j = i' 11

The GCD test, applied to the two equalities above, will determine that there may be an integer solution. The integer solutions to the equalities are expressed by

t = ti,j=t2,t,=t2-ll,j,=ti-10.

for any integers t\ and t2. Substituting the variables t\ and t2 into the linear inequalities, we get

o < h < 10

o < h < 10

o < t2

11 < io

o < h 10 < io

Thus, combining the lower bounds from the last two inequalities with the upper bounds from the first two, we deduce

10 < h < 10

11 < t2 < 10

Since the lower bound on t2 is greater than its upper bound, there is no integer solution, and hence no data dependence. This example shows that even if there are equalities involving several variables, the GCD test may still create linear inequalities that involve one variable at a time.

**Acyclic Test: **Another simple heuristic is to find if there exists a variable that is boundedbelow or above by a constant. In certain circumstances, we can safely replacethe variable by the constant; the simplified inequalities have a solution if andonly if the original inequalities have a solution. Specifically, suppose every lowerbound on vi is of the formCo < CiVi for some Ci > 0.while the upper bounds on vi are all of the form

C{Vi < C0 CiVi . . . d-iVi^i Ci 1Vi i . . . c n v n .

where ci, cx,... , c« are all nonnegative. Then we can replace variable Vi by its smallest possible integer value. If there is no such lower bound, we simply replace vi with — oo. Similarly, if every constraint involving V{ can be expressed in the two forms above, but with the directions of the inequalities reversed, then we can replace variable V{ with the largest possible integer value, or by oo if there is no constant upper bound. This step can be repeated to simplify the inequalities and in some cases determine if there is a solution.

**The Loop-Residue Test**: Let us now consider the case where every variable is bounded from below and above by other variables. It is commonly the case in data dependence analysis that constraints have the form V{ < Vj c, which can be solved using a simplified version of the loop-residue test due to Shostack. A set of these constraints can be represented by a directed graph whose nodes are labeled with variables. There is an edge from Vi to Vj labeled c whenever there is a constraint V{ < Vj c.

We define the weight of a path to be the sum of the labels of all the edges along the path. Each path in the graph represents a combination of the constraints in the system. That is, we can infer that v < v' c whenever there exists a path from v to v' with weight c. A cycle in the graph with weight c represents the constraint v < v c for each node v on the cycle. If we can find a negatively weighted cycle in the graph, then we can infer v < v, which is impossible. In this case, we can conclude that there is no solution and thus no dependence.

We can also incorporate into the loop-residue test constraints of the form c < v and v < c for variable v and constant c. We introduce into the system of inequalities a new dummy variable vo, which is added to each constant upper and lower bound. Of course, v0 must have value 0, but since the loop-residue test only looks for cycles, the actual values of the variables never becomes significant. To handle constant bounds, we replace

v < chy v <v§ c

c < v by vo < v — c.

**Memoization: **Often, similar data dependence problems are solved repeatedly, because simpleaccess patterns are repeated throughout the program. One important techniqueto speed up data dependence processing is to use memoization. Memoizationtabulates the results to the problems as they are generated. The table of storedsolutions is consulted as each problem is presented; the problem needs to besolved only if the result to the problem cannot be found in the table.