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

Bueno Carrillo, Francisco; García de la Banda, M. y 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.

Descripción

Título: Effectiveness of abstract interpretation in automatic parallelization: a case study in logic programming
Autor/es:
  • Bueno Carrillo, Francisco
  • García de la Banda, M.
  • Hermenegildo, Manuel V.
Tipo de Documento: Artículo
Título de Revista/Publicación: ACM transactions on programming languages and systems
Fecha: Marzo 1999
Volumen: 21
Materias:
Palabras Clave Informales: Abstract interpretation, Automatic parallelization, Data flow analysis, Logic programming, Parallelism, Verificación de programas de ordenador, Programación lógica
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 (3MB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 13733
Identificador DC: http://oa.upm.es/13733/
Identificador OAI: oai:oa.upm.es:13733
Identificador DOI: 10.1145/316686.316688
URL Oficial: 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
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 19 Oct 2012 08:07
Ultima Modificación: 21 Abr 2016 13:04
  • 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