Symbolic WCET Computation
| Autor: | Clément Ballabriga, Julien Forget, Giuseppe Lipari |
|---|---|
| Přispěvatelé: | Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), ANR-17-CE25-0003,Corteva,Une méthodologie correcte par construction pour supporter la variabilité du temps d'exécution dans les systèmes temps réel(2017) |
| Rok vydání: | 2017 |
| Předmět: |
[INFO.INFO-AR]Computer Science [cs]/Hardware Architecture [cs.AR]
Correctness Computer science Computation Embedded Software 02 engineering and technology Set (abstract data type) Worst-case execution time 0202 electrical engineering electronic engineering information engineering Integer programming Wcet Parametric statistics 060201 languages & linguistics CCS Concepts: • Computer systems organization → Real-Time Systems 06 humanities and the arts Symbolic computations Symbolic computation symbolic evaluation Additional Key Words and Phrases: Worst-case execution time Hardware and Architecture Real-time Embedded Systems 0602 languages and literature [INFO.INFO-ES]Computer Science [cs]/Embedded Systems 020201 artificial intelligence & image processing [INFO.INFO-OS]Computer Science [cs]/Operating Systems [cs.OS] State (computer science) Algorithm Software |
| Zdroj: | ACM Transactions on Embedded Computing Systems (TECS) ACM Transactions on Embedded Computing Systems (TECS), ACM, 2017, 17 (2), pp.1-26. ⟨10.1145/3147413⟩ ACM Transactions on Embedded Computing Systems (TECS), 2017, 17 (2), pp.1-26. ⟨10.1145/3147413⟩ |
| ISSN: | 1558-3465 1539-9087 |
| DOI: | 10.1145/3147413 |
| Popis: | Parametric Worst-case execution time (WCET) analysis of a sequential program produces a formula that represents the worst-case execution time of the program, where parameters of the formula are user-defined parameters of the program (as loop bounds, values of inputs, or internal variables, etc). In this article we propose a novel methodology to compute the parametric WCET of a program. Unlike other algorithms in the literature, our method is not based on Integer Linear Programming (ILP). Instead, we follow an approach based on the notion of symbolic computation of WCET formulae. After explaining our methodology and proving its correctness, we present a set of experiments to compare our method against the state of the art. We show that our approach dominates other parametric analyses and produces results that are very close to those produced by non-parametric ILP-based approaches, while keeping very good computing time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|