Message scheduling for real-time interprocessor communication

Stefan Waldherr*, Sigrid Knust, Stefan Aust

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review


In this paper an efficient algorithm is proposed which optimizes periodic message scheduling in a real-time multiprocessor system. The system is based on a many-core single-chip computer architecture and uses a multistage baseline network for inter-core communication. Due to its basic architecture, internal blockings can occur during data transfers, i.e. the baseline network is not real-time capable by itself. Therefore, we propose a scheduling algorithm that may be performed before the execution of an application in order to compute a non-blocking schedule of periodic message transfers. Additionally, we optimize the clock rate of the network subject to the constraint that all data transfers can be performed in a non-blocking way. Our solution algorithm is based on a generalized graph coloring model and a randomized greedy approach. The algorithm was tested on some realistic communication scenarios as they appear in modern electronic car units. Computational results show the effectiveness of the proposed algorithm.

Original languageEnglish
Pages (from-to)374-382
Number of pages9
JournalJournal of Systems Architecture
Issue number8
Publication statusPublished - 14 Sep 2015
Externally publishedYes


  • Baseline network
  • Graph coloring
  • Message scheduling
  • Periodic scheduling
  • Real time


Dive into the research topics of 'Message scheduling for real-time interprocessor communication'. Together they form a unique fingerprint.

Cite this