Compilers use heuristic algorithms to quickly produce inexact solutions for register assignment (assigning values to central processing unit [CPU] registers) and instruction scheduling (ordering instructions for execution).

The survey presented in this paper describes work on combinatoric algorithms that provide exact solutions for register assignment and instruction scheduling tasks. The survey lays out the general success of combinatoric algorithms, and identifies where the solution techniques have been (or could be) broadened and strengthened.

The algorithm descriptions concentrate on the models used to represent the tasks and the techniques used to discover solutions. The three main techniques described are integer programming, constraint programming, and partitioned binary quadratic programming. The solutions are evaluated with respect to analytic bounds (static evaluation) and comparative execution results (dynamic evaluation). The paper emphasizes the important point that solutions are exact with respect to the model, and follows up by detailing the various models’ representational power.

The paper is self-contained, although greater comfort with the assumptions and motivations underlying the algorithms requires some familiarity with the issues involved in generating code for modern processor systems. Similarly, familiarity with combinatoric methods, heuristics, and branch-and-bound search would be helpful. The writing is mostly smooth, although there are some monumentally long paragraphs that may test the attention and memory of even careful readers. The bibliography is generous in both background and current references.

Researchers in the field will be interested in what other areas of the field are doing. Theoreticians will be interested in the practical application of intractable algorithms, particularly with respect to the interplay between exact and heuristic approaches. Practitioners may find it difficult to be interested in exact solutions at the cost of so much execution time. Nevertheless, there is value in learning of such solution techniques.