Independence in CLP Languages

García de la Banda, M.; Hermenegildo, Manuel V. y Marriott, K. (2000). Independence in CLP Languages. "ACM transactions on programming languages and systems", v. 22 (n. 2); pp. 269-339. ISSN 0164-0925. https://doi.org/10.1145/349214.349224.

Descripción

Título: Independence in CLP Languages
Autor/es:
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
  • Marriott, K.
Tipo de Documento: Artículo
Título de Revista/Publicación: ACM transactions on programming languages and systems
Fecha: Marzo 2000
Volumen: 22
Materias:
Palabras Clave Informales: Constraint logic programming, Independence, Parallelism, Programación lógica de restricciones, Paralelismo
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 (2MB) | Vista Previa

Resumen

Studying independence of goals has proven very useful in the context of logic programming. In particular, it has provided a formal basis for powerful automatic parallelization tools, since independence ensures that two goals may be evaluated in parallel while preserving correctness and eciency. We extend the concept of independence to constraint logic programs (CLP) and prove that it also ensures the correctness and eciency of the parallel evaluation of independent goals. Independence for CLP languages is more complex than for logic programming as search space preservation is necessary but no longer sucient for ensuring correctness and eciency. Two additional issues arise. The rst is that the cost of constraint solving may depend upon the order constraints are encountered. The second is the need to handle dynamic scheduling. We clarify these issues by proposing various types of search independence and constraint solver independence, and show how they can be combined to allow dierent optimizations, from parallelism to intelligent backtracking. Sucient conditions for independence which can be evaluated \a priori" at run-time are also proposed. Our study also yields new insights into independence in logic programming languages. In particular, we show that search space preservation is not only a sucient but also a necessary condition for ensuring correctness and eciency of parallel execution.

Más información

ID de Registro: 13471
Identificador DC: http://oa.upm.es/13471/
Identificador OAI: oai:oa.upm.es:13471
Identificador DOI: 10.1145/349214.349224
URL Oficial: http://dl.acm.org/citation.cfm?id=349214&CFID=167368878&CFTOKEN=84858823
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 03 Oct 2012 06:42
Ultima Modificación: 21 Abr 2016 12:47
  • 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