Efficient Latency Bound Analysis for Data Chains of Real-Time Tasks in Multiprocessor Systems
Jiankang Ren1,a, Xin He1, Junlong Zhou2, Hongwei Ge1, Guowei Wu3 and Guozhen Tan1
1School of Computer Science and Technology, Dalian University of Technology, China
arjk@dlut.edu.cn
2School of Computer Science and Engineering, Nanjing University of Science and Technology, China
3School of Software Technology, Dalian University of Technology, China
ABSTRACT
End-to-end latency analysis is one of the key problems in the automotive embedded system design. In this paper, we propose an efficient worst-case end-to-end latency analysis method for data chains of periodic real-time tasks executed on multiprocessors under a partitioned fixed-priority preemptive scheduling policy. The key idea of this research is to improve the analysis efficiency by transforming the problem of bounding the worst-case latency of the data chain to a problem of bounding the releasing interval of data propagation instances for each pair of consecutive tasks in the chain. In particular, we derive an upper bound on the releasing interval of successive data propagation instances to yield the desired data chain latency bound by a simple accumulation. Based on the above idea, we present an efficient latency upper bound analysis algorithm with polynomial time complexity. Experiments with randomly generated task sets based on a generic automotive benchmark show that our proposed approach can obtain a relatively tighter data chain latency upper bound with lower computational cost.
