NPAC Technical Report SCCS-698
A Framework for Representing Data Parallel Programs and its Application in Program Reordering
Rajesh Bordawekar, Alok Choudhary
Submitted March 6 1995
Abstract
In this paper, we present a framework for describing the dataflow and
dependence information of a data parallel program. Our framework
initially represents the program using a directed Intermediate Program
Locality Graph (IPLG). Using Dependence Access Relations (DARs),
the ILDG is reduced to a Program Locality Graph (PLG).
The information provided by PLG is used by the compiler to reorder the
program to improve program locality. We view the program reordering
problem as an optimization problem. To solve this problem, we present
a polynomial time heuristic, called the {\em Range Reduction
Heuristic}. The best case time complexity of the heuristic is
$O(m^{2}n^{2})$, where $m$ is the number of statements and $n$ is the
number of arrays used in the program. The average case running time of
the algorithm approaches the best case performance.
This framework will be implemented as a part of the PASSION ({\bf
P}arallel {\bf A}nd {\bf S}calable {\bf S}oftware for {\bf I/O})
compiler to compile out-of-core HPF programs. The PASSION compiler
will take advantage of the improved program locality and use the
dependence/dataflow information to perform further optimizations like
(1) Providing Hints to the file system, (2) Data Retaining Policies,
(3) Dead-code Computation Elimination and (4) Local File Reorganization.