# Re: data-flow analysis in the presence of threads

## Juergen Vollmer <vollmer@pop-karlsruhe.com>24 Dec 1996 22:13:05 -0500

From comp.compilers

Related articles
Threads and Data-Flow Analysis collberg@cs.auckland.ac.nz (1996-12-21)
Re: data-flow analysis in the presence of threads vollmer@pop-karlsruhe.com (Juergen Vollmer) (1996-12-24)
| List of all articles for this month |

 From: Juergen Vollmer Newsgroups: comp.compilers Date: 24 Dec 1996 22:13:05 -0500 Organization: Compilers Central References: 96-12-155 Keywords: analysis, parallel, bibliography

collberg@cs.auckland.ac.nz (Christian Collberg) writes:
> I'm looking for information on
> algorithms for data-flow analysis in the presence of threads. Such
> algorithms would have to model all the possible states each
> process could be in as well as race-conditions, etc. I'd
> appreciate pointers to any work in this area.

I have done my PhD (in german) in this area. From an abstract of one of
the papers:

Data flow analysis is the prerequisite of performing optimizations
such as code motion of partial redundant expressions on
imperative sequential programs. To apply these transformations to
parallel imperative programs, the notion of data flow must be extended
to concurrent programs. The additional parallel source language
features are: shared memory and nested parallel statements (PAR).
The underlying interleaving semantics of the concurrently-executed
processes result in the so-called state space explosion which on first
appearance prevents the computation of the meet over all path solution
needed for data flow analysis.

For the class of bit-vector data flow problems we can
show that for the computation of the meet over all path solution,
no interleavings are needed be considered! Based on that, we can give
simple data flow equations representing the data flow effects of the
PAR statement.
The definition of a parallel control flow graph leads to an efficient
extension of Killdal's algorithm to compute the data flow of a concurrent
program. The time complexity is the same as for analyzing a comparable''
sequential program.

Here are references to some of the papaers.

With best regards
Juergen Vollmer

@ARTICLE{vollmer.96a,
AUTHOR = "Knoop, Jens AND
Steffen, Bernhard AND
Vollmer, {J\"{u}rgen}",
TITLE = "Parallelism for Free: Efficient and Optimal Bitvector
Analyses for Parallel Programs",
JOURNAL = toplas,
YEAR = 1996
MONTH = may,
}

@INPROCEEDINGS{vollmer.95b,
AUTHOR = "Vollmer, {J\"{u}rgen}",
TITLE = "Data Flow Analysis of Parallel Programs",
BOOKTITLE = "Proceedings of the IFIP WG 10.3 Working Conference on
{\em Parallel Architectures and Compilation Techniques},
PACT'95, Limassol, Cyprus",
YEAR = 1995,
MONTH = jun,
PAGES = "168--177",
LOCATION = "jv",
URL = "http://i44www.info.uni-karlsruhe.de/\~{}vollmer/papers/dfapp-pact-95.ps.
gz",
}

@INPROCEEDINGS{vollmer.95c,
AUTHOR = "Knoop, Jens AND
Steffen, Bernhard AND
Vollmer, {J\"{u}rgen}",
TITLE = "Parallelism for free: Bitvector analyses $\rightarrow$ No
state
explosion!",
CROSSREF = "lncs.1019",
PAGES = "264 -- 289",
}

@TECHREPORT{vollmer.95g,
AUTHOR = "Knoop, Jens AND
Steffen, Bernhard AND
Vollmer, {J\"{u}rgen}",
TITLE = "Optimal Code Motion for Parallel Programs",
INSTITUTION = "{Universit\"{a}t Passau, Fakult\"{a}t f\"{u}r Mathematik und
Informatik}",
NUMBER = "MIP-9511",
YEAR = 1995,
MONTH = sep,
}
------------------------------------------------------------------------------
Juergen Vollmer, Viktoriastrasse 15, D-76133 Karlsruhe, Tel&Fax: +49(721)24874
Juergen.Vollmer@pop-karlsruhe.com http://www.pop-karlsruhe.com/vollmer
Juergen.Vollmer@acm.org
--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.