Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming

Hermenegildo, Manuel V. (2000). Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming. "Parallel computing", v. 26 (n. 13-14); pp. 1685-1708. ISSN 0167-8191. https://doi.org/10.1016/S0167-8191(00)00051-X.

Description

Title: Parallelizing irregular and pointer-based computations automatically: perspectives from logic and constraint programming
Author/s:
  • Hermenegildo, Manuel V.
Item Type: Article
Título de Revista/Publicación: Parallel computing
Date: 2000
ISSN: 0167-8191
Volume: 26
Subjects:
Freetext Keywords: Cost analysis, Pointer aliasing analysis, Granularity control, Irregular computations, Automatic parallelization
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

Irregular computations pose sorne of the most interesting and challenging problems in automatic parallelization. Irregularity appears in certain kinds of numerical problems and is pervasive in symbolic applications. Such computations often use dynamic data structures, which make heavy use of pointers. This complicates all the steps of a parallelizing compiler, from independence detection to task partitioning and placement. Starting in the mid 80s there has been significant progress in the development of parallelizing compilers for logic pro­gramming (and more recently, constraint programming) resulting in quite capable paralle­lizers. The typical applications of these paradigms frequently involve irregular computations, and make heavy use of dynamic data structures with pointers, since logical variables represent in practice a well-behaved form of pointers. This arguably makes the techniques used in these compilers potentially interesting. In this paper, we introduce in a tutoríal way, sorne of the problems faced by parallelizing compilers for logic and constraint programs and provide pointers to sorne of the significant progress made in the area. In particular, this work has resulted in a series of achievements in the areas of inter-procedural pointer aliasing analysis for independence detection, cost models and cost analysis, cactus-stack memory management, techniques for managing speculative and irregular computations through task granularity control and dynamic task allocation such as work-stealing schedulers), etc.

More information

Item ID: 13286
DC Identifier: http://oa.upm.es/13286/
OAI Identifier: oai:oa.upm.es:13286
DOI: 10.1016/S0167-8191(00)00051-X
Official URL: http://www.sciencedirect.com/science/article/pii/S016781910000051X
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 25 Sep 2012 06:54
Last Modified: 21 Apr 2016 12:36
  • 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