{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:12Z","timestamp":1750308792746,"version":"3.41.0"},"reference-count":31,"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"}],"funder":[{"name":"National Key Technology R&D Program of China","award":["2006BAH02A01"],"award-info":[{"award-number":["2006BAH02A01"]}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["6.14E+11"],"award-info":[{"award-number":["6.14E+11"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["STPGP 364910-08FQRNT 2010-NC-131844"],"award-info":[{"award-number":["STPGP 364910-08FQRNT 2010-NC-131844"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Important Science & Technology Specific Projects","award":["2009ZX01038-0012009ZX01038-002"],"award-info":[{"award-number":["2009ZX01038-0012009ZX01038-002"]}]}],"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>FPGAs are widely used in today's embedded systems design due to their low cost, high performance, and reconfigurability. Partially RunTime-Reconfigurable (PRTR) FPGAs, such as Virtex-2 Pro and Virtex-4 from Xilinx, allow part of the FPGA area to be reconfigured while the remainder continues to operate without interruption, so that HW tasks can be placed and removed dynamically at runtime. We address two problems related to HW task scheduling on PRTR FPGAs: (1) HW\/SW partitioning. Given an application in the form of a task graph with known execution times on the HW (FPGA) and SW (CPU), and known area sizes on the FPGA, find an valid allocation of tasks to either HW or SW and a static schedule with the optimization objective of minimizing the total schedule length (makespan). (2) Pipelined scheduling. Given an input task graph, construct a pipelined schedule on a PRTR FPGA with the goal of maximizing system throughput while meeting a given end-to-end deadline. Both problems are NP-hard. Satisfiability Modulo Theories (SMT) is an extension to SAT by adding the ability to handle arithmetic and other decidable theories. We use the SMT solver Yices with Linear Integer Arithmetic (LIA) theory as the optimization engine for solving the two scheduling problems. In addition, we present an efficient heuristic algorithm based on kernel recognition for the pipelined scheduling problem, a technique borrowed from SW pipelining, to overcome the scalability problem of the SMT-based optimal solution technique.<\/jats:p>","DOI":"10.1145\/1698759.1698763","type":"journal-article","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T19:20:32Z","timestamp":1267557632000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Hardware\/software partitioning and pipelined scheduling on runtime reconfigurable FPGAs"],"prefix":"10.1145","volume":"15","author":[{"given":"Mingxuan","family":"Yuan","sequence":"first","affiliation":[{"name":"Zhejiang University, P. R. China and Hong Kong University of Science and Technology"}]},{"given":"Zonghua","family":"Gu","sequence":"additional","affiliation":[{"name":"Zhejiang University, P. R. China and Hong Kong University of Science and Technology"}]},{"given":"Xiuqiang","family":"He","sequence":"additional","affiliation":[{"name":"Zhejiang University, P. R. China and Hong Kong University of Science and Technology"}]},{"given":"Xue","family":"Liu","sequence":"additional","affiliation":[{"name":"Mcgill University, Quebec, Canada"}]},{"given":"Lei","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Pittsburgh, Pittsburgh, PA"}]}],"member":"320","published-online":{"date-parts":[[2010,3,2]]},"reference":[{"volume-title":"Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'06)","author":"Ahn M.","key":"e_1_2_1_1_1","unstructured":"Ahn , M. , Yoon , J. W. , Pae , K. Y. , Kim , Y. , Kiemb , M. , and Choi , K . 2006. A spatial mapping algorithm for heterogeneous coarse-grained reconfigurable architectures . In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'06) . G. G. E. Gielen Ed., European Design and Automation Association, 363--368. Ahn, M., Yoon, J. W., Pae, K. Y., Kim, Y., Kiemb, M., and Choi, K. 2006. A spatial mapping algorithm for heterogeneous coarse-grained reconfigurable architectures. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'06). G. G. E. Gielen Ed., European Design and Automation Association, 363--368."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.476167"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/212094.212131"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065579.1065667"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2006.886411"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-004-0170-9"},{"key":"e_1_2_1_7_1","unstructured":"Carpenter J. Funk S. Holman P. Srinivasan A. Anderson J. and Baruah S. 2004. A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms. Chapman and Hall\/CRC 30--1--30--19.  Carpenter J. Funk S. Holman P. Srinivasan A. Anderson J. and Baruah S. 2004. A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms. Chapman and Hall\/CRC 30--1--30--19."},{"volume-title":"Proceedings of the 14th Reconfigurable Architectures Workshop.","author":"Claus C.","key":"e_1_2_1_8_1","unstructured":"Claus , C. , Muller , F. H. , Zeppenfeld , J. , and Stechele , W . 2007. A new framework to accelerate virtex-ii pro dynamic partial self-reconfiguration . In Proceedings of the 14th Reconfigurable Architectures Workshop. Claus, C., Muller, F. H., Zeppenfeld, J., and Stechele, W. 2007. A new framework to accelerate virtex-ii pro dynamic partial self-reconfiguration. In Proceedings of the 14th Reconfigurable Architectures Workshop."},{"volume-title":"Proceedings of the IEEE International Symposium on Electronic Design, Test and Applications (DELTA'08)","author":"Cuoccio A.","key":"e_1_2_1_9_1","unstructured":"Cuoccio , A. , Grassi , P. R. , Rana , V. , Santambrogio , M. D. , and Sciuto , D . 2008. A generation flow for self-reconfiguration controllers customization . In Proceedings of the IEEE International Symposium on Electronic Design, Test and Applications (DELTA'08) . IEEE Computer Society, 279--284. Cuoccio, A., Grassi, P. R., Rana, V., Santambrogio, M. D., and Sciuto, D. 2008. A generation flow for self-reconfiguration controllers customization. In Proceedings of the IEEE International Symposium on Electronic Design, Test and Applications (DELTA'08). IEEE Computer Society, 279--284."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/368273.368557"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.micpro.2006.02.009"},{"volume-title":"Proceedings of the International Workshop on Hardware\/Software Codesign (CODES'98)","author":"Dick R. P.","key":"e_1_2_1_12_1","unstructured":"Dick , R. P. , Rhodes , D. L. , and Wolf , W . 1998. TGFF: Task graphs for free . In Proceedings of the International Workshop on Hardware\/Software Codesign (CODES'98) , G. Borriello, A. A. Jerraya, and L. Lavagno Eds., IEEE Computer Society, Los Alamitos, CA, 97--101. Dick, R. P., Rhodes, D. L., and Wolf, W. 1998. TGFF: Task graphs for free. In Proceedings of the International Workshop on Hardware\/Software Codesign (CODES'98), G. Borriello, A. A. Jerraya, and L. Lavagno Eds., IEEE Computer Society, Los Alamitos, CA, 97--101."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11817963_11"},{"volume-title":"Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'01)","author":"Fekete S. P.","key":"e_1_2_1_15_1","unstructured":"Fekete , S. P. , K\u00f6hler , E. , and Teich , J . 2001. Optimal FPGA module placement with temporal precedence constraints . In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'01) . 658--667. Fekete, S. P., K\u00f6hler, E., and Teich, J. 2001. Optimal FPGA module placement with temporal precedence constraints. In Proceedings of the Conference and Exhibition on Design, Automation and Test in Europe (DATE'01). 658--667."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.839324"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1084834.1084903"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Kirkpatrick S. Gelatt C. D. and Vecchi M. P. 1983. Optimization by simulated annealing. Science 220 4598 671--680.  Kirkpatrick S. Gelatt C. D. and Vecchi M. P. 1983. Optimization by simulated annealing. Science 220 4598 671--680.","DOI":"10.1126\/science.220.4598.671"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Klein M. Ralya T. Pollak B. Obenza R. and Harbour M. G. 1993. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Springer.   Klein M. Ralya T. Pollak B. Obenza R. and Harbour M. G. 1993. A Practitioner's Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Springer.","DOI":"10.1007\/978-1-4615-2796-1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375596"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/503048.503076"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1289881.1289903"},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'09)","author":"Liu M.","key":"e_1_2_1_23_1","unstructured":"Liu , M. , Kuehn , W. , Lu , Z. , and Jantsch , A . 2009. Run-Time partial reconfiguration speed investigation and architectural design space exploration . In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'09) . Liu, M., Kuehn, W., Lu, Z., and Jantsch, A. 2009. Run-Time partial reconfiguration speed investigation and architectural design space exploration. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'09)."},{"volume-title":"Proceedings of the IEEE International Conference on Computer Design (ICCD'02)","author":"Memik S. O.","key":"e_1_2_1_24_1","unstructured":"Memik , S. O. and Fallah , F . 2002. Accelerated SAT-based scheduling of control\/data flow graphs . In Proceedings of the IEEE International Conference on Computer Design (ICCD'02) . IEEE Computer Society, Los Alamitos, CA, 395. Memik, S. O. and Fallah, F. 2002. Accelerated SAT-based scheduling of control\/data flow graphs. In Proceedings of the IEEE International Conference on Computer Design (ICCD'02). IEEE Computer Society, Los Alamitos, CA, 395."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.379017"},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'05)","author":"Noguera J.","key":"e_1_2_1_26_1","unstructured":"Noguera , J. and Badia , R. M . 2005. Performance and energy analysis of task-level graph transformation techniques for dynamically reconfigurable architectures . In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'05) . T. Rissa, S. J. E. Wilton, and P. H. W. Leong Eds., IEEE Press, 563--567. Noguera, J. and Badia, R. M. 2005. Performance and energy analysis of task-level graph transformation techniques for dynamically reconfigurable architectures. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL'05). T. Rissa, S. J. E. Wilton, and P. H. W. Leong Eds., IEEE Press, 563--567."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2006.878343"},{"key":"e_1_2_1_28_1","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"Papadimitriou C. H.","year":"1998","unstructured":"Papadimitriou , C. H. and Steiglitz , K . 1998 . Combinatorial Optimization: Algorithms and Complexity . Dover Publications . Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover Publications."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2006.883909"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1176760.1176809"},{"volume-title":"Xilinx virtex-4 family overview. preliminary specification ds112. Tech. rep","author":"Xilinx","key":"e_1_2_1_31_1","unstructured":"Xilinx . 2005. Xilinx virtex-4 family overview. preliminary specification ds112. Tech. rep ., Xilinx Inc . Xilinx. 2005. Xilinx virtex-4 family overview. preliminary specification ds112. Tech. rep., Xilinx Inc."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS.2008.39"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1698759.1698763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1698759.1698763","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.1698763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,2]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,2]]}},"alternative-id":["10.1145\/1698759.1698763"],"URL":"https:\/\/doi.org\/10.1145\/1698759.1698763","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":"2008-11-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"}}]}}