Memorias de investigación
Ponencias en congresos:
Efficient Set Sharing Using ZBDDs
Año:2008
Áreas de investigación
  • Lenguaje de programación
Datos
Descripción
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-supressed 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, bitset-based alternative, and show that the ZBDD version scales better in terms of both memory usage and running time.
Internacional
Si
Nombre congreso
Languages and Compilers for Parallel Computing 21th International Workshop, LCPC 2008
Tipo de participación
960
Lugar del congreso
Revisores
Si
ISBN o ISSN
978-3-540-89739-2
DOI
10.1007/978-3-540-89740-8_4
Fecha inicio congreso
31/07/2008
Fecha fin congreso
02/08/2008
Desde la página
47
Hasta la página
63
Título de las actas
Efficient Set Sharing Using ZBDDs
Esta actividad pertenece a memorias de investigación
Participantes
  • Participante: Ondøej Lhoták D. R. Cheriton School of Computer Science, University of Waterloo, Canada
  • Autor: Manuel de Hermenegildo Salinas UPM
  • Participante: Mario Méndez-Lojo Dept. of Computer Science, University of New Mexico, USA
Grupos de investigación, Departamentos, Centros e Institutos de I+D+i relacionados
  • Creador: Grupo de Investigación: Computación lógica, Lenguajes, Implementación y Paralelismo (CLIP)
  • Departamento: Inteligencia Artificial