Int. J. of Critical Computer-Based Systems   »   2016 Vol.6, No.4



Title: Hierarchical timed abstract state machines for WCET estimation


Authors: Vladimir-Alexandru Paun; Bruno Monsuez; Philippe Baufreton


UIIS, ENSTA ParisTech, 828, Boulevard des Maréchaux, 91762 Palaiseau Cedex, France
UIIS, ENSTA ParisTech, 828, Boulevard des Maréchaux, 91762 Palaiseau Cedex, France
Sagem – SAFRAN Electronics, Etablissement F. Hussenot – R&D, 100 avenue de Paris 91344 MASSY Cedex, France


Abstract: In this paper, we present an extension of the abstract state machines suited for the modelling of complex processors in the context of system verification. Besides processor simulation, the goal of our model is to provide a base for worst-case execution time estimation, providing abstraction capabilities that enable the scaling of analysis. The main difference between our model and other ASM extensions is that we define time as a mean to enable time accurate runs and hierarchical abstraction levels of components, while staying the closest possible to the original ASM mathematical foundation. The model is also designed to dynamically choose a suited component definition in order to adapt to information precision on data values. The time extension helps modelling non-instantaneous actions, which is essential for real-time systems. Adaptable precision and separation of the analysis from the model of the processor will prove well suited for integration into a worst-case execution time estimation tool.


Keywords: abstract state machines; ASM; worst-case execution time; WCET estimation; hard real-time systems; hardware modelling; formal languages; processor simulation; cycle accuracy; time accuracy; system verification; non-instantaneous actions.


DOI: 10.1504/IJCCBS.2016.081810


Int. J. of Critical Computer-Based Systems, 2016 Vol.6, No.4, pp.343 - 363


Available online: 25 Jan 2017



Editors Full text accessPurchase this articleComment on this article