A simulation study on parallel backtracking with solution memoing for independent and-parallelism

Chico de Guzmán, Pablo; Casas, Amadeo; Carro Liñares, Manuel y Hermenegildo, Manuel V. (2011). A simulation study on parallel backtracking with solution memoing for independent and-parallelism. Monografía (Informe Técnico). Facultad de Informática (UPM) [antigua denominación], Madrid, Spain.

Descripción

Título: A simulation study on parallel backtracking with solution memoing for independent and-parallelism
Autor/es:
  • Chico de Guzmán, Pablo
  • Casas, Amadeo
  • Carro Liñares, Manuel
  • Hermenegildo, Manuel V.
Tipo de Documento: Monográfico (Informes, Documentos de trabajo, etc.) (Informe Técnico)
Fecha: Enero 2011
Materias:
Palabras Clave Informales: Parallelism, Logic programming, Memoization, Backtracking, Simulation, Paralelismo, Programación lógica, Retrocesos, Simulación.
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 (771kB) | Vista Previa

Resumen

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 multiple answers. The most successful IAP implementations to date have used recomputation of answers and sequentially ordered backtracking. While in principle 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 expansion, and still frequently run into the well-known trapped goal and garbage slot problems. This work presents ideas about an alternative parallel backtracking model for IAP and a simulation studio. The model features parallel out-of-order backtracking and relies on answer memoization to reuse and combine answers. Whenever a parallel goal backtracks, its siblings also perform backtracking, but after storing the bindings generated by previous answers. The bindings are then reinstalled when combining answers. In order not to unnecessarily penalize forward execution, non-speculative and-parallel goals which have not been executed yet take precedence over sibling goals which could be backtracked over. Using a simulator, we show that this approach can bring significant performance advantages over classical approaches.

Más información

ID de Registro: 14683
Identificador DC: http://oa.upm.es/14683/
Identificador OAI: oai:oa.upm.es:14683
URL Oficial: http://software.imdea.org/es/research/publications.html
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 22 Mar 2013 07:37
Ultima Modificación: 21 Abr 2016 14:27
  • 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