Timing analysis of first-come first-served scheduled interval-timed directed acyclic graphs

R.M.W. Frijns, S. Adyanthaya, S. Stuijk, J.P.M. Voeten, M.C.W. Geilen, R.R.H. Schiffelers, H. Corporaal

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

6 Citations (Scopus)
1 Downloads (Pure)

Abstract

Analyzing worst-case application timing for systems with shared resources is difficult, especially when non-monotonic arbitration policies like First-Come-First-Served (FCFS) scheduling are used in combination with varying task execution times. Analysis methods that conservatively analyze these systems are often based on state-space exploration, which is not scalable due to its inherent susceptibility to combinatorial explosion. We propose a scalable timing analysis method on periodically restarted Directed Acyclic Task Graphs, that can provide conservative bounds on task timing properties when shared resources with FCFS scheduling are used. By expressing task enabling and completion times in intervals, denoting best-case and worst-case timing properties, contention on the shared resources can be estimated using conservative approximations. With an industrial case study we show that our approach can easily analyze models with thousands of tasks in less than 10 seconds, and the worst-case bounds obtained show an average improvement of 46% compared to bounds obtained by static worst-case analysis.
Original languageEnglish
Title of host publicationProceedings of the design, automation and test in Europe(DATE) 24-28 March 2014, Dresden, Germany
Place of PublicationPiscataway
PublisherInstitute of Electrical and Electronics Engineers
Pages1-6
ISBN (Print)978-3-9815370-2-4
DOIs
Publication statusPublished - 2014
Event17th Design, Automation and Test in Europe Conference and Exhibition (DATE 2014) - ICC, Dresden, Germany
Duration: 24 Mar 201428 Mar 2014
Conference number: 17
https://www.date-conference.com/date14/

Conference

Conference17th Design, Automation and Test in Europe Conference and Exhibition (DATE 2014)
Abbreviated titleDATE 2014
Country/TerritoryGermany
City Dresden
Period24/03/1428/03/14
Internet address

Fingerprint

Dive into the research topics of 'Timing analysis of first-come first-served scheduled interval-timed directed acyclic graphs'. Together they form a unique fingerprint.

Cite this