Symbolic Analysis For Parallelizing Compilers

In Symbolic Analysis for Parallelizing Compilers the author presents an excellent demonstration of the effectiveness of symbolic analysis in tackling important optimization problems, some of which inhibit loop parallelization. The framework that Haghighat presents has proved extremely successful in induction and wraparound variable analysis, strength reduction, dead code elimination and symbolic constant propagation. The approach can be applied to any program transformation or optimization problem that uses properties and value ranges of program names. Symbolic analysis can be used on any transformational system or optimization problem that relies on compile-time information about program variables. This covers the majority of, if not all optimization and parallelization techniques. The book makes a compelling case for the potential of symbolic analysis, applying it for the first time - and with remarkable results - to a number of classical optimization problems: loop scheduling, static timing or size analysis, and dependence analysis. It demonstrates how symbolic analysis can solve these problems faster and more accurately than existing hybrid techniques.

Abstract: "The notion of dependence captures the most important properties of a program for efficient execution on parallel computers. The dependence structure of a program defines the necessary constraints of the order of execution of the program components, and provides sufficient information for the exploitation of the available parallelism. Static discovery and management of the dependence structure of programs saves a tremendous amount of execution time, and dynamic utilization of dependence information results in a significant performance gain on parallel computers. However, experiments with supercomputers indicate that existing multiprocessing environments are unable to deliver the desired performance over a wide range of real applications, mainly due to lack of precision of their dependence information. This calls for an effective compilation scheme capable of understanding the dependence structure of complicated application programs. This thesis describes a methodology for capturing and analyzing program properties that are essential in the effective detection and efficient exploitation of parallelism on parallel computers. Based on this methodology, a symbolic analysis framework is developed for the Parafrase-2 parallelizing compiler. This framework extends the scope of a variety of important program analysis problems, and solves them in a unified way. The attained solution space of these problems is much larger than that handled by existing compiler technology. Such a powerful approach is required for the effective compilation of a large class of application programs."

This book presents novel symbolic control and data flow techniques as well as symbolic techniques and algorithms for program analysis and program optimization. Program contexts, defining a new symbolic description of program semantics for control and data flow analysis, are at the center of the techniques and methods introduced. The authors develop solutions for a number of problems encountered in program analysis by using program contexts. The solutions proposed are efficient, versatile, unified, and more general than most existing methods. The authors' symbolic analysis framework is implemented as a prototype as part of the Vienna High Performance Compiler.

A systematic method for generalized strength reduction based on this representation is also presented. This results in an effective scheme for exploitation of parallelism and optimization of the code. Symbolic analysis also serves as a basis for other code generation optimizations such as elimination of redundant computations."

The objective of program analysis is to automatically determine the p- perties of a program. Tools of software development, such as compilers, p- formance estimators, debuggers, reverse-engineering tools, program veri?- tion/testing/proving systems, program comprehension systems, and program specializationtoolsarelargelydependentonprogramanalysis. Advancedp- gram analysis can: help to ?nd program errors; detect and tune performan- critical code regions; ensure assumed constraints on data are not violated; tailor a generic program to suit a speci?c application; reverse-engineer so- ware modules, etc. A prominent program analysis technique is symbolic a- lysis, which has attracted substantial attention for many years as it is not dependent on executing a program to examine the semantics of a program, and it can yield very elegant formulations of many analyses. Moreover, the complexity of symbolic analysis can be largely independent of the input data size of a program and of the size of the machine on which the program is being executed. In this book we present novel symbolic control and data ?ow repres- tation techniques as well as symbolic techniques and algorithms to analyze and optimize programs. Program contexts which de?ne a new symbolic - scription of program semantics for control and data ?ow analysis are at the center of our approach. We have solved a number of problems encountered in program analysis by using program contexts. Our solution methods are e?cient, versatile, uni?ed, and more general (they cope with regular and irregular codes) than most existing methods.

Abstract: "A framework is introduced to solve the dependence problem in the presence of unknown symbolic terms. This framework uses the idea of abstract interpretation of programs, and is based on lattice theoretical models. Theories of dependence analysis, flow analysis, and approximate semantic analysis of programs are discussed. The details of implementation of symbolic dependence analysis in Parafrase-21 [PGH+89] is presented."

The articles in this volume are revised versions of the best papers presented at the Fifth Workshop on Languages and Compilers for Parallel Computing, held at Yale University, August 1992. The previous workshops in this series were held in Santa Clara (1991), Irvine (1990), Urbana (1989), and Ithaca (1988). As in previous years, a reasonable cross-section of some of the best work in the field is presented. The volume contains 35 papers, mostly by authors working in the U.S. or Canada but also by authors from Austria, Denmark, Israel, Italy, Japan and the U.K.

This book constitutes the thoroughly refereed post-proceedings of the 15th International Workshop on Languages and Compilers for Parallel Processing, LCPC 2002, held in College Park, MD, USA in July 2002. The 26 revised full papers presented were carefully selected during two rounds of reviewing and improvement from 32 submissions. All current issues in parallel processing are addressed, in particular memory-constrained computation, compiler optimization, performance studies, high-level languages, programming language consistency models, dynamic parallelization, parallelization of data mining algorithms, parallelizing compilers, garbage collection algorithms, and evaluation of iterative compilation.

This book constitutes the strictly refereed post-workshop proceedings of the 4th International Workshop on Languages, Compilers, and Run-Time Systems for Scalable Computing, LCR '98, held in Pittsburgh, PA, USA in May 1998. The 23 revised full papers presented were carefully selected from a total of 47 submissions; also included are nine refereed short papers. All current issues of developing software systems for parallel and distributed computers are covered, in particular irregular applications, automatic parallelization, run-time parallelization, load balancing, message-passing systems, parallelizing compilers, shared memory systems, client server applications, etc.