Effectiveness of abstract interpretation in automatic parallelization: a case study in logic programming

Bueno Carrillo, Francisco and García de la Banda, M. and Hermenegildo, Manuel V. (1999). Effectiveness of abstract interpretation in automatic parallelization: a case study in logic programming. "ACM transactions on programming languages and systems", v. 21 (n. 2); pp. 189-238. ISSN 0164-0925. https://doi.org/10.1145/316686.316688.

Description

Title: Effectiveness of abstract interpretation in automatic parallelization: a case study in logic programming
Author/s:
  • Bueno Carrillo, Francisco
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
Item Type: Article
Título de Revista/Publicación: ACM transactions on programming languages and systems
Date: March 1999
ISSN: 0164-0925
Volume: 21
Subjects:
Freetext Keywords: Abstract interpretation, Automatic parallelization, Data flow analysis, Logic programming, Parallelism, Verificación de programas de ordenador, Programación lógica
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

We report on a detailed study of the application and effectiveness of program analysis based on abstract interpretation to automatic program parallelization. We study the case of parallelizing logic programs using the notion of strict independence. We first propose and prove correct a methodology for the application in the parallelization task of the information inferred by abstract interpretation, using a parametric domain. The methodology is generic in the sense of allowing the use of different analysis domains. A number of well-known approximation domains are then studied and the transformation into the parametric domain defined. The transformation directly illustrates the relevance and applicability of each abstract domain for the application. Both local and global analyzers are then built using these domains and embedded in a complete parallelizing compiler. Then, the performance of the domains in this context is assessed through a number of experiments. A comparatively wide range of aspects is studied, from the resources needed by the analyzers in terms of time and memory to the actual benefits obtained from the information inferred. Such benefits are evaluated both in terms of the characteristics of the parallelized code and of the actual speedups obtained from it. The results show that data flow analysis plays an important role in achieving efficient parallelizations, and that the cost of such analysis can be reasonable even for quite sophisticated abstract domains. Furthermore, the results also offer significant insight into the characteristics of the domains, the demands of the application, and the trade-offs involved.

More information

Item ID: 13733
DC Identifier: http://oa.upm.es/13733/
OAI Identifier: oai:oa.upm.es:13733
DOI: 10.1145/316686.316688
Official URL: http://delivery.acm.org/10.1145/320000/316688/p189-bueno.pdf?ip=138.100.134.165&acc=ACTIVE%20SERVICE&CFID=177630517&CFTOKEN=40186477&__acm__=1350574435_4d630e4a9212f2b7a6f41b90518656d3
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 19 Oct 2012 08:07
Last Modified: 21 Apr 2016 13:04
  • 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