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

Abstract

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
Pages145-154
Number of pages10
ISBN (Electronic)9781450381048
DOIs
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

Conference

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

ASJC Scopus subject areas

  • Software

Cite this