The problem of optimal register coalescing is this: Given an interference graph of N nodes, each of degree less than K, and a set of additional weighted pairs of the form (I,J,W), where I and J are nodes and W is a weight find a K-coloring of the graph that minimizes the sum of the weights of pairs (I,J) such that color[I] != color[J].
Format of problem file is as follows. Every capital letter stands for an integer literal.
problem ::= N K edges edges ::=Where N >= 0, K > 0, and for each I,J, 0 <= I < N, 0 <= J < N, and each W >= 0.| interference-edge edges | coalesce-edge edges interference-edge ::= I J -1 coalesce-edge ::= I J W
For each node I such that I >= K, the degree of node I must be less than K. That is, the first K nodes may have arbitrarily high degree, but the rest must have low degree: for a given I, if I >= K, the number of interference edges of the form I Y -1 or X I -1 must be less than K. There may be arbitrarily many coalesce edges that mention I. (A K-coloring must trivially exist in a graph of max degree K-1.)
Format of solution file is as follows:
solution ::= N K colors colors ::=where the number of C values is N, and for each C, 0 <= C < K.| C colors
In both the problem file and the solution file, a comment starts with the % character and ends with a newline, and is ignored.
A solution is legal if for each interference (I,J,-1), color[I]!=color[J].
The cost of a solution is the sum of the weights W for all coalesce-edges (I,J,W) such that color[I]!=color[J].
The optimum solution is the minimum-cost legal solution.
This "check" program evaluates the cost of a solution.
Usage: check problem solution