A segment-swapping approach for executing trapped computations

Chico de Guzmán, Pablo and Casas, Amadeo and Carro Liñares, Manuel and Hermenegildo, Manuel V. (2012). A segment-swapping approach for executing trapped computations. In: "Practical Aspects of Declarative Languages". Lecture Notes in Computer Science (7149). Springer Berlin Heidelberg, Heidelberg, Alemania, pp. 138-152. ISBN 978-3-642-27693-4. https://doi.org/10.1007/978-3-642-27694-1_11.

Description

Title: A segment-swapping approach for executing trapped computations
Author/s:
  • Chico de Guzmán, Pablo
  • Casas, Amadeo
  • Carro Liñares, Manuel
  • Hermenegildo, Manuel V.
Editor/s:
  • Russo, Claudio
  • Zhou, Neng-Fa
Item Type: Book Section
Title of Book: Practical Aspects of Declarative Languages
Date: 2012
ISBN: 978-3-642-27693-4
Subjects:
Freetext Keywords: Parallelism, Logic programming, Trapped computations, Backtracking, Performance, Paralelismo, Programación lógica, Retroceso, Presentació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 (1MB) | Preview

Abstract

We consider the problem of supporting goal-level, independent andparallelism (IAP) in the presence of non-determinism. IAP is exploited when two or more goals which will not interfere at run time are scheduled for simultaneous execution. Backtracking over non-deterministic parallel goals runs into the wellknown trapped goal and garbage slot problems. The proposed solutions for these problems generally require complex low-level machinery which makes systems difficult to maintain and extend, and in some cases can even affect sequential execution performance. In this paper we propose a novel solution to the problem of trapped nondeterministic goals and garbage slots which is based on a single stack reordering operation and offers several advantages over previous proposals. While the implementation of this operation itself is not simple, in return it does not impose constraints on the scheduler. As a result, the scheduler and the rest of the run-time machinery can safely ignore the trapped goal and garbage slot problems and their implementation is greatly simplified. Also, standard sequential execution remains unaffected. In addition to describing the solution we report on an implementation and provide performance results. We also suggest other possible applications of the proposed approach beyond parallel execution.

More information

Item ID: 14839
DC Identifier: http://oa.upm.es/14839/
OAI Identifier: oai:oa.upm.es:14839
DOI: 10.1007/978-3-642-27694-1_11
Official URL: http://link.springer.com/chapter/10.1007%2F978-3-642-27694-1_11
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 12 Apr 2013 06:29
Last Modified: 21 Apr 2016 14:41
  • 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