{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:10:25Z","timestamp":1750219825011,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,9,26]],"date-time":"2023-09-26T00:00:00Z","timestamp":1695686400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["CNS-1932480, CNS-2008463, CCF-2028875"],"award-info":[{"award-number":["CNS-1932480, CNS-2008463, CCF-2028875"]}]},{"name":"Nebraska Research Initiative","award":["NRI-4103080440"],"award-info":[{"award-number":["NRI-4103080440"]}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"crossref","award":["N00014-17-1-2216"],"award-info":[{"award-number":["N00014-17-1-2216"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            We consider the problem of resource provisioning for real-time cyber-physical applications in an open system environment where there does not exist a global resource scheduler that has complete knowledge of the real-time performance requirements of each individual application that shares the resources with the other applications. Regularity-based Resource Partition (RRP) model is an effective strategy to hierarchically partition and assign various resource slices among such applications. However, previous work on RRP model only discusses uniform resource environment, where resources are implicitly assumed to be synchronized and clocked at the same frequency. The challenge is that a task utilizing multiple resources may experience unexpected delays in non-uniform environments, where resources are clocked at different frequencies. This paper extends the RRP model to non-uniform multi-resource open system environments to tackle this problem. It first introduces a novel composite resource partition abstraction and then proposes algorithms to construct and reconfigure the composite resource partitions. Specifically, the\n            <jats:italic>Acyclic Regular Composite Resource Partition Scheduling (ARCRP-S)<\/jats:italic>\n            algorithm constructs regular composite resource partitions and the\n            <jats:italic>Acyclic Regular Composite Resource Partition Dynamic Reconfiguration (ARCRP-DR)<\/jats:italic>\n            algorithm reconfigures the composite resource partitions in the run time upon requests of partition configuration changes. Our experimental results show that compared with state-of-the-art methods, ARCRP-S can prevent unexpected resource supply shortfall and improve the schedulability up to 50%. On the other hand, ARCRP-DR can guarantee the resource supply during the reconfiguration with moderate computational overhead.\n          <\/jats:p>","DOI":"10.1145\/3609424","type":"journal-article","created":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T12:26:51Z","timestamp":1689683211000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Regular Composite Resource Partitioning and Reconfiguration in Open Systems"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5978-9235","authenticated-orcid":false,"given":"Wei-Ju","family":"Chen","sequence":"first","affiliation":[{"name":"The University of Texas at Austin, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7175-6679","authenticated-orcid":false,"given":"Peng","family":"Wu","sequence":"additional","affiliation":[{"name":"University of Connecticut, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7163-2772","authenticated-orcid":false,"given":"Pei-Chi","family":"Huang","sequence":"additional","affiliation":[{"name":"The University of Nebraska at Omaha, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1309-8425","authenticated-orcid":false,"given":"Aloysius K.","family":"Mok","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1491-7675","authenticated-orcid":false,"given":"Song","family":"Han","sequence":"additional","affiliation":[{"name":"University of Connecticut, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,9,26]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"308","volume-title":"18th IEEE Real-Time Systems Symposium (RTSS)","author":"Deng Zhong","year":"1997","unstructured":"Zhong Deng and J. W.-S. Liu. 1997. Scheduling real-time applications in an open environment. In 18th IEEE Real-Time Systems Symposium (RTSS). IEEE, 308\u2013319."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procir.2015.02.110"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/1023508"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1109\/ISORC.2018.00015","volume-title":"21st IEEE International Symposium on Real-Time Distributed Computing (ISORC)","author":"Boudjadar Jalil","year":"2018","unstructured":"Jalil Boudjadar, Jin Hyun Kim, Linh Thi Xuan Phan, Insup Lee, Kim G. Larsen, and Ulrik Nyman. 2018. Generic formal framework for compositional analysis of hierarchical scheduling systems. In 21st IEEE International Symposium on Real-Time Distributed Computing (ISORC). IEEE, 51\u201358."},{"issue":"4","key":"e_1_3_2_6_2","first-page":"111","article-title":"Toward a practical regularity-based model: The impact of evenly distributed temporal resource partitions","volume":"16","author":"Li Yu","year":"2017","unstructured":"Yu Li and Albert M. K. Cheng. 2017. Toward a practical regularity-based model: The impact of evenly distributed temporal resource partitions. ACM Transactions on Embedded Computing Systems (TECS) 16, 4 (2017), 111.","journal-title":"ACM Transactions on Embedded Computing Systems (TECS)"},{"key":"e_1_3_2_7_2","first-page":"2","volume-title":"24th IEEE Real-Time Systems Symposium (RTSS)","author":"Shin Insik","year":"2003","unstructured":"Insik Shin and Insup Lee. 2003. Periodic resource model for compositional real-time guarantees. In 24th IEEE Real-Time Systems Symposium (RTSS). IEEE, 2\u201313."},{"key":"e_1_3_2_8_2","first-page":"129","volume-title":"28th IEEE Real-Time Systems Symposium (RTSS)","author":"Easwaran Arvind","year":"2007","unstructured":"Arvind Easwaran, Madhukar Anand, and Insup Lee. 2007. Compositional analysis framework using EDP resource models. In 28th IEEE Real-Time Systems Symposium (RTSS). IEEE, 129\u2013138."},{"issue":"5","key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"1646","DOI":"10.1109\/TC.2015.2449857","article-title":"Transparent real-time task scheduling on temporal resource partitions","volume":"65","author":"Li Yu","year":"2015","unstructured":"Yu Li and Albert Mo Kim Cheng. 2015. Transparent real-time task scheduling on temporal resource partitions. IEEE Trans. Comput. 65, 5 (2015), 1646\u20131655.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_10_2","first-page":"137","volume-title":"33rd IEEE Real-Time Systems Symposium (RTSS)","author":"Li Yu","year":"2012","unstructured":"Yu Li and Albert M. K. Cheng. 2012. Static approximation algorithms for regularity-based resource partitioning. In 33rd IEEE Real-Time Systems Symposium (RTSS). IEEE, 137\u2013148."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940883"},{"key":"e_1_3_2_12_2","first-page":"129","volume-title":"22nd IEEE Real-Time Systems Symposium (RTSS)","author":"Mok Aloysius K.","year":"2001","unstructured":"Aloysius K. Mok and Xiang Feng. 2001. Towards compositionality in real-time resource partitioning based on regularity bounds. In 22nd IEEE Real-Time Systems Symposium (RTSS). IEEE, 129\u2013138."},{"key":"e_1_3_2_13_2","first-page":"1","article-title":"Online reconfiguration of regularity-based resource partitions in cyber-physical systems","author":"Chen Wei-Ju","year":"2021","unstructured":"Wei-Ju Chen, Peng Wu, Pei-Chi Huang, Aloysius K. Mok, and Song Han. 2021. Online reconfiguration of regularity-based resource partitions in cyber-physical systems. Real-Time Systems (2021), 1\u201344.","journal-title":"Real-Time Systems"},{"key":"e_1_3_2_14_2","volume-title":"International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)","author":"Shirero S.","year":"1999","unstructured":"S. Shirero, Matsumoto Takashi, and Hiraki Kei. 1999. On the schedulability conditions on partial time slots. In International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA)."},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1023\/B:TIME.0000027934.77900.22"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2009.2013633"},{"key":"e_1_3_2_17_2","volume-title":"22nd Euromicro Conference on Real-Time Systems (ECRTS)","author":"Buttazzo Giorgio","year":"2010","unstructured":"Giorgio Buttazzo, Enrico Bini, and Yifan Wu. 2010. Partitioning parallel applications on multiprocessor reservations. In 22nd Euromicro Conference on Real-Time Systems (ECRTS)."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2011.2123902"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2788396"},{"issue":"5","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"1184","DOI":"10.1109\/TPDS.2018.2878699","article-title":"A survey of prediction and classification techniques in multicore processor systems","volume":"30","author":"Ababei Cristinel","year":"2018","unstructured":"Cristinel Ababei and Milad Ghorbani Moghaddam. 2018. A survey of prediction and classification techniques in multicore processor systems. IEEE Trans. on Parallel and Distributed Systems 30, 5 (2018), 1184\u20131200.","journal-title":"IEEE Trans. on Parallel and Distributed Systems"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1145\/1383422.1383447","volume-title":"Proceedings of the 17th International Symposium on High Performance Distributed Computing","author":"Diamos Gregory F.","year":"2008","unstructured":"Gregory F. Diamos and Sudhakar Yalamanchili. 2008. Harmony: An execution model and runtime for heterogeneous many core systems. In Proceedings of the 17th International Symposium on High Performance Distributed Computing. 197\u2013200."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.1631"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2798725"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2019.05.015"},{"key":"e_1_3_2_25_2","first-page":"1","volume-title":"2014 21st International Conference on High Performance Computing (HiPC)","author":"Wen Yuan","year":"2014","unstructured":"Yuan Wen, Zheng Wang, and Michael F. P. O\u2019Boyle. 2014. Smart multi-task scheduling for OpenCL programs on CPU\/GPU heterogeneous platforms. In 2014 21st International Conference on High Performance Computing (HiPC). IEEE, 1\u201310."},{"key":"e_1_3_2_26_2","first-page":"78","volume-title":"the 14th ACM\/IEEE Symposium on Embedded Systems for Real-Time Multimedia","author":"Dev Kapil","year":"2016","unstructured":"Kapil Dev and Sherief Reda. 2016. Scheduling challenges and opportunities in integrated CPU+ GPU processors. In the 14th ACM\/IEEE Symposium on Embedded Systems for Real-Time Multimedia. 78\u201383."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11241-015-9223-2"},{"key":"e_1_3_2_28_2","first-page":"211","volume-title":"2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)","author":"Xu Meng","year":"2017","unstructured":"Meng Xu, Linh Thi, Xuan Phan, Hyon-Young Choi, and Insup Lee. 2017. vCAT: Dynamic cache management using CAT virtualization. In 2017 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 211\u2013222."},{"key":"e_1_3_2_29_2","first-page":"34","volume-title":"38th IEEE Real-Time Systems Symposium (RTSS)","author":"Chen Wei-Ju","year":"2017","unstructured":"Wei-Ju Chen, Pei-Chi Huang, Quan Leng, Aloysius K. Mok, and Song Han. 2017. Regular composite resource partition in open systems. In 38th IEEE Real-Time Systems Symposium (RTSS). IEEE, 34\u201344."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3131347"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1109\/RTSS46320.2019.00037","volume-title":"2019 IEEE Real-Time Systems Symposium (RTSS)","author":"Jiang Zhe","year":"2019","unstructured":"Zhe Jiang, Neil Audsley, Pan Dong, Nan Guan, Xiaotian Dai, and Lifeng Wei. 2019. MCS-IOV: Real-time i\/o virtualization for mixed-criticality systems. In 2019 IEEE Real-Time Systems Symposium (RTSS). IEEE, 326\u2013338."},{"key":"e_1_3_2_32_2","first-page":"1","volume-title":"2013 International Conference on Hardware\/Software Codesign and System Synthesis (CODES+ ISSS)","author":"Neukirchner Moritz","year":"2013","unstructured":"Moritz Neukirchner, Kai Lampka, Sophie Quinton, and Rolf Ernst. 2013. Multi-mode monitoring for mixed-criticality real-time systems. In 2013 International Conference on Hardware\/Software Codesign and System Synthesis (CODES+ ISSS). IEEE, 1\u201310."},{"key":"e_1_3_2_33_2","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1109\/RTAS.2014.6925995","volume-title":"2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS)","author":"Niz Dionisio de","year":"2014","unstructured":"Dionisio de Niz and Linh T. X. Phan. 2014. Partitioned scheduling of multi-modal mixed-criticality real-time systems on multiprocessor platforms. In 2014 IEEE 19th Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 111\u2013122."},{"key":"e_1_3_2_34_2","first-page":"3","volume-title":"Proc. of 2nd Workshop on Mixed Criticality Systems (WMC)","author":"Burns Alan","year":"2014","unstructured":"Alan Burns. 2014. System mode changes-general and criticality-based. In Proc. of 2nd Workshop on Mixed Criticality Systems (WMC). 3\u20138."},{"key":"e_1_3_2_35_2","first-page":"47","volume-title":"2016 IEEE Real-Time Systems Symposium (RTSS)","author":"Gu Xiaozhe","year":"2016","unstructured":"Xiaozhe Gu and Arvind Easwaran. 2016. Dynamic budget management with service guarantees for mixed-criticality systems. In 2016 IEEE Real-Time Systems Symposium (RTSS). IEEE, 47\u201356."},{"key":"e_1_3_2_36_2","volume-title":"WMC 2016 4th International Workshop on Mixed Criticality Systems","author":"Evripidou Chiristos","year":"2016","unstructured":"Chiristos Evripidou and A. Burns. 2016. Scheduling for mixed-criticality hypervisor systems in the automotive domain. In WMC 2016 4th International Workshop on Mixed Criticality Systems."},{"key":"e_1_3_2_37_2","first-page":"1","article-title":"FFOB: Efficient online mode-switch procrastination in mixed-criticality systems","author":"Hu Biao","year":"2018","unstructured":"Biao Hu, Lothar Thiele, Pengcheng Huang, Kai Huang, Christoph Griesbeck, and Alois Knoll. 2018. FFOB: Efficient online mode-switch procrastination in mixed-criticality systems. Real-Time Systems (2018), 1\u201343.","journal-title":"Real-Time Systems"},{"key":"e_1_3_2_38_2","first-page":"105","volume-title":"25th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)","author":"Chen Tianyang","year":"2018","unstructured":"Tianyang Chen and Linh Thi Xuan Phan. 2018. SafeMC: A system for the design and evaluation of mode-change protocols. In 25th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 105\u2013116."},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2019.01.015"},{"key":"e_1_3_2_40_2","first-page":"197","volume-title":"22nd Euromicro Conference on Real-Time Systems (ECRTS)","author":"Phan Linh T. X.","year":"2010","unstructured":"Linh T. X. Phan, Insup Lee, and Oleg Sokolsky. 2010. Compositional analysis of multi-mode systems. In 22nd Euromicro Conference on Real-Time Systems (ECRTS). IEEE, 197\u2013206."},{"key":"e_1_3_2_41_2","first-page":"117","volume-title":"24th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS)","author":"Li Haoran","year":"2018","unstructured":"Haoran Li, Meng Xu, Chong Li, Chenyang Lu, Christopher Gill, Linh Phan, Insup Lee, and Oleg Sokolsky. 2018. Multi-mode virtualization for soft real-time systems. In 24th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS). IEEE, 117\u2013128."},{"key":"e_1_3_2_42_2","volume-title":"29th Euromicro Conference on Real-Time Systems (ECRTS)","author":"Nikolov Vladimir","year":"2017","unstructured":"Vladimir Nikolov, Stefan Wesner, Eugen Frasch, and Franz J. Hauck. 2017. A hierarchical scheduling model for dynamic soft-realtime system. In 29th Euromicro Conference on Real-Time Systems (ECRTS)."},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3461648.3463854"},{"issue":"1","key":"e_1_3_2_44_2","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/0165-6074(89)90128-2","article-title":"Algorithms and complexity of the periodic maintenance problem","volume":"27","author":"Mok A. K.","year":"1989","unstructured":"A. K. Mok, L. Rosier, I. Tulchinsky, and D. Varvel. 1989. Algorithms and complexity of the periodic maintenance problem. Microprocessing and Microprogramming 27, 1 (1989), 657\u2013664.","journal-title":"Microprocessing and Microprogramming"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1109\/RTSS46320.2019.00050","volume-title":"2019 IEEE Real-Time Systems Symposium (RTSS)","author":"Chen Wei-Ju","year":"2019","unstructured":"Wei-Ju Chen, Peng Wu, Pei-Chi Huang, Aloysius K. Mok, and Song Han. 2019. Online reconfiguration of regularity-based resource partitions in cyber-physical systems. In 2019 IEEE Real-Time Systems Symposium (RTSS). IEEE, 495\u2013507."},{"issue":"4","key":"e_1_3_2_46_2","first-page":"979","article-title":"Schedulability analysis of deferrable scheduling algorithms for maintaining real-time data freshness","volume":"63","author":"Han Song","year":"2012","unstructured":"Song Han, Deji Chen, Ming Xiong, Kam-Yiu Lam, Aloysius K. Mok, and Krithi Ramamritham. 2012. Schedulability analysis of deferrable scheduling algorithms for maintaining real-time data freshness. IEEE Trans. Comput. 63, 4 (2012), 979\u2013994.","journal-title":"IEEE Trans. Comput."},{"key":"e_1_3_2_47_2","first-page":"140","volume-title":"Real-Time Systems Symposium","author":"Wei Yi-Hung","year":"2013","unstructured":"Yi-Hung Wei, Quan Leng, Song Han, Aloysius K. Mok, Wenlong Zhang, and Masayoshi Tomizuka. 2013. RT-WiFi: Real-time high-speed communication protocol for wireless cyber-physical control applications. In Real-Time Systems Symposium. IEEE, 140\u2013149."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.5555\/1965374"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3609424","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3609424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:23Z","timestamp":1750178783000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3609424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,26]]},"references-count":47,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3609424"],"URL":"https:\/\/doi.org\/10.1145\/3609424","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2023,9,26]]},"assertion":[{"value":"2022-08-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}