|
Research |
Institut für Computersprachen E185/1 | ||
|
Home Research Embedded Systems PBQP PDFA Symbolic Analysis |
Symbolic Analysis of Programs
The aim of this work is to develop an effective and unified symbolic analysis framework for parallelizing compilers and other software validation tools. Symbolic analysis uses symbolic expressions to describe the computations as algebraic formulas over a program's problem size. A new representation of symbolic analysis information called program context is introduced, which is a comprehensive and compact control and data flow analysis information. The symbolic evaluation techniques comprise accurate modeling of assignment and input/output statements, branches, loops, recurrences, arrays and procedures. All of the techniques target both linear as well as non-linear expressions and constraints. Efficiency of symbolic evaluation is highly improved by aggressive simplification techniques. Symbolic analysis has been applied for a parallelizing HPF compiler, e.g. dependence analysis, array-privatization, communication vectorization and elimination of redundant communication. In addition, some software validation techniques based on symbolic analysis has been investigated, e.g. dead lock detections, memory leak detection, and cache analysis. This work is a collaboration with Aurora, a special
research program funded by the Austrian Science Fund, Prof. T. Fahringer, Prof. H. Blieberger,
and B. Burgstaller. References[7] Advanced Symbolic Analysis for Compilers. T. Fahringer and B. Scholz. State-of-the-Art Survey, Lecture Notes in Computer Science (LNCS), Vol. 2628, Springer Press, 2003.[6] Symbolic Cache Analysis for Real-Time Systems. J. Blieberger, T.Fahringer, and B. Scholz. Real-Time Systems, Special Issue on Worst-Case Execution Time Analysis, Kluwer Press, Vol. 18(2/3), pp. 181-215, 2000. [ps.gz] [5] A Unified Symbolic Evaluation Framework for Parallelizing Compilers. T. Fahringer and B. Scholz. IEEE Transactions on Parallel and Distributed Systems (TPDS), IEEE Press, Vol. 11(11), pp. 1105-1125, 2000. [ps.gz] [4] Symbolic Data Flow Analysis for Detecting Deadlocks in Ada Tasking Programs. J. Blieberger, B. Burgstaller, and B. Scholz. In Proc. of the Ada-Europe International Conference on Reliable Software Technologies (ADA'00),Lecture Notes in Computer Science (LNCS), Vol. 1845, pp. 136-145, Springer Press, Potsdam, Germany, June 2000. [pdf] [3] Symbolic Pointer Analysis for Detecting Memory Leaks. B. Scholz, J. Blieberger, and T. Fahringer. In Proc. of the Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'00), pp. 104-113, ACM Press, Boston, MA, USA, January 2000. [pdf] [2] Interprocedural Symbolic Analysis of Ada Programs with Aliases. J.Blieberger, B. Burgstaller, and B. Scholz. In Proc. of the Ada-Europe International Conference on Reliable Software Technologies (ADA'99), Lecture Notes in Computer Science (LNCS), Vol. 1622, pp. 136-145,, Santander, Spain, June 1999. [pdf] [1] Symbolic Evaluation for Parallelizing Compilers. T. Fahringer and B. Scholz. In Proc. of the 11th ACM International Conference on Supercomputing (ICS'97), pp. 261-268, ACM Press, Vienna, Austria, July 1997. [ps.gz] |
|||
|
||||