Logo der Universität Wien

Probabilistic Data Flow System with Two-Edge Profiling


Traditionally optimization is done statically independent of actual execution environments. For generating highly optimized code, however, runtime information can be used to adapt a program to different environments. In probabilistic data flow systems runtime information on representative input data is exploited to compute the probability with what data flow facts may hold. Probabilistic data flow analysis can guide advanced optimizing transformations in order to improve the running time of programs. In comparison classical data flow analysis does not take runtime information into account. All paths are equally weighted irrespectively whether they are never, heavily, or rarely executed. In this paper we present the best solution what we can theoretically obtain for probabilistic data flow problems and compare it with the state-of-the-art one-edge approach. We show that the differences can be considerable and improvements are crucial. However, the theoretically best solution is too expensive in general and feasible approaches are required. In the sequel we develop an efficient approach which employs two-edge profiling and classical data flow analysis. We show that the results of the two-edge approach are significantly better than the state-of-the-art one-edge approach.

Grafik Top
Grafik Top
Technical Report (Technical Report)
Scientific Computing
Institute for Software Technology and Parallel Systems, University of Vienna
December 1999
Official URL
Grafik Top
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna