\section{Background and Motivation}
\label{section:current}
%
The Fortran D compiler and the Pablo performance analysis environment
individually provide sophisticated support for developing high-performance
data-parallel programs, but each can benefit significantly from mutual
integration. The following subsections describe the functionality of each
subsystem, and then use an example to illustrate the need for integrated
compilation and performance analysis.

\subsection{Fortran D Compiler}
\label{section:fortrand}
%
A Fortran D program consists of a base Fortran 77 program annotated with
data distribution directives describing how the principal arrays of the
program are to be distributed across the processors in a parallel
system. (The example below will illustrate the use of the data layout
directives.) The Fortran 77D compiler uses this data-distribution to
generate an explicitly parallel, {\em single-program multiple data} (SPMD)
node program for a distributed-memory machine. The compiler first
partitions the computation using the {\em owner-computes} rule \cite{RP89},
and then implements the necessary communication and synchronization by
inserting calls to a message-passing library for the target
machine.\footnote{ While the Fortran D compiler includes support for irregular
	applications (those whose computational requirements and non-local
	data requirements cannot be determined at compile-time), the work
	described here focuses on programming environment support for
	regular applications alone. }

To generate and optimize the explicitly parallel program, the
compiler transforms the code extensively.  It converts the shared arrays
(i.e., the global name space) to local arrays, perhaps introducing overlap
areas to simplify the generated code.  It reduces loop bounds and
introduces guards as necessary to partition the computation among the
processors.  It computes what non-local array sections are referenced by
each RHS reference to determine the communication required. It optimizes
the communication by hoisting messages out of loops (message
vectorization), combining messages between the same pair of processors
(message aggregation), and moving message sends above preceding code blocks
that do not modify the data being sent (vector message pipelining). It
introduces collective communication such as broadcasts or reductions when
required. In loop nests with loop-carried, cross-processor true
dependences, it pipelines the computation to achieve partial parallelism,
using strip-mining to amortize the overhead of message-passing by using
fewer but larger messages (coarse-grain pipelining). Finally, it introduces
explicit buffering for messages where necessary, and replaces the
corresponding array references with buffer references to avoid unbuffering
costs when possible.

\subsection{Pablo Performance Environment}
\label{section:pablo}

The Pablo environment consists of three primary components: an extensible
data capture library \cite{pabloScale:93}, a data meta-format for
describing the structure of performance data records without constraining
their contents \cite{aydt:sddf}, and a graphical data analysis toolkit that
allows users to quickly construct new performance data analyses
\cite{pabloSpringer:93,pabloVR:94}.

The data capture library can trace, count, or time code fragments as well
as capture entry to and exit from procedures, loops, and message-passing
calls.  A group of library extension interfaces allow instrumentation
software developers to incrementally add new functionality to the library.
For example, one extension computes histograms of input/output performance
metrics, given an event trace of input/output events,\footnote{
	This input/output extension is basis for input/output
	characterization in the national Scalable I/O Initiative 
	and to tune the performance of input/output intensive
	scientific codes \cite{mckoy:workshop}. 
}
whereas another computes sliding window averages of performance data.

Perhaps the key source of the flexibility in all components of Pablo is a
flexible performance data meta-format that separates data semantics from
data structure. The Pablo Self-Defining Data Format (SDDF) is a data
description language that specifies both the structure of data records and
the data record instances, thus providing the ability to define and process
new performance data records to suit the needs of a performance tool. Thus,
SDDF provides a natural mechanism for information sharing between the
Fortran D compiler and the Pablo performance analysis software.

%% Finally, the graphical data analysis toolkit provides the ability to define
%% new graphical display modules driven by SDDF records, while a predefined
%% set of display modules support visualization of standard parallel system
%% performance metrics such as processor utilization and message volume in a
%% variety of formats.  The example in the following section illustrates the
%% information provided by these current displays.

\subsection{Performance Correlation Example}
\label{section:motivate}
%
The need for integrated compilation systems and performance tools is best
illustrated by considering the steps to analyze the performance of a simple
Fortran~D code using decoupled compilation and performance analysis tools.
As an example, we use the Erlebacher code, an 800 line, ten procedure
benchmark written by Thomas Eidson at ICASE.  Erlebacher solves 3-D partial
differential equations by performing tridiagonal solves using
Alternating-Direction-Implicit (ADI) integration. The program operates in
succession on each of the three dimensions, with each dimension consisting
of a computation phase, followed by forward and backward substitution
phases.  Each substitution phase creates a computation wavefront across the
array in the corresponding direction. Figure \ref{figure:erle-source} shows
a portion of the Fortran D data declarations and one loop nest of the
source code. The {\tt decomposition}, {\tt align} and {\tt distribute}
statements instruct the compiler to replicate the first two dimensions of
the array {\tt duz} and to distribute the third dimension in contiguous
blocks.  The loop nest corresponds to the backward substitution phase in
the third dimension.

