Partial order based non-preemptive communication scheduling towards real-time networks-on-chip

Due to the increasing performance requirement of cyberphysical 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. DAGOrder 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.Ministry of Education (MOE)Accepted versionThis 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)