Efficient tree-based symbolic WCET computation

Grebant, Sandro; Ballabriga, Clement; Forget, Julien

Document type :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Title :

Efficient tree-based symbolic WCET computation

Author(s) :

Grebant, Sandro [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Ballabriga, Clement [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Forget, Julien [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]

Conference title :

Compas'21 :Conférence francophone d'informatique en Parallélisme, Architecture et Système

City :

Lyon

Country :

France

Start date of the conference :

2021-07-05

Publication date :

2021-07

English keyword(s) :

WCET
infeasible paths
symbolic analysis

HAL domain(s) :

Informatique [cs]
Informatique [cs]/Systèmes embarqués

English abstract : [en]

The worst case execution time (WCET) analysis allows to determine an upper bound to the execution time of a program. This analysis is required to perform a real-time schedulability analysis in order to make sure the program ...
Show more >The worst case execution time (WCET) analysis allows to determine an upper bound to the execution time of a program. This analysis is required to perform a real-time schedulability analysis in order to make sure the program will meet its deadline. This work is concerned with symbolic WCET analysis. Contrary to classical analyses which produces a constant value, symbolic WCET analysis produces a formula with different userdefined parameters of the program such as loop bounds for example. Instantiating this formula allows to compute several WCET bounds without executing the analysis several times. It also helps to analyze the impact of those parameters on the WCET. For example, the developer may want to analyze the impact of a loop bound on the WCET. We rely on a tree-based representation similar to a control-flow graph (CFG), albeit with a tree structure. Classical WCET analyses rely on integer linear programming with the implicit path enumeration technique but a tree-based representation is more suitable for a symbolic analysis. Relying on our existing symbolic WCET computation tool, the goal of our work is to be able to represent different hardware and software facts in order to tighten the resulting WCET bound. A hardware fact represents the effect of a hardware component, e.g. processor caches, on the execution time of the program. A software fact represents the effect of an element of the program structure, e.g. a loop bound, on the execution time of the program. To achieve those representations, existing techniques to model hardware facts need to be adapted to the tree-based representation and the existing annotation language needs to be enhanced. Annotations provide a way to express several flow facts which are not always related to the program structure. A great example would be a lower bound on the execution count of a part of a loop. We are currently working on the representation of infeasible paths for tree-based WCET analysis. The tree will be annotated with the results of an infeasible paths analysis. It will allow to tighten the resulting WCET by excluding some nodes from the WCET path.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Efficient tree-based symbolic WCET computation BibTeX CSV Excel RIS

Efficient tree-based symbolic WCET computation

BibTeX

CSV

Excel

RIS