{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:43:21Z","timestamp":1750308201642,"version":"3.41.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"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":[[2005,1]]},"abstract":"<jats:p>Complexities of applications implemented on embedded and programmable systems grow with the advances in capacities and capabilities of these systems. Mapping applications onto them manually is becoming a very tedious task. This draws attention to using high-level synthesis within design flows. Meanwhile, it is essential to provide a flexible formulation of optimization objectives as well as to perform efficient planning for various design objectives early on in the design flow. In this work, we address these issues in the context of data flow graph (DFG) scheduling, which is an essential element within the high-level synthesis flow. We present an algorithm that schedules a chain of operations with data dependencies among consecutive operations at a single step. This local problem is repeated to generate the schedule for the whole DFG. The local problem is formulated as a maximum weight noncrossing bipartite matching. We use a technique from the computational geometry domain to solve the matching problem. This technique provides a theoretical guarantee on the solution quality for scheduling a single chain of operations. Although still being local, this provides a relatively wider perspective on the global scheduling objectives. In our experiments we compared the latencies obtained using our algorithm with the optimal latencies given by the exact solution to the integer linear programming (ILP) formulation of the problem. In 9 out of 14 DFGs tested, our algorithm found the optimal solution, while generating latencies comparable to the optimal solution in the remaining five benchmarks. The formulation of the objective function in our algorithm provides flexibility to incorporate different optimization goals. We present examples of how to exploit the versatility of our algorithm with specific examples of objective functions and experimental results on the ability of our algorithm to capture these objectives efficiently in the final schedules.<\/jats:p>","DOI":"10.1145\/1044111.1044115","type":"journal-article","created":{"date-parts":[[2005,1,26]],"date-time":"2005-01-26T16:35:53Z","timestamp":1106757353000},"page":"33-57","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["A scheduling algorithm for optimization and early planning in high-level synthesis"],"prefix":"10.1145","volume":"10","author":[{"given":"Seda Ogrenci","family":"Memik","sequence":"first","affiliation":[{"name":"Northwestern University, Evanston, IL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryan","family":"Kastner","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Elaheh","family":"Bozorgzadeh","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Majid","family":"Sarrafzadeh","sequence":"additional","affiliation":[{"name":"University of California, Los Angeles, Los Angeles, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Actel. Visit the Web site http:\/\/varicore.actel.com.  Actel. Visit the Web site http:\/\/varicore.actel.com."},{"key":"e_1_2_1_2_1","unstructured":"Altera Corp. Visit the Web site http:\/\/www.altera.com\/products\/prd-index.html.  Altera Corp. Visit the Web site http:\/\/www.altera.com\/products\/prd-index.html."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01553888"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.62794"},{"key":"e_1_2_1_5_1","unstructured":"Chameleon Systems. Visit the Web site www.chameleonsystems.com.  Chameleon Systems. Visit the Web site www.chameleonsystems.com."},{"volume-title":"Proceedings of the Design Automation Conference. 10","author":"Cloutier R.","key":"e_1_2_1_6_1","unstructured":"Cloutier , R. and Thomas , D . 1990. The combination of scheduling, allocation and mapping in a single algorithm . Proceedings of the Design Automation Conference. 10 .1145\/123186.123230 Cloutier, R. and Thomas, D. 1990. The combination of scheduling, allocation and mapping in a single algorithm. Proceedings of the Design Automation Conference. 10.1145\/123186.123230"},{"key":"e_1_2_1_7_1","unstructured":"Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA.   Cormen T. H. Leiserson C. E. and Rivest R. L. 1990. Introduction to Algorithms. MIT Press Cambridge MA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1981.1675827"},{"volume-title":"Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines.","author":"Gokhale M. B.","key":"e_1_2_1_9_1","unstructured":"Gokhale , M. B. , Stone , J. M. , Arnold , J. , and Kalinowski , M . 2000. Stream-oriented FPGA computing in the streams-c high level language . In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines. Gokhale, M. B., Stone, J. M., Arnold, J., and Kalinowski, M. 2000. Stream-oriented FPGA computing in the streams-c high level language. In Proceedings of the IEEE Symposium on Field-Programmable Custom Computing Machines."},{"volume-title":"Proceedings of the International Conference on Computer Aided Design.","author":"Haldar M.","key":"e_1_2_1_10_1","unstructured":"Haldar , M. , Nayak , A. , Choudhary , A. , and Banerjee , P . 2001. A system for synthesizing optimized FPGA hardware from matlab . In Proceedings of the International Conference on Computer Aided Design. Haldar, M., Nayak, A., Choudhary, A., and Banerjee, P. 2001. A system for synthesizing optimized FPGA hardware from matlab. In Proceedings of the International Conference on Computer Aided Design."},{"volume-title":"Proceedings of the Conference on Parallel Architectures and Compilation Techniques.","author":"Hammes J.","key":"e_1_2_1_11_1","unstructured":"Hammes , J. , Rinker , R. , Bohm , W. , Najjar , W. , Draper , B. , and Beveridge , R . 1999. Cameron: High-level language compilation for reconfigurable systems . In Proceedings of the Conference on Parallel Architectures and Compilation Techniques. Hammes, J., Rinker, R., Bohm, W., Najjar, W., Draper, B., and Beveridge, R. 1999. Cameron: High-level language compilation for reconfigurable systems. In Proceedings of the Conference on Parallel Architectures and Compilation Techniques."},{"volume-title":"Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines.","author":"Hauck S.","key":"e_1_2_1_12_1","unstructured":"Hauck , S. , Fry , T. W. , Hosler , M. M. , and Kao , J. P . 1997. The Chimaera reconfigurable functional unit . In Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines. Hauck, S., Fry, T. W., Hosler, M. M., and Kao, J. P. 1997. The Chimaera reconfigurable functional unit. In Proceedings of the IEEE Symposium on FPGAs for Custom Computing Machines."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205185"},{"volume-title":"Proceedings of the International Conference on Computer-Aided Design.","author":"Kastner R.","key":"e_1_2_1_14_1","unstructured":"Kastner , R. , Memik , S. O. , Bozorgzadeh , E. , and Sarrafzadeh , M . 2001. Instruction generation for hybrid reconfigurable systems . In Proceedings of the International Conference on Computer-Aided Design. Kastner, R., Memik, S. O., Bozorgzadeh, E., and Sarrafzadeh, M. 2001. Instruction generation for hybrid reconfigurable systems. In Proceedings of the International Conference on Computer-Aided Design."},{"volume-title":"Proceedings of the European Design Automation Conference.","author":"Kramer H.","key":"e_1_2_1_15_1","unstructured":"Kramer , H. and Rosenstiel , W . 1990. System synthesis using behavioral descriptions . In Proceedings of the European Design Automation Conference. Kramer, H. and Rosenstiel, W. 1990. System synthesis using behavioral descriptions. In Proceedings of the European Design Automation Conference."},{"volume-title":"The Computer Science and Engineering Handbook, Chap. 6, Allen B","author":"Lee D. T.","key":"e_1_2_1_16_1","unstructured":"Lee , D. T. 1996. \" Computational geometry\". In The Computer Science and Engineering Handbook, Chap. 6, Allen B . Tucker, Ed. CRC Press, Boca Raton , FL. Lee, D. T. 1996. \"Computational geometry\". In The Computer Science and Engineering Handbook, Chap. 6, Allen B. Tucker, Ed. CRC Press, Boca Raton, FL."},{"volume-title":"Proceedings of the International Symposium on Microarchitecture.","author":"Lee C.","key":"e_1_2_1_17_1","unstructured":"Lee , C. , Potkonjak , M. , and Mangione-Smith , W. H . 1997. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems . In Proceedings of the International Symposium on Microarchitecture. Lee, C., Potkonjak, M., and Mangione-Smith, W. H. 1997. Mediabench: A tool for evaluating and synthesizing multimedia and communications systems. In Proceedings of the International Symposium on Microarchitecture."},{"key":"e_1_2_1_18_1","unstructured":"Lucent Technologies. Lucent technologies announces high-speed communications cores for customizing ORCA FPGAs.  Lucent Technologies. Lucent technologies announces high-speed communications cores for customizing ORCA FPGAs."},{"volume-title":"Proceedings of the International Symposium on Microarchitecture.","author":"Mahlke S. A.","key":"e_1_2_1_19_1","unstructured":"Mahlke , S. A. , Lin , D. C. , Chen , W. Y. , Hank , R. E. , and Bringmann , R. A . 1992. Effective compiler support for predicated execution using the hyperblock . In Proceedings of the International Symposium on Microarchitecture. Mahlke, S. A., Lin, D. C., Chen, W. Y., Hank, R. E., and Bringmann, R. A. 1992. Effective compiler support for predicated execution using the hyperblock. In Proceedings of the International Symposium on Microarchitecture."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Design Automation Conference.","author":"McFarland M. C.","year":"1986","unstructured":"McFarland , M. C. 1986 . Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions . In Proceedings of the Design Automation Conference. McFarland, M. C. 1986. Using bottom-up design techniques in the synthesis of digital hardware from abstract behavioral descriptions. In Proceedings of the Design Automation Conference."},{"volume-title":"Proceedings of the Design Automation Conference.","author":"McFarland M. C.","key":"e_1_2_1_21_1","unstructured":"McFarland , M. C. , Parker , A. C. , and Camposano , R . 1988. Tutorial on high-level synthesis . In Proceedings of the Design Automation Conference. McFarland, M. C., Parker, A. C., and Camposano, R. 1988. Tutorial on high-level synthesis. In Proceedings of the Design Automation Conference."},{"volume-title":"Proceedings of the Design Automation Conference. 10","author":"Monteiro J.","key":"e_1_2_1_22_1","unstructured":"Monteiro , J. , Devadas , S. , Ashar , P. , and Mauskar , A . 1996. Scheduling techniques to enable power management . In Proceedings of the Design Automation Conference. 10 .1145\/240518.240584 Monteiro, J., Devadas, S., Ashar, P., and Mauskar, A. 1996. Scheduling techniques to enable power management. In Proceedings of the Design Automation Conference. 10.1145\/240518.240584"},{"volume-title":"Proceedings of the International Symposium on System Synthesis. 10","author":"Musoll E.","key":"e_1_2_1_23_1","unstructured":"Musoll , E. and Cortadella , J . 1995. Scheduling and resource binding for low power . In Proceedings of the International Symposium on System Synthesis. 10 .1145\/224486.224523 Musoll, E. and Cortadella, J. 1995. Scheduling and resource binding for low power. In Proceedings of the International Symposium on System Synthesis. 10.1145\/224486.224523"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.1987.1270350"},{"volume-title":"Proceedings of the Design Automation Conference.","author":"Parker A. C.","key":"e_1_2_1_25_1","unstructured":"Parker , A. C. , Pizarro , J. , and Mlinar , M . 1986. Maha: A program for datapath synthesis . In Proceedings of the Design Automation Conference. Parker, A. C., Pizarro, J., and Mlinar, M. 1986. Maha: A program for datapath synthesis. In Proceedings of the Design Automation Conference."},{"volume-title":"Proceedings of the International Conference on Computer Design. 10","author":"Paulin P. G.","key":"e_1_2_1_26_1","unstructured":"Paulin , P. G. and Knight , J. P . 1987. Force directed scheduling in automatic data path synthesis . In Proceedings of the International Conference on Computer Design. 10 .1145\/37888.37918 Paulin, P. G. and Knight, J. P. 1987. Force directed scheduling in automatic data path synthesis. In Proceedings of the International Conference on Computer Design. 10.1145\/37888.37918"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.31522"},{"volume-title":"Proceedings of the Design Automation Conference. 10","author":"Potasman J.","key":"e_1_2_1_28_1","unstructured":"Potasman , J. , Lis , J. , Nicolau , A. , and Gajski , D . 1990. Percolation based synthesis . In Proceedings of the Design Automation Conference. 10 .1145\/123186.123333 Potasman, J., Lis, J., Nicolau, A., and Gajski, D. 1990. Percolation based synthesis. In Proceedings of the Design Automation Conference. 10.1145\/123186.123333"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1015341305426"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/82.847069"},{"volume-title":"Proceedings of the Conference on Programming Language Design and Implementation. 10","author":"So B.","key":"e_1_2_1_31_1","unstructured":"So , B. , Hall , M. , and Diniz , P . 2002. A compiler approach to fast design space exploration in fpga-based systems . In Proceedings of the Conference on Programming Language Design and Implementation. 10 .1145\/512529.512550 So, B., Hall, M., and Diniz, P. 2002. A compiler approach to fast design space exploration in fpga-based systems. In Proceedings of the Conference on Programming Language Design and Implementation. 10.1145\/512529.512550"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the International Symposium on Computer Aided Design. 10","author":"Srivastava A.","year":"2003","unstructured":"Srivastava , A. , Memik , S. O. , Choi , B. K. , and Sarrafzadeh , M . 2003. Achieving design closure through delay relaxation parameter . In Proceedings of the International Symposium on Computer Aided Design. 10 .1109\/ICCAD. 2003 .24 Srivastava, A., Memik, S. O., Choi, B. K., and Sarrafzadeh, M. 2003. Achieving design closure through delay relaxation parameter. In Proceedings of the International Symposium on Computer Aided Design. 10.1109\/ICCAD.2003.24"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Thomas D. E. Lagnese E. D. Walker R. A. Nestor J. A. Rajan J. V. and Blackburn R. L. 1990. Algorithmic and Register Transfer Level Synthesis: The System Architect's Workbench. Kluwer Academic Publishers Norwell MA.   Thomas D. E. Lagnese E. D. Walker R. A. Nestor J. A. Rajan J. V. and Blackburn R. L. 1990. Algorithmic and Register Transfer Level Synthesis: The System Architect's Workbench. Kluwer Academic Publishers Norwell MA.","DOI":"10.1007\/978-1-4613-1519-3"},{"volume-title":"Proceedings of the European Design and Test Conference.","author":"Timmer A. H.","key":"e_1_2_1_34_1","unstructured":"Timmer , A. H. and Jess , J. A. G. 1995. Exact scheduling strategies based on bipartite graph matching . In Proceedings of the European Design and Test Conference. Timmer, A. H. and Jess, J. A. G. 1995. Exact scheduling strategies based on bipartite graph matching. In Proceedings of the European Design and Test Conference."},{"volume-title":"Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines.","author":"Wazlowski M.","key":"e_1_2_1_35_1","unstructured":"Wazlowski , M. , Agarwal , L. , Lee , T. , Smith , A. , Lam , E. , Athanas , P. , Silverman , H. , and Gosh , S . 1993. Prism-ii compiler and architecture . In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines. Wazlowski, M., Agarwal, L., Lee, T., Smith, A., Lam, E., Athanas, P., Silverman, H., and Gosh, S. 1993. Prism-ii compiler and architecture. In Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines."},{"volume-title":"Proceedings of the Design Automation Conference. 10","author":"Wong J. L.","key":"e_1_2_1_36_1","unstructured":"Wong , J. L. , Megerian , S. , and Potkonjak , M . 2002. Forward-looking objective functions: Concepts and applications in high level synthesis . In Proceedings of the Design Automation Conference. 10 .1145\/513918.514141 Wong, J. L., Megerian, S., and Potkonjak, M. 2002. Forward-looking objective functions: Concepts and applications in high level synthesis. In Proceedings of the Design Automation Conference. 10.1145\/513918.514141"},{"key":"e_1_2_1_37_1","unstructured":"Xilinx Inc. Visit the Web site www.xilinx.com\/apps\/appsweb.htm.  Xilinx Inc. Visit the Web site www.xilinx.com\/apps\/appsweb.htm."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044115","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1044111.1044115","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:25:05Z","timestamp":1750263905000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044111.1044115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1044111.1044115"],"URL":"https:\/\/doi.org\/10.1145\/1044111.1044115","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}