Efficient Set Sharing Using ZBDDs

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

Description

Title: Efficient Set Sharing Using ZBDDs
Author/s:
  • Méndez-Lojo, Mario
  • Lhoták, Ondrej
  • 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 (430kB) | Preview

Abstract

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.

More information

Item ID: 4376
DC Identifier: http://oa.upm.es/4376/
OAI Identifier: oai:oa.upm.es:4376
DOI: 10.1007/978-3-540-89740-8_4
Official URL: http://www.cs.ualberta.ca/lcpc08/
Deposited by: Memoria Investigacion
Deposited on: 29 Sep 2010 11:34
Last Modified: 20 Apr 2016 13:38
  • 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