Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Survey on combinatorial register allocation and instruction scheduling
Lozano R., Schulte C. ACM Computing Surveys52 (3):1-50,2019.Type:Article
Date Reviewed: Jan 26 2021

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.

Reviewer:  R. Clayton Review #: CR147170 (2105-0121)
Bookmark and Share
  Reviewer Selected
 
 
Quadratic Programming Methods (G.1.6 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Quadratic Programming Methods": Date
A method of trust region type for minimizing noisy functions
Elster C., Neumaier A. Computing 58(1): 31-46, 1997. Type: Article
Jun 1 1998
Perturbation to enhance support vector machines for classification
To K., Lim C. Journal of Computational and Applied Mathematics 163(1): 233-239, 2004. Type: Article
May 19 2004
Minimizing quadratic functions subject to bound constraints with the rate of convergence and finite termination
Dostál Z., Schöberl J. Computational Optimization and Applications 30(1): 23-43, 2005. Type: Article
Aug 2 2005
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy