Parallel Optimization of Parallel Programs

Jens Knoop
Dept. of Computer Science, University of Dortmund, Germany

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

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.

ASTEC seminar
February 27, 2001

Place: Information technology, Uppsala University
Room: 2215 (note new room)
Time: 11.00-12.00

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