{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:13Z","timestamp":1750308793192,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,2,1]],"date-time":"2010-02-01T00:00:00Z","timestamp":1264982400000},"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. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2010,2]]},"abstract":"<jats:p>Hardware synthesis is the process by which system-level, Register Transfer (RT)-level, or behavioral descriptions can be turned into real implementations, in terms of logic gates. Scheduling is one of the most time-consuming steps in the overall design flow, and may become much more complex when performing hardware synthesis from high-level specifications. Exploiting a single scheduling strategy on very large designs is often reductive and potentially inadequate. Furthermore, finding the \u201cbest\u201d single candidate among all possible scheduling algorithms is practically infeasible. In this article we introduce a hybrid scheduling approach that is a preliminary step towards a comprehensive solution not yet provided by industrial or by academic solutions. Our method relies on an abstract symbolic representation of data flow nodes (operations) bound to control flow paths: it produces a more realistic lower bound during the prescheduling resource estimation step and speeds up slower but accurate heuristic scheduling techniques, thus achieving a globally improved result.<\/jats:p>","DOI":"10.1145\/1698759.1698762","type":"journal-article","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T19:20:32Z","timestamp":1267557632000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Speeding-up heuristic allocation, scheduling and binding with SAT-based abstraction\/refinement techniques"],"prefix":"10.1145","volume":"15","author":[{"given":"Gianpiero","family":"Cabodi","sequence":"first","affiliation":[{"name":"Politecnico di Torino, Turin, Italy"}]},{"given":"Luciano","family":"Lavagno","sequence":"additional","affiliation":[{"name":"Politecnico di Torino, Turin, Italy"}]},{"given":"Marco","family":"Murciano","sequence":"additional","affiliation":[{"name":"Politecnico di Torino, Turin, Italy"}]},{"given":"Alex","family":"Kondratyev","sequence":"additional","affiliation":[{"name":"Cadence Design Systems, Inc., San Jose, CA"}]},{"given":"Yosinori","family":"Watanabe","sequence":"additional","affiliation":[{"name":"Cadence Design Systems, Inc., San Jose, CA"}]}],"member":"320","published-online":{"date-parts":[[2010,3,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1177220"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/92.555989"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.309942"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1025"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/581199.581252"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.62794"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/123186.123335"},{"key":"e_1_2_1_8_1","article-title":"Computing lower bounds on functional units before scheduling","author":"Chaudhuri S.","year":"1994","journal-title":"IEEE Trans. VLSI Syst. 36--41."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/876638.876643"},{"key":"e_1_2_1_10_1","unstructured":"Cooper K. D. Schielke P. J. and Subramanian D. 1998. An experimental evaluation of list scheduling. Tech. rep. Deptartment of Computer Science Rice University.  Cooper K. D. Schielke P. J. and Subramanian D. 1998. An experimental evaluation of list scheduling. Tech. rep. Deptartment of Computer Science Rice University."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/321033.321034"},{"key":"e_1_2_1_13_1","unstructured":"De Micheli G. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill Higher Education.   De Micheli G. 1994. Synthesis and Optimization of Digital Circuits. McGraw-Hill Higher Education."},{"key":"e_1_2_1_14_1","first-page":"4","article-title":"Temporal induction by incremental SAT solving","volume":"89","author":"E\u00e9n N.","year":"2003","journal-title":"Electron. Not. Theor. Comput. Sci."},{"key":"e_1_2_1_15_1","unstructured":"E\u00e9n N. and S\u00f6rensson N. 2003b. The minisat SAT solver. http:\/\/www.cs.chalmers.se\/Cs\/Research\/FormalMethods\/MiniSat\/.  E\u00e9n N. and S\u00f6rensson N. 2003b. The minisat SAT solver. http:\/\/www.cs.chalmers.se\/Cs\/Research\/FormalMethods\/MiniSat\/."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/645674.663446"},{"key":"e_1_2_1_17_1","unstructured":"Garey M. R. and Johnson D. S. 1990. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York.   Garey M. R. and Johnson D. S. 1990. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman New York."},{"key":"e_1_2_1_18_1","unstructured":"Haynal S. P. 2000. Automata-Based symbolic scheduling. Ph.D. thesis.   Haynal S. P. 2000. Automata-Based symbolic scheduling. Ph.D. thesis."},{"volume-title":"Computer Architecture: A Quantitative Approach. Morgan Kaufmann.","year":"2002","author":"Hennessy J. L.","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-1066(93)90018-C"},{"volume-title":"Proceedings of the 9th Great Lakes Symposium on VLSI (GLS'99)","author":"Katkoori S.","key":"e_1_2_1_21_1"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/217474.217514"},{"volume-title":"Proceedings of the International Conference on Tools with Artificial Intelligence.","author":"Marques-Silva J. P.","key":"e_1_2_1_23_1"},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design: VLSI in Computers and Processors. IEEE Computer Society, 395--400","author":"Memik S. O.","key":"e_1_2_1_24_1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379017"},{"volume-title":"Proceedings of the IEEE Annual Symposium on VLSI, 187","author":"Namballa R.","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270350"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/37888.37918"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.82037"},{"volume-title":"Proceedings of the European Design Automation Conference. IEEE Computer Society Press, 283--288","author":"Safir A.","key":"e_1_2_1_30_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Selman B. Kautz H. and Cohen B. 1996. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 521--532.  Selman B. Kautz H. and Cohen B. 1996. Local search strategies for satisfiability testing. In DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 521--532.","DOI":"10.1090\/dimacs\/026\/25"},{"volume-title":"SIS: A system for sequential circuit synthesis. Tech. rep. UCB\/ERL M92\/41","year":"1992","author":"Sentovich E. M.","key":"e_1_2_1_32_1"},{"volume-title":"Proceedings of the 4th International Conference on Genetic Algorithms. 502--508","author":"Syswerda G.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/290833.290839"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02960762"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698759.1698762","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1698759.1698762","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:58Z","timestamp":1750278178000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698759.1698762"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":35,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1698759.1698762"],"URL":"https:\/\/doi.org\/10.1145\/1698759.1698762","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2010,2]]},"assertion":[{"value":"2009-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}