License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2019.5
URN: urn:nbn:de:0030-drops-107702
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10770/
Go to the corresponding OASIcs Volume Portal

Varoumas, Steven ; Crolard, Tristan

WCET of OCaml Bytecode on Microcontrollers: An Automated Method and Its Formalisation

pdf-format:
OASIcs-WCET-2019-5.pdf (0.6 MB)

Abstract

Considering the bytecode representation of a program written in a high-level programming language enables portability of its execution as well as a factorisation of various possible analyses of this program. In this article, we present a method for computing the worst-case execution time (WCET) of an embedded bytecode program fit to run on a microcontroller. Due to the simple memory model of such a device, this automated WCET computation relies only on a control-flow analysis of the program, and can be adapted to multiple models of microcontrollers. This method evaluates the bytecode program using concrete as well as partially unknown values, in order to estimate its longest execution time. We present a software tool, based on this method, that computes the WCET of a synchronous embedded OCaml program. One key contribution of this article is a mechanically checked formalisation of the aforementioned method over an idealised bytecode language, as well as its proof of correctness.

BibTeX - Entry

@InProceedings{varoumas_et_al:OASIcs:2019:10770,
  author =	{Steven Varoumas and Tristan Crolard},
  title =	{{WCET of OCaml Bytecode on Microcontrollers: An Automated Method and Its Formalisation}},
  booktitle =	{19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)},
  pages =	{5:1--5:12},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-118-4},
  ISSN =	{2190-6807},
  year =	{2019},
  volume =	{72},
  editor =	{Sebastian Altmeyer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10770},
  URN =		{urn:nbn:de:0030-drops-107702},
  doi =		{10.4230/OASIcs.WCET.2019.5},
  annote =	{Keywords: Worst-case execution time, microcontrollers, synchronous programming, bytecode, OCaml}
}

Keywords: Worst-case execution time, microcontrollers, synchronous programming, bytecode, OCaml
Collection: 19th International Workshop on Worst-Case Execution Time Analysis (WCET 2019)
Issue Date: 2019
Date of publication: 03.07.2019
Supplementary Material: http://stevenvar.github.io

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI