TY - GEN
T1 - Partial order based non-preemptive communication scheduling towards real-time networks-on-chip
AU - Chen, Peng
AU - Chen, Hui
AU - Zhou, Jun
AU - Liu, Di
AU - Li, Shiqing
AU - Liu, Weichen
AU - Chang, Wanli
AU - Guan, Nan
N1 - Funding Information:
This work is partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (MoE2019-T2-1-071) and Tier 1 (MoE2019-T1-001-072), and Nanyang Technological University, Singapore, under its NAP (M4082282) and SUG (M4082087).
Publisher Copyright:
© 2021 ACM.
PY - 2021/3/22
Y1 - 2021/3/22
N2 - Due to the increasing performance requirement of cyber-physical systems, many-core processors with high parallelism are gaining wide utilization, where network-on-chip (NoC) is a prevalent choice for inter-core communication. Unfortunately, the contention on NoCs introduces large timing uncertainties, which complicates the response time estimation. To address this problem, for real-time applications modeled as a directed acyclic graph (DAG), we introduce DAG-Order, a partial order based time-predictable scheduling paradigm, resulting in real-time NoCs. Specifically, DAG-Order is built upon an existing single-cycle long-range traversal (SLT) NoC that is to simplify the process of validation and verification. Then, DAG-Order is proposed based on a dynamic scheduling approach, which jointly considers communication as well as computation workloads, and matches SLT NoC. DAG-Order achieves provably bound safety by enforcing certain partial order constraints among edges/vertices that eliminate the execution-timing anomaly during the runtime phase. Finally, an effective algorithm exploring for a proper schedule order is deployed to tighten the upper bound. Experimental results demonstrate that DAG-Order performs better than state-of-the-art scheduling approaches.
AB - Due to the increasing performance requirement of cyber-physical systems, many-core processors with high parallelism are gaining wide utilization, where network-on-chip (NoC) is a prevalent choice for inter-core communication. Unfortunately, the contention on NoCs introduces large timing uncertainties, which complicates the response time estimation. To address this problem, for real-time applications modeled as a directed acyclic graph (DAG), we introduce DAG-Order, a partial order based time-predictable scheduling paradigm, resulting in real-time NoCs. Specifically, DAG-Order is built upon an existing single-cycle long-range traversal (SLT) NoC that is to simplify the process of validation and verification. Then, DAG-Order is proposed based on a dynamic scheduling approach, which jointly considers communication as well as computation workloads, and matches SLT NoC. DAG-Order achieves provably bound safety by enforcing certain partial order constraints among edges/vertices that eliminate the execution-timing anomaly during the runtime phase. Finally, an effective algorithm exploring for a proper schedule order is deployed to tighten the upper bound. Experimental results demonstrate that DAG-Order performs better than state-of-the-art scheduling approaches.
UR - http://www.scopus.com/inward/record.url?scp=85104935221&partnerID=8YFLogxK
U2 - 10.1145/3412841.3441895
DO - 10.1145/3412841.3441895
M3 - Conference article published in proceeding or book
AN - SCOPUS:85104935221
T3 - Proceedings of the ACM Symposium on Applied Computing
SP - 145
EP - 154
BT - Proceedings of the 36th Annual ACM Symposium on Applied Computing, SAC 2021
PB - Association for Computing Machinery
T2 - 36th Annual ACM Symposium on Applied Computing, SAC 2021
Y2 - 22 March 2021 through 26 March 2021
ER -