{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T14:36:50Z","timestamp":1775054210652,"version":"3.50.1"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Artif. Intell. Tools"],"published-print":{"date-parts":[[2008,2]]},"abstract":"<jats:p> Instruction scheduling is one of the most important steps for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block \u2014 a straight-line sequence of code with a single entry point and a single exit point \u2014 subject to precedence, latency, and resource constraints. Solving the problem exactly is NP-complete, and heuristic approaches are currently used in most compilers. In contrast, we present a scheduler that finds provably optimal schedules for basic blocks using techniques from constraint programming. In developing our optimal scheduler, the key to scaling up to large, real problems was in the development of preprocessing techniques for improving the constraint model. We experimentally evaluated our optimal scheduler on the SPEC 2000 integer and floating point benchmarks. On this benchmark suite, the optimal scheduler was very robust \u2014 all but a handful of the hundreds of thousands of basic blocks in our benchmark suite were solved optimally within a reasonable time limit \u2014 and scaled to the largest basic blocks, including basic blocks with up to 2600 instructions. This compares favorably to the best previous exact approaches. <\/jats:p>","DOI":"10.1142\/s0218213008003765","type":"journal-article","created":{"date-parts":[[2008,3,4]],"date-time":"2008-03-04T11:05:40Z","timestamp":1204628740000},"page":"37-54","source":"Crossref","is-referenced-by-count":16,"title":["OPTIMAL BASIC BLOCK INSTRUCTION SCHEDULING FOR MULTIPLE-ISSUE PROCESSORS USING CONSTRAINT PROGRAMMING"],"prefix":"10.1142","volume":"17","author":[{"given":"ABID M.","family":"MALIK","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada"}]},{"given":"JIM","family":"McINNES","sequence":"additional","affiliation":[{"name":"IBM Canada Toronto Lab, Toronto, Ontario, Canada"}]},{"given":"PETER","family":"VAN BEEK","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Waterloo, Waterloo, Ontario, Canada"}]}],"member":"219","published-online":{"date-parts":[[2011,11,21]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/2166.357217"},{"key":"rf2","unstructured":"R.\u00a0Govindarajan, The Compiler Design Handbook, eds. Y. N.\u00a0Srikant and P.\u00a0Shankar (CRC Press, 2003)\u00a0pp. 631\u2013687."},{"key":"rf3","volume-title":"Advanced Compiler Design and Implementation","author":"Muchnick S.","year":"1997"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1109\/71.372778"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-005-2862-8"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0096-0551(98)00002-2"},{"key":"rf8","first-page":"981","volume":"34","author":"Arya S.","journal-title":"IEEE Transactions on Computers C"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(97)00184-3"},{"key":"rf14","volume-title":"Handbook of Constraint Programming","author":"Smith B. M.","year":"2006"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-1479-4"},{"key":"rf18","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1613\/jair.834","volume":"14","author":"Debruyne R.","journal-title":"J. Artificial Intelligence Research"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1147\/rd.385.0577"}],"container-title":["International Journal on Artificial Intelligence Tools"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218213008003765","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T17:09:54Z","timestamp":1565197794000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218213008003765"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,2]]},"references-count":12,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,21]]},"published-print":{"date-parts":[[2008,2]]}},"alternative-id":["10.1142\/S0218213008003765"],"URL":"https:\/\/doi.org\/10.1142\/s0218213008003765","relation":{},"ISSN":["0218-2130","1793-6349"],"issn-type":[{"value":"0218-2130","type":"print"},{"value":"1793-6349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,2]]}}}