B.1 Data Dependence Definitions

Data dependence is the criterion that KAP uses to determine if a given loop can be optimized. KAP tries to ensure that the optimized program produces the same results as the scalar input. For some loops, certain optimizations can result in incorrect answers; in these cases KAP detects and informs you of the dependencies that can interfere with KAP transformations.

Data dependence analysis was originally motivated by vector and parallel computation. The basic tools and notations apply to advanced serial optimizations on uniprocessor computers.

KAP determines data dependence and bases decisions on such information automatically, informing you only of those dependencies preventing optimization.

KAP uses a data dependence graph that shows where data values are generated and where they are used within a DO loop or DO loop nest. The data dependence graph is processed (with standard graph traversal techniques) to find potential problem areas, which appear as cycles in the graph. Each data dependence cycle is carefully examined to see if it can be broken and the loop transformed, or if part or all of the loop must be executed in its original form.

For an in-depth study of data dependence, consult the following:

• Michael Wolfe, "Optimizing Supercompilers for Supercomputers," (Research monographs in parallel and distributed processing) MIT Press, Cambridge, MA, 1989.

• Michael Wolfe and Utpal Banerjee, "Data Dependence and Its Application to Parallel Processing," International Journal of Parallel Programming, Vol. 16, No. 2, April, 1988.

• David Padua and Michael Wolfe, "Advanced Compiler Optimization for Supercomputers," Communications of the ACM, Vol. 29, No. 12, December, 1986.

Copyright © Digital Equipment Corporation. 1999. All Rights Reserved.