Abstract
We study the following optimization problem. The input is a number k and a directed graph with a specified “start” vertex, each of whose vertices may have one “memory bank requirement”, an integer. There are k “registers”, labeled 1 …k. A valid solution associates to the vertices with no bank requirement one or more “load instructions” L[b,j], for bank b and register j, such that every directed trail from the start vertex to some vertex with bank requirement c contains a vertex u that has been associated L[c,i] (for some register i ≤ k) and no vertex following u in the trail has been associated an L[b,i], for any bank b. The objective is to minimize the total number of associated load instructions. We give a k(k + 1)-approximation algorithm based on linear programming rounding, with (k + 1) being the best possible unless Vertex Cover has approximation 2 − ε for ε > 0. We also present a O(k logn) approximation, with n being the number of vertices in the input directed graph. Based on the same linear program, another rounding method outputs a valid solution with objective at most 2k times the optimum for k registers, using 2k registers.
Gruia Calinescu is supported in part by NSF grant NeTS-0916743 and Minming Li is supported in part by a grant from Research Grants Council of the Hong Kong Special Administrative Region, China [Project No. CityU117408].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Freescale, http://www.freescale.com .
Zilog, http://www.zilog.com .
Agarwal, A., Alon, N., Charikar, M.S.: Improved approximation for directed cut problems. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC 2007, pp. 671–680. ACM, New York (2007)
Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley Interscience, Hoboken (2000)
Bergner, P., Dahl, P., Engebretsen, D., O’Keefe, M.: Spill code minimization via interference region spilling. In: Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation, PLDI 1997, pp. 287–295. ACM, New York (1997)
Bernstein, D., Golumbic, M., Mansour, Y., Pinter, R., Goldin, D., Krawczyk, H., Nahshon, I.: Spill code minimization techniques for optimizing compliers. In: Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, PLDI 1989, pp. 258–263. ACM, New York (1989)
Briggs, P., Cooper, K.D., Torczon, L.: Coloring register pairs. ACM Lett. Program. Lang. Syst. 1, 3–13 (1992)
Charikar, M., Chekuri, C., Cheung, T.-Y., Dai, Z., Goel, A., Guha, S., Li, M.: Approximation Algorithms for Directed Steiner Problems. Journal of Algorithms 33(1), 73–91 (1999)
Cheriyan, J., Karloff, H.J., Rabani, Y.: Approximating directed multicuts. Combinatorica 25(3), 251–269 (2005)
Cooper, K., Dasgupta, A., Eckhardt, J.: Revisiting Graph Coloring Register Allocation: A Study of the Chaitin-Briggs and Callahan-Koblenz Algorithms. In: Ayguadé, E., Baumgartner, G., Ramanujam, J., Sadayappan, P. (eds.) LCPC 2005. LNCS, vol. 4339, pp. 1–16. Springer, Heidelberg (2006)
Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered PCP and the hardness of Hypergraph Vertex Cover. In: STOC 2003: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 595–601. ACM, New York (2003)
Falk, H.: Wcet-aware register allocation based on graph coloring. In: 46th ACM/IEEE, Design Automation Conference, DAC 2009, pp. 726–731 (2009)
Fu, C., Wilken, K.: A faster optimal register allocator. In: Proceedings of the 35th Annual ACM/IEEE International Symposium on Microarchitecture, MICRO, vol. 35, pp. 245–256. IEEE Computer Society Press, Los Alamitos (2002)
Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Proceedings of the 21st International Colloquium on Automata, Languages and Programming (1994)
Gupta, A.: Improved results for directed multicut. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2003, pp. 454–455. Society for Industrial and Applied Mathematics, Philadelphia (2003)
Jansen, K.: The allocation problem in hardware design. Discrete Applied Mathematics 43(1), 37–46 (1993)
Jansen, K., Reiter, J.: An approximation algorithm for the register allocation problem. Integration 25(2), 89–102 (1998)
Kannan, S., Proebsting, T.A.: Proebsting. Register allocation in structured programs. J. Algorithms 29(2), 223–237 (1998)
Koes, D., Goldstein, S.C.: A progressive register allocator for irregular architectures. In: Proceedings of the International Symposium on Code Generation and Optimization, CGO 2005, pp. 269–280. IEEE Computer Society, Washington, DC, USA (2005)
Koes, D.R., Goldstein, S.C.: A global progressive register allocator. In: Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2006, pp. 204–215. ACM, New York (2006)
Koes, D.R., Goldstein, S.C.: Register allocation deconstructed. In: Proceedings of the 12th International Workshop on Software and Compilers for Embedded Systems, SCOPES 2009, pp. 21–30. ACM, New York (2009)
Li, M., Xue, C.J., Liu, T., Zhao, Y.: Analysis and approximation for bank selection instruction minimization on partitioned memory architecture. In: Proceedings of the ACM SIGPLAN/SIGBED 2010 Conference on Languages, Compilers, and Tools for Embedded Systems (2010)
Pereira, F.M.Q., Palsberg, J.: Register allocation by puzzle solving. In: Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2008, pp. 216–226. ACM, New York (2008)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)
Smith, M.D., Ramsey, N., Holloway, G.: A generalized algorithm for graph-coloring register allocation. In: Proceedings of the ACM SIGPLAN 2004 Conference on Programming Language Design and Implementation, PLDI 2004, pp. 277–288. ACM, New York (2004)
Thorup, M.: All structured programs have small tree-width and good register allocation. Inf. Comput. 142(2), 159–181 (1998); Preliminary version in WG 1997
Zalamea, J., Llosa, J., Ayguad, E., Valero, M.: Modulo scheduling with integrated register spilling. In: Dietz, H. (ed.) LCPC 2001. LNCS, vol. 2624, pp. 115–130. Springer, Heidelberg (2003)
Zelikovsky, A.: A series of approximation algorithms for the acyclic directed Steiner tree problem. Algorithmica 18 (1997)
Zhou, Y.: Hardness of register loading. Personal Communication (2010)
Zosin, L., Khuller, S.: On directed Steiner trees. In: SODA, pp. 59–63 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Calinescu, G., Li, M. (2011). Register Loading via Linear Programming. In: Dehne, F., Iacono, J., Sack, JR. (eds) Algorithms and Data Structures. WADS 2011. Lecture Notes in Computer Science, vol 6844. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22300-6_15
Download citation
DOI: https://doi.org/10.1007/978-3-642-22300-6_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22299-3
Online ISBN: 978-3-642-22300-6
eBook Packages: Computer ScienceComputer Science (R0)