Automatic compile-time parallelization of logic programs for restricted, goal-level, independent and-parallelism.

Muthukumar, Kalyan and Bueno Carrillo, Francisco and García de la Banda, M. and Hermenegildo, Manuel V. (1999). Automatic compile-time parallelization of logic programs for restricted, goal-level, independent and-parallelism.. "Journal of logic programming", v. 38 (n. 2); pp. 165-218. ISSN 1567-8326. https://doi.org/10.1016/S0743-1066(98)10022-5.

Description

Title: Automatic compile-time parallelization of logic programs for restricted, goal-level, independent and-parallelism.
Author/s:
  • Muthukumar, Kalyan
  • Bueno Carrillo, Francisco
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
Item Type: Article
Título de Revista/Publicación: Journal of logic programming
Date: February 1999
ISSN: 1567-8326
Volume: 38
Subjects:
Freetext Keywords: Automatic parallelization, Parallelizing compilers, Conditional dependency graphs, And-parallelism, &-Prolog, paralelización automática, compiladores paralelizantes, gráficos de dependencia condicional.
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 (3MB) | Preview

Abstract

A framework for the automatic parallelization of (constraint) logic programs is proposed and proved correct. Intuitively, the parallelization process replaces conjunctions of literals with parallel expressions. Such expressions trigger at run-time the exploitation of restricted, goal-level, independent and-parallelism. The parallelization process performs two steps. The first one builds a conditional dependency graph (which can be implified using compile-time analysis information), while the second transforms the resulting graph into linear conditional expressions, the parallel expressions of the &-Prolog language. Several heuristic algorithms for the latter ("annotation") process are proposed and proved correct. Algorithms are also given which determine if there is any loss of parallelism in the linearization process with respect to a proposed notion of maximal parallelism. Finally, a system is presented which implements the proposed approach. The performance of the different annotation algorithms is compared experimentally in this system by studying the time spent in parallelization and the effectiveness of the results in terms of speedups.

More information

Item ID: 14266
DC Identifier: http://oa.upm.es/14266/
OAI Identifier: oai:oa.upm.es:14266
DOI: 10.1016/S0743-1066(98)10022-5
Official URL: http://www.sciencedirect.com/science/article/pii/S0743106698100225
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 15 Jan 2013 10:23
Last Modified: 21 Apr 2016 13:50
  • 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