KIT | KIT-Bibliothek | Impressum | Datenschutz

Data flow analysis of parallel programs

Vollmer, Jürgen


Data flow analysis is the prerequisite of performing optimizations
such as common subexpression eliminations or 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
source language features are: common address space (shared memory),
nested parallel statements (PAR),or-parallelism, critical regions
and message passing. 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 one-bit data flow problems (also known as
bit-vector problems) we can show that for the computation of the
meet over all path solution, not all interleavings are needed.
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
... mehr

Volltext §
DOI: 10.5445/IR/34695
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Programmstrukturen und Datenorganisation (IPD)
Publikationstyp Buch
Publikationsjahr 1995
Sprache Englisch
Identifikator urn:nbn:de:swb:90-AAA346956
KITopen-ID: 34695
Erscheinungsvermerk Karlsruhe 1995. (Interner Bericht. Fakultät für Informatik, Universität Karlsruhe. 1995,19.)
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page