On the correctness and efficiency of independent and-parallelism in logic programs

Hermenegildo, Manuel V. y Rossi, Francesca (1989). On the correctness and efficiency of independent and-parallelism in logic programs. En: "1989 north american conference in logic programming", October 16-20, 1989, Cleveland, Ohio. ISBN 0262620642.

Descripción

Título: On the correctness and efficiency of independent and-parallelism in logic programs
Autor/es:
  • Hermenegildo, Manuel V.
  • Rossi, Francesca
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 1989 north american conference in logic programming
Fechas del Evento: October 16-20, 1989
Lugar del Evento: Cleveland, Ohio
Título del Libro: Logic Programming, Proceedings of the North American Conference 1989
Fecha: Octubre 1989
ISBN: 0262620642
Materias:
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 (1MB) | Vista Previa

Resumen

This paper presents and proves some fundamental results for independent and-parallelism (IAP). First, the paper treats the issues of correctness and efficiency: after defining strict and non-strict goal independence, it is proved that if strictly independent goals are executed in parallel the solutions obtained are the same as those produced by standard sequential execution. It is also shown that, in the absence of failure, the parallel proof procedure doesn't genérate any additional work (with respect to standard SLDresolution) while the actual execution time is reduced. The same results hold even if non-strictly independent goals are executed in parallel, provided a trivial rewriting of such goals is performed. In addition, and most importantly, treats the issue of compile-time generation of IAP by proposing conditions, to be written at compile-time, to efficiently check strict and non-strict goal independence at run-time and proving the sufficiency of such conditions. It is also shown how simpler conditions can be constructed if some information regarding the binding context of the goals to be executed in parallel is available to the compiler trough either local or program-level analysis. These results therefore provide a formal basis for the automatic compile-time generation of IAP. As a corollary of such results, the paper also proves that negative goals are always non-strictly independent, and that goals which share a first occurrence of an existential variable are never independent.

Más información

ID de Registro: 14498
Identificador DC: http://oa.upm.es/14498/
Identificador OAI: oai:oa.upm.es:14498
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 15 Feb 2013 07:48
Ultima Modificación: 21 Abr 2016 14:12
  • GEO_UP4
  • 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
  • InvestigaM
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM