Re: data-flow analysis in the presence of threads

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
--

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