Comparing Cost Functions in Resource Analysis

Albert Albiol, Elvira and Arenas Sánchez, Purificación and Genaim, Samir and Puebla Sánchez, Alvaro Germán (2009). Comparing Cost Functions in Resource Analysis. In: "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.

Description

Title: Comparing Cost Functions in Resource Analysis
Author/s:
  • Albert Albiol, Elvira
  • Arenas Sánchez, Purificación
  • Genaim, Samir
  • Puebla Sánchez, Alvaro Germán
Item Type: Presentation at Congress or Conference (Article)
Event Title: First international conference on Foundational and practical aspects of resource analysis, FOPARA'09
Event Dates: 06/11/2009 - 06/11/2009
Event Location: Eindhoven, Holanda
Title of Book: Proceedings of the First international conference on Foundational and practical aspects of resource analysis
Date: November 2009
ISBN: 978-3-642-15330-3
Volume: 6324
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Lenguajes y Sistemas Informáticos e Ingeniería del Software
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (313kB) | Preview

Abstract

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

More information

Item ID: 5710
DC Identifier: http://oa.upm.es/5710/
OAI Identifier: oai:oa.upm.es:5710
Official URL: http://www.springerlink.com/content/978-3-642-15330-3#section=776412&page=1&locus=22
Deposited by: Memoria Investigacion
Deposited on: 18 Jan 2011 09:42
Last Modified: 20 Apr 2016 14:26
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM