{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:23:11Z","timestamp":1774628591237,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,5,6]],"date-time":"2019-05-06T00:00:00Z","timestamp":1557100800000},"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. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2019,6,30]]},"abstract":"<jats:p>Loop pipelining is an essential technique in high-level synthesis to increase the throughput and resource utilisation of field-programmable gate array--based accelerators. It relies on modulo schedulers to compute an operator schedule that allows subsequent loop iterations to overlap partially when executed while still honouring all precedence and resource constraints. Modulo schedulers face a bi-criteria problem: minimise the initiation interval (II; i.e., the number of timesteps after which new iterations are started) and minimise the schedule length.<\/jats:p>\n          <jats:p>We present Moovac, a novel exact formulation that models all aspects (including the II minimisation) of the modulo scheduling problem as a single integer linear program, and discuss simple measures to prevent excessive runtimes, to challenge the old preconception that exact modulo scheduling is impractical.<\/jats:p>\n          <jats:p>We substantiate this claim by conducting an experimental study covering 188 loops from two established high-level synthesis benchmark suites, four different time limits, and three bounds for the schedule length, to compare our approach against a highly tuned exact formulation and a state-of-the-art heuristic algorithm. In the fastest configuration, an accumulated runtime of under 16 minutes is spent on scheduling all loops, and proven optimal IIs are found for 179 test instances.<\/jats:p>","DOI":"10.1145\/3317670","type":"journal-article","created":{"date-parts":[[2019,5,7]],"date-time":"2019-05-07T12:15:57Z","timestamp":1557231357000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Exact and Practical Modulo Scheduling for High-Level Synthesis"],"prefix":"10.1145","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8073-720X","authenticated-orcid":false,"given":"Julian","family":"Oppermann","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Darmstadt, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2231-7749","authenticated-orcid":false,"given":"Melanie","family":"Reuter-Oppermann","sequence":"additional","affiliation":[{"name":"Karlsruhe Institute of Technology, Karlsruhe, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1918-3911","authenticated-orcid":false,"given":"Lukas","family":"Sommer","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Darmstadt, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1164-3082","authenticated-orcid":false,"given":"Andreas","family":"Koch","sequence":"additional","affiliation":[{"name":"Technische Universit\u00e4t Darmstadt, Darmstadt, Germany"}]},{"given":"Oliver","family":"Sinnen","sequence":"additional","affiliation":[{"name":"University of Auckland, Auckland, New Zealand"}]}],"member":"320","published-online":{"date-parts":[[2019,5,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018742213548"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207128"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2013.09.006"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2014.6927490"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/514191.514208"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146909.1147025"},{"key":"e_1_2_1_8_1","first-page":"22","article-title":"Simplex Scheduling","volume":"1994","author":"de Dinechin Beno\u00eet Dupont","year":"1994","unstructured":"Beno\u00eet Dupont de Dinechin . 1994 . Simplex Scheduling : More Than Lifetime-Sensitive Instruction Scheduling. Technical Report PRISM 1994 . 22 . Beno\u00eet Dupont de Dinechin. 1994. Simplex Scheduling: More Than Lifetime-Sensitive Instruction Scheduling. Technical Report PRISM 1994.22.","journal-title":"More Than Lifetime-Sensitive Instruction Scheduling. Technical Report PRISM"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA\u201907)","author":"de Dinechin B. D.","year":"2007","unstructured":"B. D. de Dinechin . 2007 . Time-indexed formulations and a large neighborhood search for the resource-constrained modulo scheduling problem . In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA\u201907) . 144--151. B. D. de Dinechin. 2007. Time-indexed formulations and a large neighborhood search for the resource-constrained modulo scheduling problem. In Proceedings of the 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA\u201907). 144--151."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070100263"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/258915.258933"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/224538.224542"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591635.2591653"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\u201902)","author":"Fimmel Dirk","year":"2002","unstructured":"Dirk Fimmel and Jan M\u00fcller . 2002 . Optimal software pipelining with rational initiation interval . In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\u201902) . 638--643. Dirk Fimmel and Jan M\u00fcller. 2002. Optimal software pipelining with rational initiation interval. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA\u201902). 638--643."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.17.242"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155115"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ReCoSoC.2013.6581538"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.sorms.2012.12.001"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2015.22"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/53990.54022"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 2nd IEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201904)","author":"Lattner Chris","unstructured":"Chris Lattner and Vikram S. Adve . 2004. LLVM: A compilation framework for lifelong program analysis and transformation . In Proceedings of the 2nd IEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201904) . IEEE, Los Alamitos, CA, 75--88. Chris Lattner and Vikram S. Adve. 2004. LLVM: A compilation framework for lifelong program analysis and transformation. In Proceedings of the 2nd IEE\/ACM International Symposium on Code Generation and Optimization (CGO\u201904). IEEE, Los Alamitos, CA, 75--88."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.910814"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2968455.2968512"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF03356742"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 2014 IEEE International Symposium on Workload Characterication (IISWC\u201914)","author":"Reagen Brandon","unstructured":"Brandon Reagen , Robert Adolf , Yakun Sophia Shao , Gu-Yeon Wei , and David M. Brooks . 2014. MachSuite: Benchmarks for accelerator design and customized architectures . In Proceedings of the 2014 IEEE International Symposium on Workload Characterication (IISWC\u201914) . IEEE, Los Alamitos, CA, 110--119. Brandon Reagen, Robert Adolf, Yakun Sophia Shao, Gu-Yeon Wei, and David M. Brooks. 2014. MachSuite: Benchmarks for accelerator design and customized architectures. In Proceedings of the 2014 IEEE International Symposium on Workload Characterication (IISWC\u201914). IEEE, Los Alamitos, CA, 110--119."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-009-9239-4"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2308175"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2561828.2561872"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3317670","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3317670","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:02:27Z","timestamp":1750208547000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3317670"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,6]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3317670"],"URL":"https:\/\/doi.org\/10.1145\/3317670","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"value":"1936-7406","type":"print"},{"value":"1936-7414","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,6]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-05-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}