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

Hermenegildo, Manuel V. and 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.

Description

Title: Strict and non-strict independent and-parallelism in logic programs: Correctness, efficiency, and compile-time conditions.
Author/s:
  • Hermenegildo, Manuel V.
  • Rossi, Francesca
Item Type: Article
Título de Revista/Publicación: Journal of logic programming
Date: 1995
ISSN: 1567-8326
Volume: 22
Subjects:
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
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 (2MB) | Preview

Abstract

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.

More information

Item ID: 14300
DC Identifier: http://oa.upm.es/14300/
OAI Identifier: oai:oa.upm.es:14300
DOI: 10.1016/0743-1066(93)00007-F
Official URL: http://www.sciencedirect.com/science/article/pii/074310669300007F
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 17 Jan 2013 07:51
Last Modified: 21 Apr 2016 13:54
  • 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