MINDS @ UW-Madison

Solving Multiple Dataflow Queries Using WPDSs

Show full item record

File(s):

Author(s)
Lal, Akash; Reps, Thomas
Publisher
University of Wisconsin-Madison Department of Computer Sciences
Citation
TR1632
Date
2008
Abstract
A dataflow query asks for the set of reachable (abstract) states, given a starting set of states. In this paper, we show how to optimize multiple queries on the same program (each with a different starting set of states) for better overall running time. After a preprocessing phase, we obtain an asymptotic improvement in answering dataflow queries. We use weighted pushdown systems as the abstract model of a program. Our techniques are interprocedural. They are general, yet provide an impressive speedup. We applied our algorithm to three very different applications, one based on finding affine relations using linear algebra, and others for model checking Boolean programs, and obtained 1.5-fold to 7-fold speedups.
Permanent link
http://digital.library.wisc.edu/1793/60628 
Export
Export to RefWorks 
‚Äč

Part of

Show full item record

Search and browse




About MINDS@UW

Deposit materials

  1. Register to deposit in MINDS@UW
  2. Need deposit privileges? Contact us.
  3. Already registered? Have deposit privileges? Deposit materials.