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
Calculation of WCET with symbolic execution
Luleå University of Technology, Department of Computer Science, Electrical and Space Engineering.
2022 (English)Independent thesis Advanced level (professional degree), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Calculating WCET for schedulability analysis of RTIC applications is today performed with a hybrid approach with both static analysis of code and hardware measurements. A fully static analysis tool would allow for a easier integration into a CI/CD pipeline without the actual hardware. This thesis attempts to compute WCET statically, using symbolic execution engine KLEE to generate all the possible paths of execution for a task and then analyses these paths to approximate the worst-case for each path which would yield a approximate WCET for the analysed program.

To analyze a path in a program the low-level intermediary assembly language used by the LLVM optimization infrastructure (called LLVM IR) is compared to the finished assembly language to draw conclusions on how an LLVM IR instruction is processed into assembly. To be able to perform this mapping from LLVM IR to assembly, the symbolic execution engine KLEE has been extended to also log each LLVM IR instruction run in a path. These logs combined with a translation table is how the approximations are calculated.

The resulting approximations correlate with the actual cycles when the analysed program is run on actual hardware, which indicates that tool could actually be used to approximate WCET. There are however no guarantees and the tool has not been tested for larger scale programs.

Place, publisher, year, edition, pages
2022. , p. 37
Keywords [en]
wcet, klee, static analysis, rust, llvm
National Category
Computer Engineering
Identifiers
URN: urn:nbn:se:ltu:diva-92596OAI: oai:DiVA.org:ltu-92596DiVA, id: diva2:1689116
Educational program
Computer Science and Engineering, master's level
Supervisors
Examiners
Available from: 2022-08-22 Created: 2022-08-22 Last updated: 2022-08-22Bibliographically approved

Open Access in DiVA

fulltext(1082 kB)174 downloads
File information
File name FULLTEXT01.pdfFile size 1082 kBChecksum SHA-512
73624007eccda0e692cc875f039da4161aa6b2a999bf92ece54c2339535110f5e2fca8e5033de1c8de7b63ed696e4f6d6df824628eaaf7e79cf8c9e46e087455
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Österberg, Carl
By organisation
Department of Computer Science, Electrical and Space Engineering
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 174 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

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