Strict and non-strict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions.

Hermenegildo, Manuel V. y Rossi, Francesca (1995). Strict and non-strict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions.. "Journal of logic programming", v. 22 (n. 1); pp. 1-45. ISSN 1567-8326. https://doi.org/10.1016/0743-1066(93)00007-F.

Descripción

Título: Strict and non-strict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions.
Autor/es:
  • Hermenegildo, Manuel V.
  • Rossi, Francesca
Tipo de Documento: Artículo
Título de Revista/Publicación: Journal of logic programming
Fecha: 1995
Volumen: 22
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 (2MB) | Vista Previa

Resumen

This paper presents some fundamental properties of independent and-parallelism and extends its applicability by enlarging the class of goals eligible for parallel execution. A simple model of (independent) and-parallel execution is proposed and issues of correctness and efficiency discussed in the light of this model. Two conditions, "strict" and "non-strict" independence, are defined and then proved sufficient to ensure correctness and efñciency of parallel execution: if goals which meet these conditions are executed in parallel the solutions obtained are the same as those produced by standard sequential execution. Also, in absence of failure, the parallel proof procedure does not genérate any additional work (with respect to standard SLD-resolution) while the actual execution time is reduced. Finally, in case of failure of any of the goals no slow down will occur. For strict independence the results are shown to hold independently of whether the parallel goals execute in the same environment or in sepárate environments. In addition, a formal basis is given for the automatic compile-time generation of independent and-parallelism: compile-time conditions to efficiently check goal independence at run-time are proposed and proved sufficient. Also, rules are given for constructing simpler conditions if information regarding the binding context of the goals to be executed in parallel is available to the compiler.

Más información

ID de Registro: 14300
Identificador DC: http://oa.upm.es/14300/
Identificador OAI: oai:oa.upm.es:14300
Identificador DOI: 10.1016/0743-1066(93)00007-F
URL Oficial: http://www.sciencedirect.com/science/article/pii/074310669300007F
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 17 Ene 2013 07:51
Ultima Modificación: 21 Abr 2016 13:54
  • 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