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

Cabeza Gras, Daniel and 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.

Description

Title: Non-Strict Independence-Based Program Parallelization Using Sharing and Freeness Information.
Author/s:
  • Cabeza Gras, Daniel
  • Hermenegildo, Manuel V.
Item Type: Article
Título de Revista/Publicación: Theoretical Computer Science
Date: November 2009
Volume: 410
Subjects:
Freetext Keywords: Parallelism; Automatic parallelization; Abstract interpretation; Abstract domains; Sharing and freeness; Non-strict independence; Parallelizing compilers; Declarative languages; Logic programming
Faculty: Facultad de Informática (UPM)
Department: Lenguajes y Sistemas Informáticos e Ingeniería del Software
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 (924kB) | Preview

Abstract

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.

More information

Item ID: 5368
DC Identifier: http://oa.upm.es/5368/
OAI Identifier: oai:oa.upm.es:5368
DOI: 10.1016/j.tcs.2009.07.044
Official URL: http://www.sciencedirect.com/science/journal/03043975
Deposited by: Memoria Investigacion
Deposited on: 03 Dec 2010 12:18
Last Modified: 20 Apr 2016 14:11
  • 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