The Fortran D compiler translates the data declarations and the sequential
loop of Figure \ref{figure:erle-source}
into the parallel, message-passing code for the Intel iPSC/860 shown in
Figure~\ref{figure:erle-f77}.  The compiler distributes the array across
the processors as specified, but also adds overlap areas to hold
off-processor values ($z=0$ and $z=9$) in order to simplify the generated
code. It then distributes the iterations of the $k$ loop across the
processors, with iteration $k$ being executed on the processor that owns
the $k^{th}$ XY plane, as specified by the owner-computes rule. Communication
is then required to satisfy references to non-local sections of the array.
Merely inserting the communication inside the $i$ loop, however, would
result in frequent, extremely fine-grain messages (of one word each) and
consequently too much communication overhead.  Instead, the compiler
strip-mines the $i$ loop in blocks of 8 iterations and uses one message per
block of 8 elements in order to amortize this overhead. It also inserts a
broadcast to satisfy the source reference {\tt duz(i,j,64)}, and hoists the
broadcast outside the $i$ and $j$ loops since this boundary XY plane is not
modified within this loop.

%-------------------------
\input{Figures/erle-code.tex}
%-------------------------

Comparing Figure~\ref{figure:erle-source} with Figure~\ref{figure:erle-f77}
highlights the difficulty of the performance analysis task faced by a
Fortran D application developer. There are significant structural and
semantic differences between the two versions of the code:
{ \def\baselinestretch{1.0}
\begin{itemize}
\item[$-$]
the single-threaded, global name-space, programming model is replaced by
an explicitly parallel, local name-space, message-passing model;
\item[$-$]
the use of overlap areas and explicit buffering complicates the
relationship between global and local data layouts;
\item[$-$]
the computation is substantially reordered to achieve partial parallelism,
resulting in several, staggered wavefronts moving across the array;
\item[$-$]
the loop indexing to handle boundary conditions is more complex;
\item[$-$]
the pipelined communication requires careful tuning to appropriately
trade-off parallelism and communication, but this requires extensive
understanding of the communication and computation performance
characteristics of the underlying machine.
\end{itemize}
}

These deep differences between source and compiled code impose at least
three kinds of obstacles to the development of efficient, data-parallel
programs. First, during code development, it is difficult for a programmer
to understand how the code being written will be parallelized, and thus
difficult to understand the implications of algorithmic and code design
choices on performance. Therefore, it is important that the programming
environment provide at least a qualitative understanding of the parallelism
and communication synthesized by the compiler and the impact of
source code constructs on these.

\begin{figure}[tb]
\centerline{\psfig{file=Figures/erle-traffic.ps,width=1.0\textwidth}}
\caption{Erlebacher Dynamic Behavior (Pablo Performance Environment)}
\label{figure:erle-traffic}
\end{figure}
%
Second, performance information obtained by measuring the executing program
most directly relates to the characteristics of the explicitly parallel
code, and is extremely difficult to interpret in relation to the source
code written by the programmer. For example, for the code fragment above,
current performance instrumentation and analysis
tools~\cite{pabloTools:94,pabloSpringer:93,millerIPS2:90,riesIPD:93} for
distributed memory parallel systems would capture and present performance
data from the generated Fortran 77 code of Figure~\ref{figure:erle-f77}.
Thus, current Pablo performance displays for this program (shown in
Figure~\ref{figure:erle-traffic}) clearly show the performance
characteristics of the message-passing program, including the volume of
message traffic, processor utilizations, and the staircase communication
pattern arising from nearest neighbor communication. While these displays
are useful, they fail to help the programmer understand where in the
original source code the principal performance bottlenecks in the program
originated, or
the underlying causes of these bottlenecks. Without this understanding, the
programmer will be unable to improve the program's performance. 
To support performance analysis and tuning without sacrificing the advantages
of the abstract, data-parallel language, it is imperative that performance
tools correlate performance information to the source code written by the
programmer, and explain the impact of source code constructs on the
performance.

Finally, complex compiler-synthesized communication patterns like the
coarse-grained pipeline in Figure~\ref{figure:erle-f77}
are difficult for the programmer to manipulate for tuning.
As \S\ref{section:self-tuning} shows, tuning the
pipeline requires a sophisticated and detailed understanding of the system
performance characteristics.
Instead, tuning such communication patterns more
appropriately falls into the purview of the compiler, with the support of
the programming environment.

To provide the various kinds of performance support recommended above,
the performance environment needs detailed
information about the relationship between the source program and the
compiler-synthesized explicitly parallel code. This information could be
obtained if the compiler made available the results of its analysis and
relevant aspects of the code transformations it performs. Furthermore, the
compiler can exploit dynamic performance data to tune communication
patterns like the coarse-grained pipeline. Together, these requirements
strongly motivate an integrated approach to compilation and performance
analysis, with each component of the system making available analysis
results to the other to raise the level of information provided by the
programming environment. The following section describes our efforts to
develop such an integrated programming environment, based on the Rice
Fortran 77D compiler and the Pablo performance environment.


%% The advantages of the abstract, data-parallel languages would be lost if
%% the programmer were required to understand the details of this
%% compiler-generated code in order to understand the program's performance
%% characteristics during code development and tuning.  In particular, the 
