{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T17:12:58Z","timestamp":1771953178424,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T00:00:00Z","timestamp":1643587200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["1911235"],"award-info":[{"award-number":["1911235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            This paper describes a new approach to register-pressure-aware instruction scheduling, using\n            <jats:bold>Ant Colony Optimization (ACO)<\/jats:bold>\n            . ACO is a nature-inspired optimization technique that researchers have successfully applied to NP-hard sequencing problems like the\n            <jats:bold>Traveling Salesman Problem (TSP)<\/jats:bold>\n            and its derivatives. In this work, we describe an ACO algorithm for solving the long-standing compiler optimization problem of balancing\n            <jats:bold>Instruction-Level Parallelism (ILP)<\/jats:bold>\n            and\n            <jats:bold>Register Pressure (RP)<\/jats:bold>\n            in pre-allocation instruction scheduling. Three different cost functions are studied for estimating RP during instruction scheduling. The proposed ACO algorithm is implemented in the LLVM open-source compiler, and its performance is evaluated experimentally on three different machines with three different instruction-set architectures: Intel x86, ARM, and AMD GPU. The proposed ACO algorithm is compared to an exact\n            <jats:bold>Branch-and-Bound (B&amp;B)<\/jats:bold>\n            algorithm proposed in previous work. On x86 and ARM, both algorithms are evaluated relative to LLVM's generic scheduler, while on the AMD GPU, the algorithms are evaluated relative to AMD's production scheduler. The experimental results show that using SPECrate 2017 Floating Point, the proposed algorithm gives geometric-mean improvements of 1.13% and 1.25% in execution speed on x86 and ARM, respectively, relative to the LLVM scheduler. Using PlaidML on an AMD GPU, it gives a geometric-mean improvement of 7.14% in execution speed relative to the AMD scheduler. The proposed ACO algorithm gives approximately the same execution-time results as the B&amp;B algorithm, with each algorithm outperforming the other on a substantial number of hard scheduling regions. ACO gives better results than B&amp;B on many large instances that B&amp;B times out on. Both ACO and B&amp;B outperform the LLVM algorithm on the CPU and the AMD algorithm on the GPU.\n          <\/jats:p>","DOI":"10.1145\/3505558","type":"journal-article","created":{"date-parts":[[2022,1,31]],"date-time":"2022-01-31T13:43:02Z","timestamp":1643636582000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Register-Pressure-Aware Instruction Scheduling Using Ant Colony Optimization"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8727-671X","authenticated-orcid":false,"given":"Ghassan","family":"Shobaki","sequence":"first","affiliation":[{"name":"California State University, Sacramento, CA"}]},{"given":"Vahl Scott","family":"Gordon","sequence":"additional","affiliation":[{"name":"California State University, Sacramento, CA"}]},{"given":"Paul","family":"McHugh","sequence":"additional","affiliation":[{"name":"California State University, Sacramento, CA"}]},{"given":"Theodore","family":"Dubois","sequence":"additional","affiliation":[{"name":"California State University, Sacramento, CA"}]},{"given":"Austin","family":"Kerbow","sequence":"additional","affiliation":[{"name":"California State University, Sacramento, CA"}]}],"member":"320","published-online":{"date-parts":[[2022,1,31]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2007.52"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_2"},{"key":"e_1_3_3_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/1526330"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.4149\/cai_2018_1_165"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892219"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.585892"},{"key":"e_1_3_3_8_1","volume-title":"Optimization, Learning and Natural Algorithms (in Italian)Ph.D. thesis","author":"Dorigo M.","year":"1992","unstructured":"M. Dorigo. 1992. Optimization, Learning and Natural Algorithms (in Italian). Ph.D. thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, Italy (1992)."},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(88)90333-5"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2010.2048354"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/329055.329067"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/2700693.2700700"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55407"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1159750"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(01)00329-0"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-005-2862-8"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2006.16"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.2174\/092986608784567465"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830494"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1732003.1732079"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(98)00002-2"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/238997.239002"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/977395.977673"},{"key":"e_1_3_3_24_1","doi-asserted-by":"crossref","unstructured":"G. Leguizam\u00f3n and C. A. Coello Coello. 2010. Multi-objective ant colony optimization: A taxonomy and review of approaches. Integration of swarm intelligence and artificial neural network. 2011 67--94.","DOI":"10.1142\/9789814280150_0003"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCCC.2011.32"},{"key":"e_1_3_3_26_1","volume-title":"Constraint-based register allocation and instruction scheduling","author":"Lozano R. C.","year":"2018","unstructured":"R. C. Lozano. 2018. Constraint-based register allocation and instruction scheduling. Doctoral thesis, KTH Royal Institute of Technology, 2018."},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3332373"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3200920"},{"key":"e_1_3_3_29_1","unstructured":"V. Makarov. 2013. Mechanism for performing instruction scheduling based on register pressure sensitivity. U.S. Patent No. 8 549 508. 2013."},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/1571221"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2006.890229"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-019-03820-y"},{"key":"e_1_3_3_33_1","doi-asserted-by":"publisher","DOI":"10.3390\/info10010011"},{"key":"e_1_3_3_34_1","unstructured":"Perf (Performance analysis tool on Linux). https:\/\/en.wikipedia.org\/wiki\/Perf_(Linux)."},{"key":"e_1_3_3_35_1","unstructured":"PlaidML machine learning benchmarks. https:\/\/github.com\/plaidml\/plaidbench#intel-corporation-machine-learning-benchmarks."},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3200691.3178500"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321607.321620"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512432"},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2297"},{"key":"e_1_3_3_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3301489"},{"key":"e_1_3_3_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377918"},{"key":"e_1_3_3_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24306-1_10"},{"key":"e_1_3_3_43_1","unstructured":"SPEC CPU 2017. https:\/\/www.spec.org\/cpu2017\/."},{"key":"e_1_3_3_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-005-6466-x"},{"key":"e_1_3_3_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.885829"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505558","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3505558","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:24Z","timestamp":1750182564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3505558"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,31]]},"references-count":44,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3505558"],"URL":"https:\/\/doi.org\/10.1145\/3505558","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,31]]},"assertion":[{"value":"2021-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}