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

Abstract

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
DOIs
Publication statusPublished - 2019
Externally publishedYes
EventDesign, Automation & Test in Europe Conference & Exhibition, DATE 2019 - Florence, Italy
Duration: 25 Mar 201929 Mar 2019

Conference

ConferenceDesign, Automation & Test in Europe Conference & Exhibition, DATE 2019
Abbreviated titleDATE 2019
CountryItaly
CityFlorence
Period25/03/1929/03/19

Fingerprint

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

Cite this