Towards extracting non-strict independent and-parallelism using sharing and freeness information

Cabeza Gras, Daniel and Hermenegildo, Manuel V. (1993). Towards extracting non-strict independent and-parallelism using sharing and freeness information. Monografía (Technical Report). Facultad de Informática (UPM), Madrid, Spain.

Description

Title: Towards extracting non-strict independent and-parallelism using sharing and freeness information
Author/s:
  • Cabeza Gras, Daniel
  • Hermenegildo, Manuel V.
Item Type: Monograph (Technical Report)
Date: April 1993
Subjects:
Freetext Keywords: Parallel execution of logic programs, Generation of annotations for parallelism, Abstract interpretation, Non-strictly independent and-parallelism, Ejecución paralela de programación lógica, Generación de notas para paralelismos, Interpretación abstracta.
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

Logic programming systems which exploit and-parallelism among non-deterministic goals rely on notions of independence among those goals in order to ensure certain efficiency properties. "Non-strict" independence (NSI) is a more relaxed notion than the traditional notion of "strict" independence (SI) which still ensures the relevant efficiency properties and can allow considerable more parallelism than SI. However, all compilation technology developed to date has been based on SI, presumably because of the intrinsic complexity of exploiting NSI. This is related to the fact that NSI cannot be determined "a priori" as SI. This paper fills this gap by developing a technique for compile-time detection and annotation of NSI. It also proposes algorithms for combined compile- time/run-time detection, presenting novel run-time checks for this type of parallelism. Also, a transformation procedure to eliminate shared variables among parallel goals is presented, attempting to perform as much work as possible at compiletime. The approach is based on the knowledge of certain properties about run-time instantiations of program variables —sharing and freeness— for which compile-time technology is available, with new approaches being currently proposed.

More information

Item ID: 15224
DC Identifier: http://oa.upm.es/15224/
OAI Identifier: oai:oa.upm.es:15224
Official URL: ftp://clip.dia.fi.upm.es/pub/papers/PARFORCE/
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 10 May 2013 06:19
Last Modified: 21 Apr 2016 15:15
  • 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