Efficient Set Sharing Using ZBDDs

Méndez-Lojo, Mario; Lhoták, Ondrej y Hermenegildo, Manuel V. (2008). Efficient Set Sharing Using ZBDDs. En: "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. https://doi.org/10.1007/978-3-540-89740-8_4.

Descripción

Título: Efficient Set Sharing Using ZBDDs
Autor/es:
  • Méndez-Lojo, Mario
  • Lhoták, Ondrej
  • Hermenegildo, Manuel V.
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 21th international workshop, Languages and compilers for parallel computing, LCPC 2008
Fechas del Evento: 31/07/2008-02/08/2008
Lugar del Evento: Edmonton, Alberta, Canadá
Título del Libro: Proceedings of 21th international workshop, Languages and compilers for parallel computing, LCPC 2008
Fecha: 2008
ISBN: 978-3-540-89739-2
Materias:
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 (430kB) | Vista Previa

Resumen

Set sharing is an abstract domain in which each concrete object is represented by the set of local variables from which it might be reachable. It is a useful abstraction to detect parallelism opportunities, since it contains definite information about which variables do not share in memory, i.e., about when the memory regions reachable from those variables are disjoint. Set sharing is a more precise alternative to pair sharing, in which each domain element is a set of all pairs of local variables from which a common object may be reachable. However, the exponential complexity of some set sharing operations has limited its wider application. This work introduces an efficient implementation of the set sharing domain using Zero-suppressed Binary Decision Diagrams (ZBDDs). Because ZBDDs were designed to represent sets of combinations (i.e., sets of sets), they naturally represent elements of the set sharing domain. We show how to synthesize the operations needed in the set sharing transfer functions from basic ZBDD operations. For some of the operations, we devise custom ZBDD algorithms that perform better in practice. We also compare our implementation of the abstract domain with an efficient, compact, bit set-based alternative, and show that the ZBDD version scales better in terms of both memory usage and running time.

Más información

ID de Registro: 4376
Identificador DC: http://oa.upm.es/4376/
Identificador OAI: oai:oa.upm.es:4376
Identificador DOI: 10.1007/978-3-540-89740-8_4
URL Oficial: http://www.cs.ualberta.ca/lcpc08/
Depositado por: Memoria Investigacion
Depositado el: 29 Sep 2010 11:34
Ultima Modificación: 20 Abr 2016 13:38
  • 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