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

Chico de Guzmán, Pablo and Casas, Amadeo and Carro Liñares, Manuel and Hermenegildo, Manuel V. (2011). A simulation study on parallel backtracking with solution memoing for independent and-parallelism. Monografía (Technical Report). Facultad de Informática (UPM), Madrid, Spain.

Description

Title: A simulation study on parallel backtracking with solution memoing for independent and-parallelism
Author/s:
  • Chico de Guzmán, Pablo
  • Casas, Amadeo
  • Carro Liñares, Manuel
  • Hermenegildo, Manuel V.
Item Type: Monograph (Technical Report)
Date: January 2011
Subjects:
Freetext Keywords: Parallelism, Logic programming, Memoization, Backtracking, Simulation, Paralelismo, Programación lógica, Retrocesos, Simulación.
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 (771kB) | Preview

Abstract

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.

More information

Item ID: 14683
DC Identifier: http://oa.upm.es/14683/
OAI Identifier: oai:oa.upm.es:14683
Official URL: http://software.imdea.org/es/research/publications.html
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 22 Mar 2013 07:37
Last Modified: 21 Apr 2016 14:27
  • 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