Long-Run Cost Analysis by Approximation of Linear Operators over Dioids

David Cachera 1 Thomas Jensen 1 Arnaud Jobin 1 Pascal Sotin 1
1 Lande - Logiciel : ANalyse et DEveloppement
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : We present a static analysis technique for modeling and approxi- mating the long-run resource usage of programs. The approach is based on a quantitative semantic framework where programs are represented as linear op- erators over dioids. We show how to extract the long-run cost of a program from the matrix representation of its semantics. An essential contribution is to provide abstraction techniques which make it feasible to compute safe over- approximations of this cost. A theorem is proved stating that such abstractions yield correct approximations of the program's long-run cost. The theoretical developments are illustrated on a concrete example taken from the analysis of the cache behaviour of a simple bytecode language.
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00182338
Contributeur : David Cachera <>
Soumis le : vendredi 25 janvier 2008 - 12:14:56
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : vendredi 25 novembre 2016 - 20:48:20

Fichiers

RR-6338.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00182338, version 4

Citation

David Cachera, Thomas Jensen, Arnaud Jobin, Pascal Sotin. Long-Run Cost Analysis by Approximation of Linear Operators over Dioids. [Research Report] RR-6338, INRIA. 2007, pp.35. 〈inria-00182338v4〉

Partager

Métriques

Consultations de la notice

600

Téléchargements de fichiers

109