{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:50:42Z","timestamp":1756385442454,"version":"3.41.0"},"reference-count":8,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,4,1]],"date-time":"2011-04-01T00:00:00Z","timestamp":1301616000000},"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. Program. Lang. Syst."],"published-print":{"date-parts":[[2011,4]]},"abstract":"<jats:p>Since its introduction by Joseph A. Fisher in 1979, trace scheduling has influenced much of the work on compile-time ILP (Instruction Level Parallelism) transformations. Initially developed for use in microcode compaction, it quickly became the main technique for machine-level compile-time parallelism exploitation. Although it has been used since the 1980s in many state-of-the-art compilers (e.g., Intel, Fujitsu, HP), a rigorous theory of trace scheduling is still lacking in the existing literature. This is reflected in the ad hoc way compensation code is inserted after a trace compaction, in the total absence of any attempts to measure the size of that compensation code, and so on.<\/jats:p>\n          <jats:p>\n            The aim of this article is to create a mathematical theory of the foundation of trace scheduling. We give a clear algorithm showing how to insert compensation code after a trace is replaced with its schedule, and then\n            <jats:italic>prove<\/jats:italic>\n            that the resulting program is indeed equivalent to the original program. We derive an upper bound on the size of that compensation code, and show that this bound can be actually attained. We also give a very simple proof that the trace scheduling algorithm always terminates.\n          <\/jats:p>","DOI":"10.1145\/1961204.1961206","type":"journal-article","created":{"date-parts":[[2011,5,3]],"date-time":"2011-05-03T12:48:53Z","timestamp":1304426933000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Mathematical foundation of trace scheduling"],"prefix":"10.1145","volume":"33","author":[{"given":"Utpal","family":"Banerjee","sequence":"first","affiliation":[{"name":"University of California, Irvine, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,5,4]]},"reference":[{"volume-title":"Dependence Analysis","author":"Banerjee U.","key":"e_1_2_1_1_1","unstructured":"Banerjee , U. 1997. Dependence Analysis . Kluwer Academic Publishers , Norwell, MA . Banerjee, U. 1997. Dependence Analysis. Kluwer Academic Publishers, Norwell, MA."},{"key":"e_1_2_1_2_1","unstructured":"Ellis J. R. 1985. Bulldog: A compiler for VLIW architecture. Ph.D. thesis Tech. rep. YALEU\/DCS\/RR364 Department of Computer Science Yale University.   Ellis J. R. 1985. Bulldog: A compiler for VLIW architecture. Ph.D. thesis Tech. rep. YALEU\/DCS\/RR364 Department of Computer Science Yale University."},{"volume-title":"The optimization of horizontal microcode within and beyond basic blocks: An Application of processor scheduling with resources. Tech. rep. COO-3077-161, Courant Mathematics and Computing Laboratory","author":"Fisher J. A.","key":"e_1_2_1_3_1","unstructured":"Fisher , J. A. 1979. The optimization of horizontal microcode within and beyond basic blocks: An Application of processor scheduling with resources. Tech. rep. COO-3077-161, Courant Mathematics and Computing Laboratory , New York University . Fisher, J. A. 1979. The optimization of horizontal microcode within and beyond basic blocks: An Application of processor scheduling with resources. Tech. rep. COO-3077-161, Courant Mathematics and Computing Laboratory, New York University."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675827"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205185"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/356819.356822"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205182"},{"volume-title":"Department of Computer Science","author":"Nicolau A.","key":"e_1_2_1_8_1","unstructured":"Nicolau , A. 1985. Parallelism , memory anti-aliasing and correctness for trace-scheduling compilers. Tech. rep. YALE\/DCS\/RR-374 , Department of Computer Science , Yale University . Nicolau, A. 1985. Parallelism, memory anti-aliasing and correctness for trace-scheduling compilers. Tech. rep. YALE\/DCS\/RR-374, Department of Computer Science, Yale University."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1961204.1961206","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1961204.1961206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:59:50Z","timestamp":1750244390000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1961204.1961206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,4]]},"references-count":8,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,4]]}},"alternative-id":["10.1145\/1961204.1961206"],"URL":"https:\/\/doi.org\/10.1145\/1961204.1961206","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2011,4]]},"assertion":[{"value":"2009-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}