|
Research |
Institut für Computersprachen E185/1 | ||
|
Home Research Embedded Systems PBQP PDFA Symbolic Analysis |
Profile Guided OptimizationsTraditional compilers optimize programs without considering actual execution runs of programs. Without knowing the runtime behavior compilers cannot distinguish between rarely, heavily or never executed program paths. This deficiency leads to inefficient code. In a classical optimization a program analysis guids a transformation, which modifies the program in order to optimize it. Many optimizations use data flow analysis frameworks for their analysis. However, classical data flow analysis does not take runtime information into account for distinguishing between frequently and rarely executed branches -- all paths are equally weighted for the solution (e.g. meet over all path solution or maximum fix point solution). The solution of classical data flow information is whether a data flow fact does or does not hold at a program point. To overcome the problems of classical data flow analysis we work on
new program analysis techniques called Probabilistic Data Flow
Analysis (PDFA) which utilize profile information. In contrast to
classical data flow systems, solutions of PDFA give either the frequency
or the probability of a data flow fact at a program point.
Sophisticated transformations can utilize this detailed solution for
generating highly efficient code. For changing program inputs the target
code is adapted by re-compiling the code with new profile information. The figure below depicts a probabilistic optimization framework for a compiler with a profiling feedback loop. The profiler is responsible for producing profile information based on the execution environment. This information is passed over to the probabilistic optimizer. Control-flow analysis constructs the control-flow graph annotated with edge probabilities. Based on the annotated control-flow graph and on data-flow equations, probabilistic data-flow analysis computes a probabilistic solution of the data-flow problem. Based on the analysis information the transformation is performed. This work is a collaboration with Aurora, a special research program funded by the Austrian Science Fund and Prof. E. Mehofer. References[7] Predicated Partial Redundancy Elimination with Cost Analysis. B. Scholz, E. Mehofer, and N. Horspool. Parallel Processing Letters (Ed. H. Kosch), World Scientific, Vol. 13(4), pp. ??-??, 2003. [pdf][6] Partial Redundancy Elimination with Predication Techniques. B. Scholz, E. Mehofer, and N. Horspool. In Proc. of International Conference on Parallel and Distributed Computing (EuroPar'03), Lecture Notes in Computer Science (LNCS), Vol. 2790, pp. 242-250, Springer Press, Klagenfurt, Austria, August 2003. [pdf] [5] Dataflow Frequency Analysis based on Whole Program Paths. B. Scholz and E. Mehofer. In Parallel Architectures and Compilation Techniques (PACT'02), pp. 95-103, IEEE Press, Charlottesville, Virginia, USA, September 2002. [ps.gz] [4] A Novel Probabilistic Data-Flow Framework. E. Mehofer and B. Scholz. In Proc. of International Conference on Compiler Construction (CC'01), Lecture Notes in Computer Science (LNCS), Vol. 2027, pp. 37-51, Springer Press, Genova, Italy, April 2001. [ps.gz] [3] Probabilistic communication optimizations and parallelization for distributed-memory systems. E. Mehofer and B. Scholz. In Proc. of 9th Euromicro Workshop on Parallel and Distributed Processing (PDP'01), pp. 186-192, IEEE Press, Mantova, Italy, February 2001. [ps.gz] [2] Probabilistic Procedure Cloning for High-Performance Systems. S. Benkner, E. Mehofer, and B. Scholz. In Proc. of 12th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'2000), pp. 105-111, Sao Pedro, Brazil, October 2000. [ps.gz] [1] Probabilistic Data Flow System with Two-Edge Profiling. E. Mehofer and B. Scholz. In Proc. of Workshop on Dynamic and Adaptive Compilation and Optimization (Dynamo'00), ACM SIGPLAN Notices, Vol. 35(7), pp. 65 - 72, ACM Press, Boston, Massachusetts, January 2000. [ps.gz] |
|||
|
||||