Timing analysis of First-Come First-Served scheduled interval-timed Directed Acyclic Graphs
conference paper
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. cop. 2014 EDAA.
ACM-SIGDA; ECSI; EDA Consortium (EDAC); European Design and Automation Association (EDAA); IEEE Council on Electronic Design Automation (CEDA); Russian Academy of Sciences (RAS)
ACM-SIGDA; ECSI; EDA Consortium (EDAC); European Design and Automation Association (EDAA); IEEE Council on Electronic Design Automation (CEDA); Russian Academy of Sciences (RAS)
Topics
TNO Identifier
503237
ISSN
15301591
ISBN
783981537024
Publisher
Institute of Electrical and Electronics Engineers Inc.
Article nr.
6800502
Source title
17th Design, Automation and Test in Europe, DATE 2014, 24 March 2014 through 28 March 2014, Dresden
Files
To receive the publication files, please send an e-mail request to TNO Repository.