{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:26:28Z","timestamp":1758270388007,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","license":[{"start":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T00:00:00Z","timestamp":1506470400000},"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. Embed. Comput. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>In real-time embedded system design, one major goal is to construct a feasible schedule. Whether a feasible schedule exists depends on the Worst-Case Execution Time (WCET) of each task. Consequently, it is important to minimize the WCET of each task. We investigate the problem of instruction scheduling and register allocation for a program executed on a clustered Very Long Instruction Word (VLIW) processor such that the WCET of the program is minimized, and propose a novel, unified instruction scheduling and register allocation heuristic approach. Our heuristic approach is underpinned by a set of novel techniques, including spanning graph-based WCET-aware live range splitting, WCET-aware dynamic register pressure control, WCET-aware basic block prioritization for performing integrated instruction scheduling and register allocation, and WCET-aware spill code handling. We have implemented our approach in Trimaran 4.0, and compared it with the state-of-the-art approach by using a set of 20 benchmarks. The experimental results show that our approach achieves the maximum WCET improvement of 29.61% and the average WCET improvement of 10.23%, respectively.<\/jats:p>","DOI":"10.1145\/3126524","type":"journal-article","created":{"date-parts":[[2017,9,27]],"date-time":"2017-09-27T12:33:53Z","timestamp":1506515633000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["An Efficient WCET-Aware Instruction Scheduling and Register Allocation Approach for Clustered VLIW Processors"],"prefix":"10.1145","volume":"16","author":[{"given":"Xuesong","family":"Su","sequence":"first","affiliation":[{"name":"The University of New South Wales, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hui","family":"Wu","sequence":"additional","affiliation":[{"name":"The University of New South Wales, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingling","family":"Xue","sequence":"additional","affiliation":[{"name":"The University of New South Wales, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 1995 International Conference on Parallel Architectures and Compiler Techniques (PACT 95)","author":"Brasier Thomas S.","year":"1995","unstructured":"Thomas S. Brasier , Philip H. Sweany , Steven J. Beaty , and Steve Carr . 1995 . CRAIG: A practical framework for combining instruction scheduling and register assignment . In Proceedings of the 1995 International Conference on Parallel Architectures and Compiler Techniques (PACT 95) , Limassol, Cyprus. Thomas S. Brasier, Philip H. Sweany, Steven J. Beaty, and Steve Carr. 1995. CRAIG: A practical framework for combining instruction scheduling and register assignment. In Proceedings of the 1995 International Conference on Parallel Architectures and Compiler Techniques (PACT 95), Limassol, Cyprus."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/177492.177575"},{"key":"e_1_2_1_4_1","unstructured":"Inc CEVA. 2017. CEVA-X DSP Cores for Multimedia and Communications. Copyright. (2017). Retrieved from http:\/\/www.ceva-dsp.com\/product\/ceva-x2\/.  Inc CEVA. 2017. CEVA-X DSP Cores for Multimedia and Communications. Copyright. (2017). Retrieved from http:\/\/www.ceva-dsp.com\/product\/ceva-x2\/."},{"key":"e_1_2_1_5_1","first-page":"571","article-title":"Register allocation and spilling via graph coloring. (Feb. 18 1986)","volume":"4","author":"Chaitin Gregory J.","year":"1986","unstructured":"Gregory J. Chaitin . 1986 . Register allocation and spilling via graph coloring. (Feb. 18 1986) . US Patent 4 , 571 ,678. Gregory J. Chaitin. 1986. Register allocation and spilling via graph coloring. (Feb. 18 1986). US Patent 4,571,678.","journal-title":"US Patent"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0096-0551(81)90048-5"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11532378_4"},{"key":"e_1_2_1_8_1","unstructured":"Transmeta Corporation. 2001-2004. Transmeta Efficeon Processor. Copyright. (2001-2004). Retrieved from http:\/\/datasheets.chipdb.org\/Transmeta\/TM8600\/efficeon_tm8600_prod_brief.pdf.  Transmeta Corporation. 2001-2004. Transmeta Efficeon Processor. Copyright. (2001-2004). Retrieved from http:\/\/datasheets.chipdb.org\/Transmeta\/TM8600\/efficeon_tm8600_prod_brief.pdf."},{"key":"e_1_2_1_9_1","volume-title":"Bulldog: A compiler for VLIW architectures. Technical Report. Yale Univ.","author":"Ellis John Rolfe","year":"1985","unstructured":"John Rolfe Ellis . 1985 . Bulldog: A compiler for VLIW architectures. Technical Report. Yale Univ. , New Haven, CT ( USA) . John Rolfe Ellis. 1985. Bulldog: A compiler for VLIW architectures. Technical Report. Yale Univ., New Haven, CT (USA)."},{"volume-title":"Proceedings of the 11th International Workshop on Software 8 Compilers for Embedded Systems. ACM, 11--20","author":"Eriksson Mattias V.","key":"e_1_2_1_10_1","unstructured":"Mattias V. Eriksson , Oskar Skoog , and Christoph W. Kessler . 2008. Optimal vs. heuristic integrated code generation for clustered VLIW architectures . In Proceedings of the 11th International Workshop on Software 8 Compilers for Embedded Systems. ACM, 11--20 . Mattias V. Eriksson, Oskar Skoog, and Christoph W. Kessler. 2008. Optimal vs. heuristic integrated code generation for clustered VLIW architectures. In Proceedings of the 11th International Workshop on Software 8 Compilers for Embedded Systems. ACM, 11--20."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629911.1630100"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038698.2038722"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2011.10"},{"key":"e_1_2_1_14_1","first-page":"102","article-title":"Genetic algorithms in search, optimization, and machine learning","volume":"1989","author":"Golberg David E.","year":"1989","unstructured":"David E. Golberg . 1989 . Genetic algorithms in search, optimization, and machine learning . Addion Wesley 1989 (1989), 102 . David E. Golberg. 1989. Genetic algorithms in search, optimization, and machine learning. Addion Wesley 1989 (1989), 102.","journal-title":"Addion Wesley"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/55364.55407"},{"key":"e_1_2_1_16_1","volume-title":"OASIcs-OpenAccess Series in Informatics","volume":"15","author":"Gustafsson Jan","year":"2010","unstructured":"Jan Gustafsson , Adam Betts , Andreas Ermedahl , and Bj\u00f6rn Lisper . 2010 . The M\u00e4lardalen WCET benchmarks: Past, present and future . In OASIcs-OpenAccess Series in Informatics , Vol. 15 . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Jan Gustafsson, Adam Betts, Andreas Ermedahl, and Bj\u00f6rn Lisper. 2010. The M\u00e4lardalen WCET benchmarks: Past, present and future. In OASIcs-OpenAccess Series in Informatics, Vol. 15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/1128020.1128563"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TrustCom.2011.142"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2012.2236114"},{"key":"e_1_2_1_20_1","unstructured":"Texas Instruments incorporated. 1995-2016. TI TMS320C64x DSPs Architecture. Copyright. (1995-2016). Retrieved from http:\/\/www.ti.com.  Texas Instruments incorporated. 1995-2016. TI TMS320C64x DSPs Architecture. Copyright. (1995-2016). Retrieved from http:\/\/www.ti.com."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2845083"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/580550.876436"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2015.34"},{"key":"e_1_2_1_24_1","volume-title":"International Symposium On Leveraging Applications of Formal Methods, Verification and Validation. Springer, 482--485","author":"Lisper Bj\u00f6rn","year":"2014","unstructured":"Bj\u00f6rn Lisper . 2014 . SWEET--a tool for WCET flow analysis . In International Symposium On Leveraging Applications of Formal Methods, Verification and Validation. Springer, 482--485 . Bj\u00f6rn Lisper. 2014. SWEET--a tool for WCET flow analysis. In International Symposium On Leveraging Applications of Formal Methods, Verification and Validation. Springer, 482--485."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.v38:3"},{"key":"e_1_2_1_27_1","unstructured":"STMicroelectronics Group of Companies. 2000-2004. ST200 VLIW Series ST231 Core and Instruction Set Architecture Manual. Copyright. (2000-2004). Retrieved from http:\/\/lipforge.ens-lyon.fr\/docman\/view.php\/53\/26\/st231arch.pdf.  STMicroelectronics Group of Companies. 2000-2004. ST200 VLIW Series ST231 Core and Instruction Set Architecture Manual. Copyright. (2000-2004). Retrieved from http:\/\/lipforge.ens-lyon.fr\/docman\/view.php\/53\/26\/st231arch.pdf."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1011508.1011512"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/330249.330250"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499369.2465565"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTCSA.2016.46"},{"key":"e_1_2_1_32_1","unstructured":"Jeffrey D. Ullman. 1976. Complexity of sequencing problems. In Computer and Job-Shop Scheduling Theory.  Jeffrey D. Ullman. 1976. Complexity of sequencing problems. In Computer and Job-Shop Scheduling Theory."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.1.85"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TrustCom.2013.113"},{"key":"e_1_2_1_35_1","volume-title":"Automation and Test in Europe Conference and Exhibition (DATE)","author":"Zhang Xuemeng","year":"2014","unstructured":"Xuemeng Zhang , Hui Wu , Haiyan Sun , and Jingling Xue . 2014 . Lifetime holes aware register allocation for clustered VLIW processors. In Design , Automation and Test in Europe Conference and Exhibition (DATE) , 2014. IEEE, 1--4. Xuemeng Zhang, Hui Wu, Haiyan Sun, and Jingling Xue. 2014. Lifetime holes aware register allocation for clustered VLIW processors. In Design, Automation and Test in Europe Conference and Exhibition (DATE), 2014. IEEE, 1--4."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2038698.2038707"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10617-012-9103-0"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2994602"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3046683"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126524","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3126524","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:05:02Z","timestamp":1750273502000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3126524"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,27]]},"references-count":38,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3126524"],"URL":"https:\/\/doi.org\/10.1145\/3126524","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2017,9,27]]},"assertion":[{"value":"2017-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}