TY - JOUR
T1 - Message scheduling for real-time interprocessor communication
AU - Waldherr, Stefan
AU - Knust, Sigrid
AU - Aust, Stefan
PY - 2015/9/14
Y1 - 2015/9/14
N2 - 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.
AB - 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.
KW - Baseline network
KW - Graph coloring
KW - Message scheduling
KW - Periodic scheduling
KW - Real time
UR - http://www.scopus.com/inward/record.url?scp=84941315375&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84941315375&partnerID=8YFLogxK
U2 - 10.1016/j.sysarc.2015.06.002
DO - 10.1016/j.sysarc.2015.06.002
M3 - Article
AN - SCOPUS:84941315375
SN - 1383-7621
VL - 61
SP - 374
EP - 382
JO - Journal of Systems Architecture
JF - Journal of Systems Architecture
IS - 8
ER -