{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:28:54Z","timestamp":1750220934879,"version":"3.41.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T00:00:00Z","timestamp":1551225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"College of Engineering and Computer Science (ECS) at California State University, Sacramento"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"<jats:p>Multiple combinatorial algorithms have been proposed for doing pre-allocation instruction scheduling with the objective of minimizing register pressure or balancing register pressure and instruction-level parallelism. The cost function that is minimized in most of these algorithms is the peak register pressure (or the peak excess register pressure). In this work, we explore an alternative register-pressure cost function, which is the Sum of Live Interval Lengths (SLIL). Unlike the peak cost function, which captures register pressure only at the highest pressure point in the schedule, the proposed SLIL cost function captures register pressure at all points in the schedule. Minimizing register pressure at all points is desirable in larger scheduling regions with multiple high-pressure points. This article describes a Branch-and-Bound (B8B) algorithm for minimizing the SLIL cost function. The algorithm is based on two SLIL-specific dynamic lower bounds as well as the history utilization technique proposed in our previous work. The proposed algorithm is implemented into the LLVM Compiler and evaluated experimentally relative to our previously proposed B8B algorithm for minimizing the peak excess register pressure. The experimental results show that the proposed algorithm for minimizing the SLIL cost function produces substantially less spilling than the previous algorithm that minimizes the peak cost function. Execution-time results on various processors show that the proposed B8B algorithm significantly improves the performance of many CPU2006 benchmarks by up to 49% relative to LLVM's default scheduler. The geometric-mean improvement for FP2006 on Intel Core i7 is 4.22%.<\/jats:p>","DOI":"10.1145\/3301489","type":"journal-article","created":{"date-parts":[[2019,2,27]],"date-time":"2019-02-27T15:00:28Z","timestamp":1551279628000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Exploring an Alternative Cost Function for Combinatorial Register-Pressure-Aware Instruction Scheduling"],"prefix":"10.1145","volume":"16","author":[{"given":"Ghassan","family":"Shobaki","sequence":"first","affiliation":[{"name":"California State University, Sacramento"}]},{"given":"Austin","family":"Kerbow","sequence":"additional","affiliation":[{"name":"California State University, Sacramento"}]},{"given":"Christopher","family":"Pulido","sequence":"additional","affiliation":[{"name":"California State University, Sacramento"}]},{"given":"William","family":"Dobson","sequence":"additional","affiliation":[{"name":"California State University, Sacramento"}]}],"member":"320","published-online":{"date-parts":[[2019,2,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37051-9_2"},{"volume-title":"Proceedings of the IFIP Working Conference on Architectures and Compilation Techniques for Fine and Medium Grain Parallelism. 243--254","author":"Berson D.","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","unstructured":"T. Cormen C. Leiserson R. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press.   T. Cormen C. Leiserson R. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2892208.2892219"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55407"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2003.1159750"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2006.16"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-005-2862-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(98)00002-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/238997.239002"},{"volume-title":"Proceedings of the 30th International Symposium on Microarchitecture.","author":"Lee C.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","unstructured":"R. C. Lozano M. Carlsson G. H. Blindell and C. Schulte. 2018. Combinatorial register allocation and instruction scheduling. https:\/\/arxiv.org\/abs\/1804.02452.  R. C. Lozano M. Carlsson G. H. Blindell and C. Schulte. 2018. Combinatorial register allocation and instruction scheduling. https:\/\/arxiv.org\/abs\/1804.02452."},{"issue":"8","key":"e_1_2_1_13_1","first-page":"549","article-title":"Mechanism for Performing Instruction Scheduling based on Register Pressure Sensitivity","author":"Makarov V.","year":"2013","journal-title":"U.S. Patent"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178487.3178500"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/321607.321620"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.2297"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9725-9"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512432"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2004.27"},{"volume-title":"CPU2006. 2006","year":"2006","author":"SPEC","key":"e_1_2_1_22_1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-005-6466-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1241601.1241621"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1331699.1331707"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301489","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3301489","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:53:25Z","timestamp":1750204405000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3301489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,27]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3301489"],"URL":"https:\/\/doi.org\/10.1145\/3301489","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"type":"print","value":"1544-3566"},{"type":"electronic","value":"1544-3973"}],"subject":[],"published":{"date-parts":[[2019,2,27]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}