Identification of Heap-Carried Data Dependence Via Explicit Store Heap Models

Marron, Mark and Stefanovic, Darko and Kapur, Deepak and Hermenegildo, Manuel V. (2008). Identification of Heap-Carried Data Dependence Via Explicit Store Heap Models. In: "21th international workshop, Languages and compilers for parallel computing, LCPC 2008", 31/07/2008-02/08/2008, Edmonton, Alberta, Canadá. ISBN 978-3-540-89739-2.

Description

Title: Identification of Heap-Carried Data Dependence Via Explicit Store Heap Models
Author/s:
  • Marron, Mark
  • Stefanovic, Darko
  • Kapur, Deepak
  • Hermenegildo, Manuel V.
Item Type: Presentation at Congress or Conference (Article)
Event Title: 21th international workshop, Languages and compilers for parallel computing, LCPC 2008
Event Dates: 31/07/2008-02/08/2008
Event Location: Edmonton, Alberta, Canadá
Title of Book: Proceedings of 21th international workshop, Languages and compilers for parallel computing, LCPC 2008
Date: 2008
ISBN: 978-3-540-89739-2
Subjects:
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 (504kB) | Preview

Abstract

Dependence information between program values is extensively used in many program optimization techniques. The ability to identify statements, calls and loop iterations that do not depend on each other enables many transformations which increase the instruction and thread-level parallelism in a program. When program variables contain complex data structures including arrays, records, and recursive data structures, the ability to precisely model data dependence based on heap structure remains a challenging problem. This paper presents a technique for precisely tracking heap based data dependence in non-trivial Java programs via static analysis. Using an abstract interpretation framework, the approach extends a shape analysis technique based on an existing graph model of heaps, by integrating read/write history information and intelligent memorization. The method has been implemented and its effectiveness and utility are demonstrated by computing detailed dependence information for two benchmarks (Em3d and BH from the JOlden suite) and using this information to parallelize the benchmarks.

More information

Item ID: 4374
DC Identifier: http://oa.upm.es/4374/
OAI Identifier: oai:oa.upm.es:4374
Official URL: http://www.cs.ualberta.ca/lcpc08/
Deposited by: Memoria Investigacion
Deposited on: 30 Sep 2010 07:53
Last Modified: 20 Apr 2016 13:37
  • 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