mdh.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Deriving WCET Bounds by Abstract Execution
Mälardalen University, School of Innovation, Design and Engineering.
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0001-6571-0175
Mälardalen University, School of Innovation, Design and Engineering.ORCID iD: 0000-0001-5297-6548
2011 (English)In: Proc. 11th International Workshop on Worst-Case Execution Time (WCET) Analysis (WCET 2011:), 2011, p. 72-82Conference paper, Published paper (Refereed)
Abstract [en]

Standard static WCET analysis methods today are based on the IPET technique, where WCET estimation is formulated as an integer linear programming (ILP) problem subject to linear program flow constraints with an objective function derived from the hardware timing model. The estimate is then calculated by an ILP solver. The hardware cost model, as well as the program flow constraints, are often derived using a static program analysis framework such as abstract interpretation. An alternative idea to estimate the WCET is to add time as an explicit variable, incremented for each basic block in the code. The possible values of this variable can then be bound by a value analysis. We have implemented this idea by integrating the time estimation in our Abstract Execution method for calculating program flow constraints. This method is in principle a very detailed value analysis. As it computes intervals bounding variable values, it bounds both the BCET and the WCET. In addition, it derives the explicit execution paths through the program which correspond to the calculated BCET and WCET bounds. We have compared the precision and the analysis time with the traditional IPET technique for a number of benchmark programs, and show that the new method typically is capable of calculating as tight or even tighter WCET estimates in shorter time. Our current implementation can handle simple timing models with constant execution times for basic blocks and edges in the CFG, but it is straightforward to extend the method to more detailed hardware timing models.

Place, publisher, year, edition, pages
2011. p. 72-82
National Category
Computer Sciences Computer and Information Sciences
Identifiers
URN: urn:nbn:se:mdh:diva-13594Scopus ID: 2-s2.0-84906236289ISBN: 9781632663153 (print)OAI: oai:DiVA.org:mdh-13594DiVA, id: diva2:466137
Conference
11th International Workshop on Worst-Case Execution Time Analysis, WCET 2011, Held at the 23rd Euromicro Conference on Real-Time Systems; Porto; Portugal; 5 July 2011 through 5 July 2011
Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Scopus

Authority records BETA

Gustafsson, JanLisper, Björn

Search in DiVA

By author/editor
Ermedahl, AndreasGustafsson, JanLisper, Björn
By organisation
School of Innovation, Design and Engineering
Computer SciencesComputer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 249 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf