Sharing analysis of arrays, collections, and recursive structures

Marron, Mark; Méndez-Lojo, Mario; Hermenegildo, Manuel V.; Stefanovic, Darko y Kapur, Deepak (2008). Sharing analysis of arrays, collections, and recursive structures. En: "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.

Descripción

Título: Sharing analysis of arrays, collections, and recursive structures
Autor/es:
  • Marron, Mark
  • Méndez-Lojo, Mario
  • Hermenegildo, Manuel V.
  • Stefanovic, Darko
  • Kapur, Deepak
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering
Fechas del Evento: November 9-10, 2008
Lugar del Evento: Atlanta, GA, USA
Título del Libro: PASTE '08 Proceedings of the 8th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering
Fecha: 2008
ISBN: 978-1-60558-382-2
Materias:
Palabras Clave Informales: Shape analysis, Shared structures, Parallelism, Análisis de la forma, Estructuras comunes, Paralelismo.
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Inteligencia Artificial
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 (762kB) | Vista Previa

Resumen

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.

Más información

ID de Registro: 14308
Identificador DC: http://oa.upm.es/14308/
Identificador OAI: oai:oa.upm.es:14308
URL Oficial: http://dl.acm.org/citation.cfm?doid=1512475.1512485
Depositado por: Biblioteca Facultad de Informatica
Depositado el: 18 Ene 2013 08:28
Ultima Modificación: 21 Abr 2016 13:54
  • 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