Non-Strict Independence-Based Program Parallelization Using Sharing and Freeness Information.

Cabeza Gras, Daniel y Hermenegildo, Manuel V. (2009). Non-Strict Independence-Based Program Parallelization Using Sharing and Freeness Information.. "Theoretical Computer Science", v. 410 (n. 46); pp. 4704-4723. ISSN 0304-3975. https://doi.org/10.1016/j.tcs.2009.07.044.

Descripción

Título: Non-Strict Independence-Based Program Parallelization Using Sharing and Freeness Information.
Autor/es:
  • Cabeza Gras, Daniel
  • Hermenegildo, Manuel V.
Tipo de Documento: Artículo
Título de Revista/Publicación: Theoretical Computer Science
Fecha: Noviembre 2009
Volumen: 410
Materias:
Palabras Clave Informales: Parallelism; Automatic parallelization; Abstract interpretation; Abstract domains; Sharing and freeness; Non-strict independence; Parallelizing compilers; Declarative languages; Logic programming
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Lenguajes y Sistemas Informáticos e Ingeniería del Software
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 (924kB) | Vista Previa

Resumen

The current ubiquity of multi-core processors has brought renewed interest in program parallelization. Logic programs allow studying the parallelization of programs with complex, dynamic data structures with (declarative) pointers in a comparatively simple semantic setting. In this context, automatic parallelizers which exploit and-parallelism rely on notions of independence in order to ensure certain efficiency properties. “Non-strict” independence is a more relaxed notion than the traditional notion of “strict” independence which still ensures the relevant efficiency properties and can allow considerable more parallelism. Non-strict independence cannot be determined solely at run-time (“a priori”) and thus global analysis is a requirement. However, extracting non-strict independence information from available analyses and domains is non-trivial. This paper provides on one hand an extended presentation of our classic techniques for compile-time detection of non-strict independence based on extracting information from (abstract interpretation-based) analyses using the now well understood and popular Sharing + Freeness domain. This includes algorithms for combined compile-time/run-time detection which involve special run-time checks for this type of parallelism. In addition, we propose herein novel annotation (parallelization) algorithms, URLP and CRLP, which are specially suited to non-strict independence. We also propose new ways of using the Sharing + Freeness information to optimize how the run-time environments of goals are kept apart during parallel execution. Finally, we also describe the implementation of these techniques in our parallelizing compiler and recall some early performance results. We provide as well an extended description of our pictorial representation of sharing and freeness information.

Más información

ID de Registro: 5368
Identificador DC: http://oa.upm.es/5368/
Identificador OAI: oai:oa.upm.es:5368
Identificador DOI: 10.1016/j.tcs.2009.07.044
URL Oficial: http://www.sciencedirect.com/science/journal/03043975
Depositado por: Memoria Investigacion
Depositado el: 03 Dic 2010 12:18
Ultima Modificación: 20 Abr 2016 14:11
  • 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