Sharing analysis of arrays, collections, and recursive structures

Marron, Mark and Méndez-Lojo, Mario and Hermenegildo, Manuel V. and Stefanovic, Darko and Kapur, Deepak (2008). Sharing analysis of arrays, collections, and recursive structures. In: "8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering", November 9-10, 2008, Atlanta, GA, USA. ISBN 978-1-60558-382-2.

Description

Title: Sharing analysis of arrays, collections, and recursive structures
Author/s:
  • Marron, Mark
  • Méndez-Lojo, Mario
  • Hermenegildo, Manuel V.
  • Stefanovic, Darko
  • Kapur, Deepak
Item Type: Presentation at Congress or Conference (Article)
Event Title: 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering
Event Dates: November 9-10, 2008
Event Location: Atlanta, GA, USA
Title of Book: PASTE '08 Proceedings of the 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering
Date: 2008
ISBN: 978-1-60558-382-2
Subjects:
Freetext Keywords: Shape analysis, Shared structures, Parallelism, Análisis de la forma, Estructuras comunes, Paralelismo.
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 (762kB) | Preview

Abstract

Precise modeling of the program heap is fundamental for understanding the behavior of a program, and is thus of signiflcant interest for many optimization applications. One of the fundamental properties of the heap that can be used in a range of optimization techniques is the sharing relationships between the elements in an array or collection. If an analysis can determine that the memory locations pointed to by different entries of an array (or collection) are disjoint, then in many cases loops that traverse the array can be vectorized or transformed into a thread-parallel versión. This paper introduces several novel sharing properties over the concrete heap and corresponding abstractions to represent them. In conjunction with an existing shape analysis technique, these abstractions allow us to precisely resolve the sharing relations in a wide range of heap structures (arrays, collections, recursive data structures, composite heap structures) in a computationally efflcient manner. The effectiveness of the approach is evaluated on a set of challenge problems from the JOlden and SPECjvm98 suites. Sharing information obtained from the analysis is used to achieve substantial thread-level parallel speedups.

More information

Item ID: 14308
DC Identifier: http://oa.upm.es/14308/
OAI Identifier: oai:oa.upm.es:14308
Official URL: http://dl.acm.org/citation.cfm?doid=1512475.1512485
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 18 Jan 2013 08:28
Last Modified: 21 Apr 2016 13:54
  • 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