2020-01-20T16:33:37Z
http://oa.upm.es/cgi/oai2
oai:oa.upm.es:4376
2016-04-20T13:38:02Z
7374617475733D707562
7375626A656374733D74656C65636F6D756E69636163696F6E6573
7375626A656374733D696E666F726D6174696361
747970653D636F6E666572656E63655F6974656D
Efficient Set Sharing Using ZBDDs
Méndez-Lojo, Mario
Lhoták, Ondrej
Hermenegildo, Manuel V.
Telecommunications
Computer Science
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.
Facultad de Informática (UPM)
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
2008
info:eu-repo/semantics/conferenceObject
Presentation at Congress or Conference
Proceedings of 21th international workshop, Languages and compilers for parallel computing, LCPC 2008 | 21th international workshop, Languages and compilers for parallel computing, LCPC 2008 | 31/07/2008-02/08/2008 | Edmonton, Alberta, Canadá
PeerReviewed
application/pdf
eng
http://www.cs.ualberta.ca/lcpc08/
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/altIdentifier/doi/10.1007/978-3-540-89740-8_4
http://oa.upm.es/4376/