{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:14Z","timestamp":1750220654402,"version":"3.41.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T00:00:00Z","timestamp":1609286400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>\n            <jats:italic>Test-pattern programs<\/jats:italic>\n            are for testing DRAM memory chips. They run on a special embedded system called\n            <jats:italic>automated test equipment<\/jats:italic>\n            (ATE). Each ATE manufacturer provides its own programming language, which is mostly low level, thus accessing the registers in the ATE directly. The register structure of each ATE is quite different and highly irregular. Since DRAM chipmakers are often equipped with diverse ATEs from different manufacturers, they employ automatic translation of a program developed for one ATE to a program for different ATEs. This raises an\n            <jats:italic>irregular register allocation<\/jats:italic>\n            problem during translation. This article proposes a solution based on partitioned Boolean quadratic programming (PBQP). PBQP has been used for a number of compiler optimizations, including\n            <jats:italic>paired register allocation<\/jats:italic>\n            , which our ATE register allocation also requires. Moreover, the\n            <jats:italic>interleaved<\/jats:italic>\n            processing in ATE incurs complex register constraints, which we could also formulate elegantly with PBQP. The original PBQP solver is not quite appropriate to use, though, since ATE register allocation does not allow spills, so we devised a more elaborate PBQP solver that trades off the allocation time and allocation search space, to find a solution in a reasonable amount of time. Our experimental results with product-level pattern programs show that the proposed register allocator successfully finds valid solutions in all cases, in the order of tenths of seconds.\n          <\/jats:p>","DOI":"10.1145\/3427378","type":"journal-article","created":{"date-parts":[[2020,12,30]],"date-time":"2020-12-30T12:30:51Z","timestamp":1609331451000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Irregular Register Allocation for Translation of Test-pattern Programs"],"prefix":"10.1145","volume":"18","author":[{"given":"Minsu","family":"Kim","sequence":"first","affiliation":[{"name":"Seoul National University, South Korea"}]},{"given":"Jeong-Keun","family":"Park","sequence":"additional","affiliation":[{"name":"Seoul National University, South Korea"}]},{"given":"Soo-Mook","family":"Moon","sequence":"additional","affiliation":[{"name":"Seoul National University, South Korea"}]}],"member":"320","published-online":{"date-parts":[[2020,12,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"R. Dean Adams. 2003. High Performance Memory Testing: Design Principles Fault Modeling and Self-Test (Frontiers in Electronic Tes  R. Dean Adams. 2003. High Performance Memory Testing: Design Principles Fault Modeling and Self-Test (Frontiers in Electronic Tes"},{"key":"e_1_2_1_2_1","volume-title":"Compilers: Principles","author":"Aho Alfred V.","year":"2003","unstructured":"Alfred V. Aho . 2003 . Compilers: Principles , Techniques and Tools (for Anna University) , 2\/e. Pearson Education India. Alfred V. Aho. 2003. Compilers: Principles, Techniques and Tools (for Anna University), 2\/e. Pearson Education India."},{"key":"e_1_2_1_3_1","volume-title":"Appel and Lal George","author":"Andrew","year":"2001","unstructured":"Andrew W. Appel and Lal George . 2001 . Optimal spilling for CISC machines with few registers. In ACM SIGPLAN Notices, Vol. 36 . ACM , 243--253. Andrew W. Appel and Lal George. 2001. Optimal spilling for CISC machines with few registers. In ACM SIGPLAN Notices, Vol. 36. ACM, 243--253."},{"key":"e_1_2_1_4_1","volume-title":"JEDEC Standard: DDR4 SDRAM: JESD79-4A","author":"JEDEC Solid State Technology Association","year":"2012","unstructured":"JEDEC Solid State Technology Association . 2012. JEDEC Standard: DDR4 SDRAM: JESD79-4A . September 2012 (2012). JEDEC Solid State Technology Association. 2012. JEDEC Standard: DDR4 SDRAM: JESD79-4A. September 2012 (2012)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/143103.143143"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/800230.806984"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3168806"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEST.2002.1041912"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_2_1_10_1","volume-title":"Shahid Asghar Ahmad, and Kumar Venkataramanan","author":"Das Dibyendu","year":"2019","unstructured":"Dibyendu Das , Shahid Asghar Ahmad, and Kumar Venkataramanan . 2019 . Deep learning-based hybrid graph-coloring algorithm for register allocation. arXiv:1912.03700. Retrieved from https:\/\/arxiv.org\/abs\/1912.03700. Dibyendu Das, Shahid Asghar Ahmad, and Kumar Venkataramanan. 2019. Deep learning-based hybrid graph-coloring algorithm for register allocation. arXiv:1912.03700. Retrieved from https:\/\/arxiv.org\/abs\/1912.03700."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892219"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2972206.2972211"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199608)26:8<929::AID-SPE40>3.3.CO;2-K"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11860990_21"},{"key":"e_1_2_1_15_1","unstructured":"Jiayi Huang Mostofa Patwary and Gregory Diamos. 2019. Coloring big graphs with alphagozero. arXiv:1902.10162. Retrieved from https:\/\/arxiv.org\/abs\/1902.10162.  Jiayi Huang Mostofa Patwary and Gregory Diamos. 2019. Coloring big graphs with alphagozero. arXiv:1902.10162. Retrieved from https:\/\/arxiv.org\/abs\/1902.10162."},{"volume-title":"IEEE Standard Test Interface Language (STIL) for Digital Test Vector Data\u2014Core Test Language","author":"IEEE Computer Society","key":"e_1_2_1_16_1","unstructured":"IEEE Computer Society . 2006. IEEE Standard Test Interface Language (STIL) for Digital Test Vector Data\u2014Core Test Language . Vol. 1999 . DOI:https:\/\/doi.org\/10.1109\/IEEESTD.1999.90563 IEEE Computer Society. 2006. IEEE Standard Test Interface Language (STIL) for Digital Test Vector Data\u2014Core Test Language. Vol. 1999. DOI:https:\/\/doi.org\/10.1109\/IEEESTD.1999.90563"},{"key":"e_1_2_1_17_1","unstructured":"Elias Khalil Hanjun Dai Yuyu Zhang Bistra Dilkina and Le Song. 2017. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems. 6348--6358.  Elias Khalil Hanjun Dai Yuyu Zhang Bistra Dilkina and Le Song. 2017. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems. 6348--6358."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3358186"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2005.4"},{"volume-title":"Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. IEEE, 297--307","author":"Kong Timothy","key":"e_1_2_1_20_1","unstructured":"Timothy Kong and Kent D. Wilken . 1998. Precise register allocation for irregular architectures . In Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. IEEE, 297--307 . Timothy Kong and Kent D. Wilken. 1998. Precise register allocation for irregular architectures. In Proceedings of the 31st Annual ACM\/IEEE International Symposium on Microarchitecture. IEEE, 297--307."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2019.00125"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEST.2015.7342393"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1002\/qre.4680080216","article-title":"Testing semiconductor memories: Theory and practice, A.J. van de Goor, Wiley, 1991. Number of pages: 512. Price: \u00a334.95","volume":"8","author":"O\u2019connor P. D. T.","year":"1992","unstructured":"P. D. T. O\u2019connor . 1992 . Testing semiconductor memories: Theory and practice, A.J. van de Goor, Wiley, 1991. Number of pages: 512. Price: \u00a334.95 . Qual. Reliabil. Eng. 8 , 2 (1992), 156 -- 157 . DOI:https:\/\/doi.org\/10.1002\/qre.4680080216 P. D. T. O\u2019connor. 1992. Testing semiconductor memories: Theory and practice, A.J. van de Goor, Wiley, 1991. Number of pages: 512. Price: \u00a334.95. Qual. Reliabil. Eng. 8, 2 (1992), 156--157. DOI:https:\/\/doi.org\/10.1002\/qre.4680080216","journal-title":"Qual. Reliabil. Eng."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ETS.2019.8791506"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1379022.1375609"},{"volume-title":"The test industry roadmap: Ask the experts! InProceedings of the 24th IEEE European Test Symposium (ETS\u201919)","author":"Rearick Jeff","key":"e_1_2_1_28_1","unstructured":"Jeff Rearick . 2019. The test industry roadmap: Ask the experts! InProceedings of the 24th IEEE European Test Symposium (ETS\u201919) . Jeff Rearick. 2019. The test industry roadmap: Ask the experts! InProceedings of the 24th IEEE European Test Symposium (ETS\u201919)."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/566225.513854"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3427378","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3427378","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:26Z","timestamp":1750197746000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3427378"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,30]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3427378"],"URL":"https:\/\/doi.org\/10.1145\/3427378","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2020,12,30]]},"assertion":[{"value":"2020-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}