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

• Main Authors: Chen, Peng, Chen, Hui, Zhou, Jun, Liu, Di, Li, Shiqing, Liu, Weichen, Chang, Wanli, Guan, Nan
• Other Authors: School of Computer Science and Engineering
• Format: Conference or Workshop Item
• Language: English
• Published: 2021
• Subjects: Engineering::Computer science and engineering; Network-on-Chip (NoC); Directed Acyclic Graph (DAG)
• Online Access: https://hdl.handle.net/10356/151448
• Institution: Nanyang Technological University

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.