Comparing Cost Functions in Resource Analysis

Albert Albiol, Elvira; Arenas Sánchez, Purificación; Genaim, Samir y Puebla Sánchez, Alvaro Germán (2009). Comparing Cost Functions in Resource Analysis. En: "First international conference on Foundational and practical aspects of resource analysis, FOPARA'09", 06/11/2009 - 06/11/2009, Eindhoven, Holanda. ISBN 978-3-642-15330-3.

Descripción

Título: Comparing Cost Functions in Resource Analysis
Autor/es:
  • Albert Albiol, Elvira
  • Arenas Sánchez, Purificación
  • Genaim, Samir
  • Puebla Sánchez, Alvaro Germán
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: First international conference on Foundational and practical aspects of resource analysis, FOPARA'09
Fechas del Evento: 06/11/2009 - 06/11/2009
Lugar del Evento: Eindhoven, Holanda
Título del Libro: Proceedings of the First international conference on Foundational and practical aspects of resource analysis
Fecha: Noviembre 2009
ISBN: 978-3-642-15330-3
Volumen: 6324
Materias:
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (313kB) | Vista Previa

Resumen

Cost functions provide information about the amount of resources required to execute a program in terms of the sizes of input arguments. They can provide an upper-bound, a lower-bound, or the average-case cost. Motivated by the existence of a number of automatic cost analyzers which produce cost functions, we propose an approach for automatically proving that a cost function is smaller than another one. In all applications of resource analysis, such as resource-usage verification, program synthesis and optimization, etc., it is essential to compare cost functions. This allows choosing an implementation with smaller cost or guaranteeing that the given resource-usage bounds are preserved. Unfortunately, automatically generated cost functions for realistic programs tend to be rather intricate, defined by multiple cases, involving non-linear subexpressions (e.g., exponential, polynomial and logarithmic) and they can contain multiple variables, possibly related by means of constraints. Thus, comparing cost functions is far from trivial. Our approach first syntactically transforms functions into simpler forms and then applies a number of su!cient conditions which guarantee that a set of expressions is smaller than another expression. Our preliminary implementation in the COSTA system indicates that the approach can be useful in practice

Más información

ID de Registro: 5710
Identificador DC: http://oa.upm.es/5710/
Identificador OAI: oai:oa.upm.es:5710
URL Oficial: http://www.springerlink.com/content/978-3-642-15330-3#section=776412&page=1&locus=22
Depositado por: Memoria Investigacion
Depositado el: 18 Ene 2011 09:42
Ultima Modificación: 20 Abr 2016 14:26
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM