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

Peng Chen, Hui Chen, Jun Zhou, Di Liu, Shiqing Li, Weichen Liu, Wanli Chang, Nan Guan

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


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 <u>s</u>ingle-cycle <u>l</u>ong-range <u>t</u>raversal (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.

Original languageEnglish
Title of host publicationProceedings of the 36th Annual ACM Symposium on Applied Computing, SAC 2021
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450381048
Publication statusPublished - 22 Mar 2021
Event36th Annual ACM Symposium on Applied Computing, SAC 2021 - Virtual, Online, Korea, Republic of
Duration: 22 Mar 202126 Mar 2021

Publication series

NameProceedings of the ACM Symposium on Applied Computing


Conference36th Annual ACM Symposium on Applied Computing, SAC 2021
Country/TerritoryKorea, Republic of
CityVirtual, Online

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Partial order based non-preemptive communication scheduling towards real-time networks-on-chip'. Together they form a unique fingerprint.

Cite this