{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:50:15Z","timestamp":1750308615320,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T00:00:00Z","timestamp":1497312000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"TEQIP Phase-II project of the University of Calcutta, India"},{"name":"TCS Research Fellowship Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2017,10,31]]},"abstract":"<jats:p>Reconfigurable devices that promise to offer the twin benefits of flexibility as in general-purpose processors along with the efficiency of dedicated hardwares often provide a lucrative solution for many of today\u2019s highly complex real-time embedded systems. However, online scheduling of dynamic hard real-time tasks on such systems with efficient resource utilization in terms of both space and time poses an enormously challenging problem. We attempt to solve this problem using a combined offline-online approach. The offline component generates and stores various optional feasible placement solutions for different sub-sets of tasks that may possibly be co-mapped together. Given a set of periodic preemptive real-time tasks that requires to be executed at runtime, the online scheduler first carries out an admission control procedure and then produces a schedule, which is guaranteed to meet all timing constraints provided it is spatially feasible to place designated subsets of these tasks at specified scheduling points within a future time interval. These feasibility checks are done and actual placement solutions are obtained through a low overhead search of the statically precomputed placement solutions. Based on this approach, we have proposed a periodic preemptive real-time scheduling methodology for runtime partially reconfigurable devices. Effectiveness of the proposed strategy has been verified through simulation based experiments and we observed that the strategy achieves high resource utilization with low task rejection rates over various simulation scenarios.<\/jats:p>","DOI":"10.1145\/3056561","type":"journal-article","created":{"date-parts":[[2017,6,13]],"date-time":"2017-06-13T12:18:36Z","timestamp":1497356316000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Spatio-Temporal Scheduling of Preemptive Real-Time Tasks on Partially Reconfigurable Systems"],"prefix":"10.1145","volume":"22","author":[{"given":"Sangeet","family":"Saha","sequence":"first","affiliation":[{"name":"A.K. Choudhury School of IT, University of Calcutta, West Bengal, India"}]},{"given":"Arnab","family":"Sarkar","sequence":"additional","affiliation":[{"name":"Dept of CSE, Indian Institute of Technology Guwahati, Guwahati, Assam"}]},{"given":"Amlan","family":"Chakrabarti","sequence":"additional","affiliation":[{"name":"A.K. Choudhury School of IT, University of Calcutta, West Bengal, India"}]}],"member":"320","published-online":{"date-parts":[[2017,6,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-90-481-3485-4_16"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/EMRTS.2000.853990"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/54.825678"},{"key":"e_1_2_1_4_1","unstructured":"M. Berkelaar P. Notebaert and K. Eikland. 2011. Lp solve 5.5 reference guide. (2011).  M. Berkelaar P. Notebaert and K. Eikland. 2011. Lp solve 5.5 reference guide. (2011)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13389-013-0048-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-16214-0_45"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/1000000003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/2492708.2492853"},{"key":"e_1_2_1_9_1","unstructured":"Chen-Chi Chiang. 2007. Hardware\/Software Real-time Relocatable Task Scheduling and Placement in Dynamically Partial Reconfigurable Systems. Ph.D. Dissertation. National Chung Cheng University Taiwan.  Chen-Chi Chiang. 2007. Hardware\/Software Real-time Relocatable Task Scheduling and Placement in Dynamically Partial Reconfigurable Systems. Ph.D. Dissertation. National Chung Cheng University Taiwan."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1134650.1134665"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978802.1978814"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/DASIP.2010.5706269"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2006.7"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICEE.2008.4553918"},{"key":"e_1_2_1_15_1","volume-title":"14th International VDI Congress Electronic Systems for Vehicles","volume":"62","author":"F\u00fcrst Simon","year":"2009","unstructured":"Simon F\u00fcrst , J\u00fcrgen M\u00f6ssinger , Stefan Bunzel , Thomas Weber , Frank Kirschke-Biller , Peter Heitk\u00e4mper , Gerulf Kinkelin , Kenji Nishikawa , and Klaus Lange . 2009 . AUTOSAR--A worldwide standard is on the road . In 14th International VDI Congress Electronic Systems for Vehicles , Baden-Baden , Vol. 62 . Simon F\u00fcrst, J\u00fcrgen M\u00f6ssinger, Stefan Bunzel, Thomas Weber, Frank Kirschke-Biller, Peter Heitk\u00e4mper, Gerulf Kinkelin, Kenji Nishikawa, and Klaus Lange. 2009. AUTOSAR--A worldwide standard is on the road. In 14th International VDI Congress Electronic Systems for Vehicles, Baden-Baden, Vol. 62."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391962.1391964"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2015.7293994"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-4-431-54610-8_5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1201\/9781420062670"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448556.2448636"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/LES.2012.2193660"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2010.76"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPL.2005.1515726"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/AHS.2014.6880151"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FPT.2005.1568523"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ECRTS.2010.34"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compeleceng.2013.07.004"},{"key":"e_1_2_1_30_1","volume-title":"Discrete Mathematics and Its Applications","author":"Rosen Kenneth","unstructured":"Kenneth Rosen . 2011. Discrete Mathematics and Its Applications ( 7 th ed.). McGraw-Hill Science . Kenneth Rosen. 2011. Discrete Mathematics and Its Applications (7th ed.). McGraw-Hill Science.","edition":"7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/LES.2015.2396069"},{"key":"e_1_2_1_32_1","volume-title":"Reconfiguration strategies for online hardware multitasking in embedded systems. Computer Science 8 Engineering 2, 6","author":"Sanchez-Elez Marcos","year":"2012","unstructured":"Marcos Sanchez-Elez and Sara Roman . 2012. Reconfiguration strategies for online hardware multitasking in embedded systems. Computer Science 8 Engineering 2, 6 ( 2012 ), 1. Marcos Sanchez-Elez and Sara Roman. 2012. Reconfiguration strategies for online hardware multitasking in embedded systems. Computer Science 8 Engineering 2, 6 (2012), 1."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/REAL.2003.1253269"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/123186.123255"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30117-2_26"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1723112.1723131"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ReCoSoC.2014.6861366"},{"volume-title":"Virtex-4 FPGA Configuration User Guide, xilinx. June","year":"2009","key":"e_1_2_1_38_1","unstructured":"Xilinx. 2009. Virtex-4 FPGA Configuration User Guide, xilinx. June ( 2009 ). Xilinx. 2009. Virtex-4 FPGA Configuration User Guide, xilinx. June (2009)."},{"key":"e_1_2_1_39_1","volume-title":"Virtex-4 family overview. Tech. Doc. DS112 (v2. 0)","author":"Xilinx Incorporation","year":"2010","unstructured":"Incorporation Xilinx . 2010. Virtex-4 family overview. Tech. Doc. DS112 (v2. 0) ( 2010 ), 1--8. Incorporation Xilinx. 2010. Virtex-4 family overview. Tech. Doc. DS112 (v2. 0) (2010), 1--8."},{"key":"e_1_2_1_40_1","volume-title":"Loke","author":"Yang Laurence T.","year":"2012","unstructured":"Laurence T. Yang , Evi Syukur , and Seng W . Loke . 2012 . Handbook on Mobile and Ubiquitous Computing: Status and Perspective. CRC Press . Laurence T. Yang, Evi Syukur, and Seng W. Loke. 2012. Handbook on Mobile and Ubiquitous Computing: Status and Perspective. CRC Press."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3056561","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3056561","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:30Z","timestamp":1750273650000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3056561"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,13]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3056561"],"URL":"https:\/\/doi.org\/10.1145\/3056561","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2017,6,13]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}