Long-Run Cost Analysis by Approximation of Linear Operators over DioidsReport as inadecuate




Long-Run Cost Analysis by Approximation of Linear Operators over Dioids - Download this document for free, or read online. Document in PDF available to download.

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.





Author: David Cachera - Thomas Jensen - Arnaud Jobin - Pascal Sotin -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents