Parallel execution of Prolog programs: a survey

Ali, Khayri A.M. and Carlsson, Mats and Gupta, Gopal and Hermenegildo, Manuel V. and Pontelli, Enrico (2001). Parallel execution of Prolog programs: a survey. "ACM transactions on programming languages and systems", v. 23 (n. 4); pp. 472-602. ISSN 0164-0925.


Title: Parallel execution of Prolog programs: a survey
  • Ali, Khayri A.M.
  • Carlsson, Mats
  • Gupta, Gopal
  • Hermenegildo, Manuel V.
  • Pontelli, Enrico
Item Type: Article
Título de Revista/Publicación: ACM transactions on programming languages and systems
Date: 2001
ISSN: 0164-0925
Volume: 23
Freetext Keywords: Automatic parallelization, constraint programming, logic programming, parallelism, prolog, paralelización automática, programación restringida, programación lógica
Faculty: Facultad de Informática (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (9MB) | Preview


Since the early days of logic programming, researchers in the field realized the potential for exploitation of parallelism present in the execution of logic programs. Their high-level nature, the presence of nondeterminism, and their referential transparency, among other characteristics, make logic programs interesting candidates for obtaining speedups through parallel execution. At the same time, the fact that the typical applications of logic programming frequently involve irregular computations, make heavy use of dynamic data structures with logical variables, and involve search and speculation, makes the techniques used in the corresponding parallelizing compilers and run-time systems potentially interesting even outside the field. The objective of this article is to provide a comprehensive survey of the issues arising in parallel execution of logic programming languages along with the most relevant approaches explored to date in the field. Focus is mostly given to the challenges emerging from the parallel execution of Prolog programs. The article describes the major techniques used for shared memory implementation of Or-parallelism, And-parallelism, and combinations of the two. We also explore some related issues, such as memory management, compile-time analysis, and execution visualization.

More information

Item ID: 11160
DC Identifier:
OAI Identifier:
DOI: 10.1145/504083.504085
Official URL:
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 19 Sep 2012 11:01
Last Modified: 20 Apr 2016 19:19
  • 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