{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:35:20Z","timestamp":1761323720257,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T00:00:00Z","timestamp":1288569600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000151","name":"Division of Industrial Innovation and Partnerships","doi-asserted-by":"publisher","award":["IIP-0706352"],"award-info":[{"award-number":["IIP-0706352"]}],"id":[{"id":"10.13039\/100000151","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Reconfigurable Technol. Syst."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:p>High-performance reconfigurable computing involves acceleration of significant portions of an application using reconfigurable hardware. When the hardware tasks of an application cannot simultaneously fit in an FPGA, the task graph needs to be partitioned and scheduled into multiple FPGA configurations, in a way that minimizes the total execution time. This article proposes the Reduced Data Movement Scheduling (RDMS) algorithm that aims to improve the overall performance of hardware tasks by taking into account the reconfiguration time, data dependency between tasks, intertask communication as well as task resource utilization. The proposed algorithm uses the dynamic programming method. A mathematical analysis of the algorithm shows that the execution time would at most exceed the optimal solution by a factor of around 1.6, in the worst-case. Simulations on randomly generated task graphs indicate that RDMS algorithm can reduce interconfiguration communication time by 11% and 44% respectively, compared with two other approaches that consider data dependency and hardware resource utilization only. The practicality, as well as efficiency of the proposed algorithm over other approaches, is demonstrated by simulating a task graph from a real-life application - N-body simulation - along with constraints for bandwidth and FPGA parameters from existing high-performance reconfigurable computers. Experiments on SRC-6 are carried out to validate the approach.<\/jats:p>","DOI":"10.1145\/1862648.1862650","type":"journal-article","created":{"date-parts":[[2010,11,16]],"date-time":"2010-11-16T14:07:19Z","timestamp":1289916439000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Reconfiguration and Communication-Aware Task Scheduling for High-Performance Reconfigurable Computing"],"prefix":"10.1145","volume":"3","author":[{"given":"Miaoqing","family":"Huang","sequence":"first","affiliation":[{"name":"NSF Center for High-Performance Reconfigurable Computing (CHREC), The George Washington University"}]},{"given":"Vikram K.","family":"Narayana","sequence":"additional","affiliation":[{"name":"NSF Center for High-Performance Reconfigurable Computing (CHREC), The George Washington University"}]},{"given":"Harald","family":"Simmler","sequence":"additional","affiliation":[{"name":"NSF Center for High-Performance Reconfigurable Computing (CHREC), The George Washington University"}]},{"given":"Olivier","family":"Serres","sequence":"additional","affiliation":[{"name":"NSF Center for High-Performance Reconfigurable Computing (CHREC), The George Washington University"}]},{"given":"Tarek","family":"El-Ghazawi","sequence":"additional","affiliation":[{"name":"NSF Center for High-Performance Reconfigurable Computing (CHREC), The George Washington University"}]}],"member":"320","published-online":{"date-parts":[[2010,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.825678"},{"volume-title":"Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201901)","author":"Brebner G.","key":"e_1_2_1_2_1","unstructured":"Brebner , G. and Diessel , O . 2001. Chip-based reconfigurable task management . In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201901) . 182--191. Brebner, G. and Diessel, O. 2001. Chip-based reconfigurable task management. In Proceedings of the International Conference on Field Programmable Logic and Applications (FPL\u201901). 182--191."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00092-0"},{"key":"e_1_2_1_4_1","unstructured":"Coffman Jr. E. G. Garey M. R. and Johnson D. S. 1996. Approximation algorithms for bin packing: a survey. In Approximation Algorithms for NP-Hard Problems. D. Hochbaum Ed. PWS Publishing Boston. 46--93. Coffman Jr. E. G. Garey M. R. and Johnson D. S. 1996. Approximation algorithms for bin packing: a survey. In Approximation Algorithms for NP-Hard Problems . D. Hochbaum Ed. PWS Publishing Boston. 46--93."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2002.1043324"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1049\/ip-cdt:20000485"},{"volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201901)","author":"Fekete S. P.","key":"e_1_2_1_7_1","unstructured":"Fekete , S. P. , K\u00f6hler , E. , and Teich , J . 2001. Optimal FPGA module placement with temporal precedence constraints . In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201901) . 658--665. Fekete, S. P., K\u00f6hler, E., and Teich, J. 2001. Optimal FPGA module placement with temporal precedence constraints. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201901). 658--665."},{"volume-title":"Proceedings of the International Conference on Engineering Reconfigurable Systems and Algorithms (ERSA\u201905)","author":"Govindu G.","key":"e_1_2_1_8_1","unstructured":"Govindu , G. , Scrofano , R. , and Prasanna , V. K . 2005. A library of parameterizable floating-point cores for FPGAs and their application to scientific computing . In Proceedings of the International Conference on Engineering Reconfigurable Systems and Algorithms (ERSA\u201905) . 137--145. Govindu, G., Scrofano, R., and Prasanna, V. K. 2005. A library of parameterizable floating-point cores for FPGAs and their application to scientific computing. In Proceedings of the International Conference on Engineering Reconfigurable Systems and Algorithms (ERSA\u201905). 137--145."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201904)","volume":"1","author":"Handa M.","unstructured":"Handa , M. and Vemuri , R . 2004. A fast algorithm for finding maximal empty rectangles for dynamic FPGA placement . In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201904) . Vol. 1 . 744--745. Handa, M. and Vemuri, R. 2004. A fast algorithm for finding maximal empty rectangles for dynamic FPGA placement. In Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE\u201904). Vol. 1. 744--745."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FCCM.2006.54"},{"volume-title":"Proceedings of the 2nd International Workshop on High-Performance Reconfigurable Computing Technology and Applications (HPRCTA\u201908)","author":"Huang M.","key":"e_1_2_1_11_1","unstructured":"Huang , M. , Simmler , H. , Saha , P. , and El-Ghazawi , T . 2008. Hardware task scheduling optimizations for reconfigurable computing . In Proceedings of the 2nd International Workshop on High-Performance Reconfigurable Computing Technology and Applications (HPRCTA\u201908) . Huang, M., Simmler, H., Saha, P., and El-Ghazawi, T. 2008. Hardware task scheduling optimizations for reconfigurable computing. In Proceedings of the 2nd International Workshop on High-Performance Reconfigurable Computing Technology and Applications (HPRCTA\u201908)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161223"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems. Springer Berlin. Kellerer H. Pferschy U. and Pisinger D. 2004. Knapsack Problems . Springer Berlin.","DOI":"10.1007\/978-3-540-24777-7"},{"volume-title":"Algorithm Design. Pearson\/Addison-Wesley","author":"Kleinberg J.","key":"e_1_2_1_14_1","unstructured":"Kleinberg , J. and Tardos , \u00c9. 2005. Algorithm Design. Pearson\/Addison-Wesley , Boston, MA . Kleinberg, J. and Tardos, \u00c9. 2005. Algorithm Design. Pearson\/Addison-Wesley, Boston, MA."},{"volume-title":"Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201902)","author":"Lienhart G.","key":"e_1_2_1_15_1","unstructured":"Lienhart , G. , Kugel , A. , and M\u00e4nner , R . 2002. Using floating-point arithmetic on FPGAs to accelerate scientific N-body simulations . In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201902) . 182--191. Lienhart, G., Kugel, A., and M\u00e4nner, R. 2002. Using floating-point arithmetic on FPGAs to accelerate scientific N-body simulations. In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM\u201902). 182--191."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1086\/112164"},{"key":"e_1_2_1_17_1","first-page":"135","article-title":"A refined particle method for astrophysical problems","volume":"149","author":"Monaghan J. J.","year":"1985","unstructured":"Monaghan , J. J. and Lattanzio , J. C. 1985 . A refined particle method for astrophysical problems . Astron. Astrophys. 149 , 135 -- 143 . Monaghan, J. J. and Lattanzio, J. C. 1985. A refined particle method for astrophysical problems. Astron. Astrophys. 149, 135--143.","journal-title":"Astron. Astrophys."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1034"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2007.4380702"},{"volume-title":"Proceedings of the IEEE Aerospace Conference.","author":"Thakkar A. J.","key":"e_1_2_1_20_1","unstructured":"Thakkar , A. J. and Ejnioui , A . 2006. Design and implementation of double precision floating point division and square root on FPGAs . In Proceedings of the IEEE Aerospace Conference. Thakkar, A. J. and Ejnioui, A. 2006. Design and implementation of double precision floating point division and square root on FPGAs. In Proceedings of the IEEE Aerospace Conference."},{"volume-title":"Proceedings of the 2nd International Conference on Engineering of Reconfigurable Systems and Architectures (ERSA). 24--30","author":"Walder H.","key":"e_1_2_1_21_1","unstructured":"Walder , H. and Platzner , M . 2002. Non-preemptive multitasking on fpga: Task placement and footprint transform . In Proceedings of the 2nd International Conference on Engineering of Reconfigurable Systems and Architectures (ERSA). 24--30 . Walder, H. and Platzner, M. 2002. Non-preemptive multitasking on fpga: Task placement and footprint transform. In Proceedings of the 2nd International Conference on Engineering of Reconfigurable Systems and Architectures (ERSA). 24--30."},{"volume-title":"Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201903)","author":"Walder H.","key":"e_1_2_1_22_1","unstructured":"Walder , H. , Steiger , C. , and Platzner , M . 2003. Fast online task placement on FPGAs: free space partitioning and 2D-hashing . In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201903) . 178--185. Walder, H., Steiger, C., and Platzner, M. 2003. Fast online task placement on FPGAs: free space partitioning and 2D-hashing. In Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS\u201903). 178--185."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Symposium on Circuits and Systems (ISCAS\u201903)","volume":"5","author":"Wiangtong T.","unstructured":"Wiangtong , T. , Cheung , P. , and Luk , W . 2003. Multitasking in hardware-software codesign for reconfigurable computer . In Proceedings of the International Symposium on Circuits and Systems (ISCAS\u201903) . Vol. 5 . 621--624. Wiangtong, T., Cheung, P., and Luk, W. 2003. Multitasking in hardware-software codesign for reconfigurable computer. In Proceedings of the International Symposium on Circuits and Systems (ISCAS\u201903). Vol. 5. 621--624."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2007.1001"}],"container-title":["ACM Transactions on Reconfigurable Technology and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862648.1862650","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1862648.1862650","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:14:51Z","timestamp":1750281291000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862648.1862650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1145\/1862648.1862650"],"URL":"https:\/\/doi.org\/10.1145\/1862648.1862650","relation":{},"ISSN":["1936-7406","1936-7414"],"issn-type":[{"type":"print","value":"1936-7406"},{"type":"electronic","value":"1936-7414"}],"subject":[],"published":{"date-parts":[[2010,11]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}