Next: References Up: Future Work Previous: Fortran 90D/HPF on

InterProcedural Analysis

Interprocedural Analysis (IPA) applies various techniques across procedure boundaries and can be used on Fortran 90D/HPF programs to enhance optimizations, expose parallelism, minimize communication and check program correctness [70].

The most immediate area where IPA is needed is in detecting the compliance of variables and COMMON blocks with the relaxed storage and sequence association rules presented in the HPF Language Specification. Compliance needs to be checked at link time or whenever all the relevant program units are visible. Obviously, additional information describing the common blocks and variables needs to be made available. This can be done through a database mechanism or by embedding the information within the object file. The method used may depend on whether the mode of operation is sourceÊtoÊsource or source-to-machine language.

However, the need for IPA goes far beyond correctness checking. HPF can be a successful parallel programming paradigm only when it improves the application's performance. The transformation from a sequential program to a Single Program Multiple Data (SPMD) program occurs in three major areas:

1) Loops and array references are transformed in their index range. Other types of loop transformations may occur such as interchange, splitting and merging.

2) Insertion of message passing calls (communication and synchronization) are added to handle static and dynamic mapping.

3) Miscellaneous code (including conditional statements) is added in order to regulate processor control over certain portions of the program. Conditional statements are added to check for the need for remapping of data.

It is possible to use IPA to reduce the amount of overhead in this sequential to SPMD transformation.

Constant Propagation across procedure boundaries is probably the easiest and yet one of the most useful IPA methods. It can aid in reducing all three of the above areas. Additionally, it can aid in the latter stages of single node optimizations such as vectorization and software pipelining.

Propagation of mapping information across procedure calls can reduce overhead involved in areas 1 and 2 in multiple ways. One way is to determine program correctness when distribution directives are used for variables that assert their mapping. Probably the largest gain from IPA of mapping information is in the elimination of unnecessary distribution checking or redistribution of data across calls. This can be a significant advantage since the alternative is to redistribute upon entry and upon exit to a procedure.

Function cloning, when used judiciously, can save significant amounts of overhead. For example, mapping information may reveal that an argument to a call has only two mappings possible. If so, it may be beneficial to clone that function with each having a different assumption about the mapping of the incoming mapped argument.

Function inlining is the traditional form of interprocedural analysis and is sometimes referred to as an interprocedural transformation. This technique has enjoyed some success although results have been inconsistent. Function inlining has the potential to expose parallelism, reduce calling overhead, increase optimization opportunities and eliminate redistribution and communications. However, unnecessary function inlining can often have negative side effects as well including code explosion.

==1.2.5-=.9=



Next: References Up: Future Work Previous: Fortran 90D/HPF on


zbozkus@
Thu Jul 6 21:09:19 EDT 1995