24 Dec 1996 22:13:05 -0500

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

From: | Juergen Vollmer <vollmer@pop-karlsruhe.com> |

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.