Lower bound cost estimation for logic programs

Debray, S.K.; López García, Pedro; Hermenegildo, Manuel V. y Lin, Nai-Wei (1997). Lower bound cost estimation for logic programs. En: "International Logic Programming Symposium 1997", Oct 12-17 1997, Island N.Y. ISBN 9780262631808.

Descripción

Título: Lower bound cost estimation for logic programs
Autor/es:
  • Debray, S.K.
  • López García, Pedro
  • Hermenegildo, Manuel V.
  • Lin, Nai-Wei
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: International Logic Programming Symposium 1997
Fechas del Evento: Oct 12-17 1997
Lugar del Evento: Island N.Y
Título del Libro: Logic Programming
Fecha: Octubre 1997
ISBN: 9780262631808
Materias:
Palabras Clave Informales: Cost analysis, Lower bound estimation, Granularity control, Parallelism, Análisis de costes, Estimación del límite inferior, Paralelismo.
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
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 (931kB) | Vista Previa

Resumen

It is generally recognized that information about the runtime cost of computations can be useful for a variety of applications, including program transformation, granularity control during parallel execution, and query optimization in deductive databases. Most of the work to date on compile-time cost estimation of logic programs has focused on the estimation of upper bounds on costs. However, in many applications, such as parallel implementations on distributed-memory machines, one would prefer to work with lower bounds instead. The problem with estimating lower bounds is that in general, it is necessary to account for the possibility of failure of head unification, leading to a trivial lower bound of 0. In this paper, we show how, given type and mode information about procedures in a logic program, it is possible to (semi-automatically) derive nontrivial lower bounds on their computational costs. We also discuss the cost analysis for the special and frequent case of divide-and-conquer programs and show how —as a pragmatic short-term solution —it may be possible to obtain useful results simply by identifying and treating divide-and-conquer programs specially.

Más información

ID de Registro: 14401
Identificador DC: http://oa.upm.es/14401/
Identificador OAI: oai:oa.upm.es:14401
URL Oficial: http://mitpress.mit.edu/books/logic-programming
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 03 Feb 2013 10:58
Ultima Modificación: 21 Abr 2016 14:02
  • 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