Parallel backtracking with answer memoing for independent and-parallelism

Chico de Guzmán, Pablo; Casas, Amadeo; Carro Liñares, Manuel y Hermenegildo, Manuel V. (2011). Parallel backtracking with answer memoing for independent and-parallelism. "Theory and practice of logic programming", v. 11 (n. 4-5); pp. 555-574. ISSN 1475-3081.


Título: Parallel backtracking with answer memoing for independent and-parallelism
  • Chico de Guzmán, Pablo
  • Casas, Amadeo
  • Carro Liñares, Manuel
  • Hermenegildo, Manuel V.
Tipo de Documento: Artículo
Título de Revista/Publicación: Theory and practice of logic programming
Fecha: Julio 2011
Volumen: 11
Palabras Clave Informales: Parallelism, Logic programming, Memoization, Backtracking, Performance, Programación lógica,Algoritmos, rendimiento
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB) | Vista Previa


Goal-level Independent and-parallelism (IAP) is exploited by scheduling for simultaneous execution two or more goals which will not interfere with each other at run time. This can be done safely even if such goals can produce múltiple answers. The most successful IAP implementations to date have used recomputation of answers and sequentially ordered backtracking. While in principie simplifying the implementation, recomputation can be very inefficient if the granularity of the parallel goals is large enough and they produce several answers, while sequentially ordered backtracking limits parallelism. And, despite the expected simplification, the implementation of the classic schemes has proved to involve complex engineering, with the consequent difficulty for system maintenance and extensión, while still frequently running into the well-known trapped goal and garbage slot problems. This work presents an alternative parallel backtracking model for IAP and its implementation. The model features parallel out-of-order (i.e., non-chronological) backtracking and relies on answer memoization to reuse and combine answers. We show that this approach can bring significant performance advantages. Also, it can bring some simplification to the important engineering task involved in implementing the backtracking mechanism of previous approaches.

Más información

ID de Registro: 4737
Identificador DC:
Identificador OAI:
Identificador DOI: 10.1017/S1471068411000172
URL Oficial:
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 17 Nov 2012 07:50
Ultima Modificación: 20 Abr 2016 13:50
  • InvestigaM
  • 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
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM