{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T12:11:49Z","timestamp":1789733509428,"version":"4.0.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["249013"],"award-info":[{"award-number":["249013"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>Compilers use software-controlled local memories to provide fast, predictable, and power-efficient access to critical data. We show that the local memory allocation for straight-line, or linearized programs is equivalent to a weighted interval-graph coloring problem. This problem is new when allowing a color interval to \u201cwrap around,\u201d and we call it the submarine-building problem. This graph-theoretical decision problem differs slightly from the classical ship-building problem, and exhibits very interesting and unusual complexity properties. We demonstrate that the submarine-building problem is NP-complete, while it is solvable in linear time for not-so-proper interval graphs, an extension of the the class of proper interval graphs. We propose a clustering heuristic to approximate any interval graph into a not-so-proper interval graph, decoupling spill code generation from local memory assignment. We apply this heuristic to a large number of randomly generated interval graphs reproducing the statistical features of standard local memory allocation benchmarks, comparing with state-of-the-art heuristics.<\/jats:p>","DOI":"10.1145\/2400682.2400693","type":"journal-article","created":{"date-parts":[[2013,1,22]],"date-time":"2013-01-22T15:28:56Z","timestamp":1358868536000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["A decoupled local memory allocator"],"prefix":"10.1145","volume":"9","author":[{"given":"Boubacar","family":"Diouf","sequence":"first","affiliation":[{"name":"INRIA, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Can","family":"Hanta\u015f","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Albert","family":"Cohen","sequence":"additional","affiliation":[{"name":"INRIA and \u00c9cole Normale Sup\u00e9rieure de Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"\u00d6zcan","family":"\u00d6zturk","sequence":"additional","affiliation":[{"name":"Bilkent University, Turkey"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jens","family":"Palsberg","sequence":"additional","affiliation":[{"name":"UCLA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,1,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378854"},{"key":"e_1_2_1_2_1","volume-title":"Document no. arm ddi 0084d","unstructured":"ARM. 1998. Document no. arm ddi 0084d , ARM Ltd . ARM7TDMI-S data sheet. ARM. 1998. Document no. arm ddi 0084d, ARM Ltd. ARM7TDMI-S data sheet."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/581888.581891"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1177\/109434208900300302"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2009.19"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bouchez F. Darte A. Guillon C. and Rastello F. 2006a. Register allocation: What does the np-completeness proof of Chaitin et al. really prove&quest; In Proceedings of the Annual Workshop on Duplicating Deconstructing and Debugging (WDDD'06).  Bouchez F. Darte A. Guillon C. and Rastello F. 2006a. Register allocation: What does the np-completeness proof of Chaitin et al. really prove&quest; In Proceedings of the Annual Workshop on Duplicating Deconstructing and Debugging (WDDD'06).","DOI":"10.1007\/978-3-540-72521-3_21"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC'06)","author":"Bouchez F.","unstructured":"Bouchez , F. , Darte , A. , Guillon , C. , and Rastello , F . 2006b. Register allocation: What does the np-completeness proof of Chaitin et al. really prove&quest; Or revisiting register allocation: Why and how . In Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC'06) . Lecture Notes in Computer Science. Springer. Bouchez, F., Darte, A., Guillon, C., and Rastello, F. 2006b. Register allocation: What does the np-completeness proof of Chaitin et al. really prove&quest; Or revisiting register allocation: Why and how. In Proceedings of the International Workshop on Languages and Compilers for Parallel Computing (LCPC'06). Lecture Notes in Computer Science. Springer."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2007.26"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1450095.1450119"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_13"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.870409"},{"key":"e_1_2_1_12_1","volume-title":"Western Network Processors Conference.","author":"Burns M.","unstructured":"Burns , M. , Prier , G. , Mirkovic , J. , and Reiher , P . 2003. Implementing address assurance in the intel ixp . Western Network Processors Conference. Burns, M., Prier, G., Mirkovic, J., and Reiher, P. 2003. Implementing address assurance in the intel ixp. Western Network Processors Conference."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90239-R"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13374-9_29"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289881.1289897"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/800229.806957"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Golumbic M. C. 2004. Algorithmic graph theory and perfect graphs. Ann. Discr. Math. 57.   Golumbic M. C. 2004. Algorithmic graph theory and perfect graphs. Ann. Discr. Math. 57.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"e_1_2_1_18_1","unstructured":"Hack S. Grund D. and Goos G. 2005. Towards register allocation for programs in ssa-form. Tech. rep. 2005-27 Universit\u00e4t Karlsruhe.  Hack S. Grund D. and Goos G. 2005. Towards register allocation for programs in ssa-form. Tech. rep. 2005-27 Universit\u00e4t Karlsruhe."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11688839_20"},{"key":"e_1_2_1_20_1","unstructured":"Instruments T. 1997. TMS370Cx7x 8-Bit Microcontroller. Texas Instruments.  Instruments T. 1997. TMS370Cx7x 8-Bit Microcontroller. Texas Instruments."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1230800.1230807"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1148882.1148891"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379049"},{"key":"e_1_2_1_24_1","unstructured":"Lee C. G. 1998. UTDSP benchmarks. http:\/\/www.eecg.toronto.edu\/~corinna\/DSP\/infrastructure\/UTDSP.html  Lee C. G. 1998. UTDSP benchmarks. http:\/\/www.eecg.toronto.edu\/~corinna\/DSP\/infrastructure\/UTDSP.html"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.05.025"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582710.1582711"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2005.27"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1880050.1880064"},{"key":"e_1_2_1_29_1","volume-title":"M-CORE: MMC2001 Reference Manual. Motorola Corporation.","author":"Motorola","year":"1998","unstructured":"Motorola . 1998 . M-CORE: MMC2001 Reference Manual. Motorola Corporation. Motorola. 1998. M-CORE: MMC2001 Reference Manual. Motorola Corporation."},{"key":"e_1_2_1_30_1","unstructured":"NVIDIA. 2008. NVIDIA unified architecture GeForce 8800 GT. http:\/\/www.nvidia.com\/page\/geforce8.html.  NVIDIA. 2008. NVIDIA unified architecture GeForce 8800 GT. http:\/\/www.nvidia.com\/page\/geforce8.html."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00722-4_12"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_21"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375609"},{"key":"e_1_2_1_34_1","unstructured":"Pouchet L. N. 2012. Polybench\/c the polyhedral benchmark suite. http:\/\/www.cse.ohio-state.edu\/~pouchet\/software\/polybench\/  Pouchet L. N. 2012. Polybench\/c the polyhedral benchmark suite. http:\/\/www.cse.ohio-state.edu\/~pouchet\/software\/polybench\/"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2007.01.015"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the ACM Symposium on Compiler Construction (CC'07)","volume":"4420","author":"Sarkar V.","unstructured":"Sarkar , V. and Barik , R . 2007. Extended linear scan: An alternate foundation for global register allocation . In Proceedings of the ACM Symposium on Compiler Construction (CC'07) . S. Krishamurthi and M. Odersky, Eds. Lecture Notes in Computer Science , vol. 4420 . Springer, 141--155. Sarkar, V. and Barik, R. 2007. Extended linear scan: An alternate foundation for global register allocation. In Proceedings of the ACM Symposium on Compiler Construction (CC'07). S. Krishamurthi and M. Odersky, Eds. Lecture Notes in Computer Science, vol. 4420. Springer, 141--155."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/502217.502221"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the Conference on Design, Automation and Test in Europe (DATE'02)","author":"Steinke S.","unstructured":"Steinke , S. , Wehmeyer , L. , Lee , B. , and Marwedel , P . 2002. Assigning program and data objects to scratchpad for energy reduction . In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'02) . IEEE Computer Society, Washington, DC, 409. Steinke, S., Wehmeyer, L., Lee, B., and Marwedel, P. 2002. Assigning program and data objects to scratchpad for energy reduction. In Proceedings of the Conference on Design, Automation and Test in Europe (DATE'02). IEEE Computer Society, Washington, DC, 409."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/951710.951747"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151074.1151085"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2400682.2400693","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2400682.2400693","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:35:01Z","timestamp":1750239301000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2400682.2400693"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,1]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["10.1145\/2400682.2400693"],"URL":"https:\/\/doi.org\/10.1145\/2400682.2400693","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,1]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}