Program Analysis and Restructuring for  High-Performance Computing
Oliver Sharp
(Professor S. L. Graham)
(ARPA) DABT63-92-C-0026 and Hertz Fellowship

We are building an analysis tool for fortran to investigate the
compilation of heterogeneous computations with irregular execution
behavior for highly parallel machines. The tool performs an extensive
symbolic analysis of sequential code and applies a series of
transformations to the code to expose parallelism and improve
utilization of resources. In addition to parallelism within a
computation (as in an individual loop nest), the tool manages the
interaction between computations. By breaking synchronization
constraints, the tool exposes additional concurrency that can be
exploited by adaptive scheduling strategies to improve efficiency.

The symbolic analysis begins by converting the program into an
extended static single assignment (SSA) form that includes symbolic
assertions. The assertions are used to limit the range of values that
a variable can take on and to statically compute conditional
expressions.  We gather the symbolic information into Symbolic Data
Descriptors, which summarize the data access behavior of the
code. Using these descriptors, the system can perform a variety of
code transformations; these range from traditional optimizations that
improve performance within a single computation to those that handle
computation interaction.

There are many ways to improve performance of a given computation;
particularly important are loop transformations like interchange and
fusion.  After these are applied, however, our tool exposes additional
concurrency by splitting sub-computations into concurrently executing
sections and pipelining multiple sub-computations.  By combining this
tool with our adaptive runtime system, we have been able to
substantially improve the scheduling efficiency of irregular programs,
including climate modeling and X-ray tomography.