Efficient Computation of Deadline-Miss Probability and Potential Pitfalls

K.-H. Chen, N. Ueter, G.V. Der Brüggen, J.-J. Chen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)


In soft real-time systems, applications can tolerate rare deadline misses. Therefore, probabilistic arguments and analyses are applicable in the timing analyses for this class of systems, as demonstrated in many existing researches. Convolution-based analyses allow to derive tight deadline-miss probabilities, but suffer from a high time complexity. Among the analytical approaches, which result in a significantly faster runtime than the convolution-based approaches, the Chernoff bounds provide the tightest results. In this paper, we show that calculating the deadline-miss probability using Chernoff bounds can be solved by considering an equivalent convex optimization problem. This allows us to, on the one hand, decrease the runtime of the Chernoff bounds while, on the other hand, ensure a tighter approximation since a larger variable space can be searched more efficiently, i.e., by using binary search techniques over a larger area instead of a sequential search over a smaller area. We evaluate this approach considering synthesized task sets. Our approach is shown to be computationally efficient for large task systems, whilst experimentally suggesting reasonable approximation quality compared to an exact analysis.
Original languageEnglish
Title of host publicationProceedings of the 2019 Design, Automation and Test in Europe Conference and Exhibition, DATE 2019
ISBN (Electronic)978-3-9819263-2-3
Publication statusPublished - 2019
Externally publishedYes
Event2019 Design, Automation & Test in Europe Conference & Exhibition, DATE 2019 - Florence, Italy
Duration: 25 Mar 201929 Mar 2019


Conference2019 Design, Automation & Test in Europe Conference & Exhibition, DATE 2019
Abbreviated titleDATE


Dive into the research topics of 'Efficient Computation of Deadline-Miss Probability and Potential Pitfalls'. Together they form a unique fingerprint.

Cite this