Parallel Optimization of Parallel Programs
Dept. of Computer Science,
University of Dortmund,
In comparison to automatic parallelization, classical optimization of
parallel programs attracted so far only little attention. This may be
due the fact that naive adaptations of sequential techniques typically
fail, and the costs of rigoros, correct adaptations are unacceptably
high because of the combinatorial explosion of the state space which
is characterized by the number of interleavings.
In this talk, however, we show that specific problem classes including
the practically most important class of GEN/KILL-problems are an
exception. They can be solved (1) as easily and efficiently as in the
sequential setting, and (2) posses naturally parallelizable
Central for these surprising results is concerning (1) the strict
separation of interference information, and its usage for solving the
considered problem, and concerning (2) the complementation of the
convential data-flow analysis (DFA) approach by an approach for
demand-driven DFA based on reverse DFA. Together this yields the key
for constructing interactive tools like debuggers as well as parallel
versions of conventional and ``hot spot'' optimizers. We demonstrate
this in detail for the class of GEN/KILL-problems, and discuss
extensions as well as limitations of the overall approach.
Place: Information technology, Uppsala University
Room 1406 is in Building 2, Floor 2, room 15
(in the southern part of the building).
Help on how to find ASTEC Seminars.
Everyone is welcome !
Updated 21-Feb-2001 08:55 by Roland Grönroos
e-mail: info -at- astec.uu.se