https://www.mdu.se/

mdu.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
Analyzing Execution-Time of Object-Oriented Programs Using Abstract Interpretation
Mälardalen University, Department of Computer Science and Electronics.ORCID iD: 0000-0001-6571-0175
2000 (English)Doctoral thesis, monograph (Other scientific)
Abstract [en]

As a result of the industrial deployment of real-time systems, there is an increasing demand for methods to perform safe and tight calculation of the worst case execution time (WCET) of programs. The WCET is a necessary prerequisite for guaranteeing correct timing behaviour of real-time systems. WCET calculation means to find the path, often among a huge number of paths, that takes the longest time to execute. The calculation is based on path information for the program, such as the maximum number of iterations in loops and identification of paths that are never executed. In most existing WCET analysis methods, this information is given as manual annotations by the programmer. In this thesis we present a method which automatically calculates path information for object-oriented real-time programs by static analysis. Thus, the method can be used in automating the WCET analysis, thereby relieving the programmer from the tedious and error-prone manual annotation work. The method, which is based on abstract interpretation, generates safe but not necessarily exact path information. A trade-off between quality and calculation cost has to be made, since finding the exact information is a complex, often intractable problem for non-trivial programs. We show how the general abstract interpretation theory can be used, in a structured way, to approximate the semantics of an imperative or object-oriented programming language. We have chosen to analyze RealTimeTalk (RTT), an object-oriented language based on Smalltalk, and have developed a prototype tool which implements our analysis for a subset of the language. We show that the tool is capable of analyzing programs with a complexity which would make manual annotation of the program all but trivial.

Place, publisher, year, edition, pages
2000.
Identifiers
URN: urn:nbn:se:mdh:diva-1835OAI: oai:DiVA.org:mdh-1835DiVA, id: diva2:114498
Available from: 2008-11-11 Created: 2008-11-11 Last updated: 2013-12-03

Open Access in DiVA

No full text in DiVA

Authority records

Gustafsson, Jan

Search in DiVA

By author/editor
Gustafsson, Jan
By organisation
Department of Computer Science and Electronics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 639 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