A segment-swapping approach for executing trapped computations

Chico de Guzmán, Pablo; Casas, Amadeo; Carro Liñares, Manuel y Hermenegildo, Manuel V. (2012). A segment-swapping approach for executing trapped computations. En: "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.

Descripción

Título: A segment-swapping approach for executing trapped computations
Autor/es:
  • Chico de Guzmán, Pablo
  • Casas, Amadeo
  • Carro Liñares, Manuel
  • Hermenegildo, Manuel V.
Editor/es:
  • Russo, Claudio
  • Zhou, Neng-Fa
Tipo de Documento: Sección de Libro
Título del Libro: Practical Aspects of Declarative Languages
Fecha: 2012
ISBN: 978-3-642-27693-4
Materias:
Palabras Clave Informales: Parallelism, Logic programming, Trapped computations, Backtracking, Performance, Paralelismo, Programación lógica, Retroceso, Presentació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 (1MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 14839
Identificador DC: http://oa.upm.es/14839/
Identificador OAI: oai:oa.upm.es:14839
Identificador DOI: 10.1007/978-3-642-27694-1_11
URL Oficial: http://link.springer.com/chapter/10.1007%2F978-3-642-27694-1_11
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 12 Abr 2013 06:29
Ultima Modificación: 21 Abr 2016 14:41
  • 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