\newcommand{\comment}[1]{}
\makeatletter
\long\def\unmarkedfootnote#1{{\long\def\@makefntext##1{##1}\footnotetext{#1}
}}
\makeatother

\documentstyle[twocolumn,epsf]{article}
\pagestyle{empty}

%set dimensions of columns, gap between columns, and space between paragraphs
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.8in}
\setlength{\footheight}{0.0in}
%\setlength{\topmargin}{0.25in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{-.15in}
\setlength{\evensidemargin}{.05in}
\setlength{\parindent}{1pc}

%I copied stuff out of art10.sty and modified them to conform to IEEE format

\makeatletter
%as Latex considers descenders in its calculation of interline spacing,
%to get 12 point spacing for normalsize text, must set it to 10 points
\def\@normalsize{\@setsize\normalsize{12pt}\xpt\@xpt
\abovedisplayskip 10pt plus2pt minus5pt\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus3pt\belowdisplayshortskip 6pt plus3pt
minus3pt\let\@listi\@listI} 

%need an 11 pt font size for subsection and abstract headings
\def\subsize{\@setsize\subsize{12pt}\xipt\@xipt}

%make section titles bold and 12 point, 2 blank lines before, 1 after
\def\section{\@startsection {section}{1}{\z@}{24pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\large\bf}}

%make subsection titles bold and 11 point, 1 blank line before, 1 after
\def\subsection{\@startsection {subsection}{2}{\z@}{12pt plus 2pt minus 2pt}
{12pt plus 2pt minus 2pt}{\subsize\bf}}
\makeatother

\begin{document}
\bibliographystyle{acm}

\date{}

\title{
%\begin{flushleft}
%\vspace{-0.9in}
%\scriptsize {\em 
%in Proceedings of the Scalable Parallel Libraries Conference II (SPLC94), Mississippi State, Mississippi, Oct, 1994.}
%\end{flushleft}
%\vspace{-0.1in}
\Large\bf Procedure Call Models for Distributed Parameters \\
 in Data Parallel Programs}


%for two authors (this is what is printed)
\author{\begin{tabular}[t]{c@{\extracolsep{8em}}c}
  Bwolen Yang	& David R. O'Hallaron \\
 \\
  \multicolumn{2}{c}{School of Computer Science} \\
  \multicolumn{2}{c}{Carnegie Mellon University} \\
  \multicolumn{2}{c}{Pittsburgh, PA~~15213}
\end{tabular}}

%\author{Bwolen Yang and David R. O'Hallaron\\
%School of Computer Science \\
%Carnegie Mellon University \\
%Pittsburgh, PA 15213}

\maketitle
\thispagestyle{empty}
\unmarkedfootnote{
Supported in part by the Air Force Office of Scientific Research under
contract F49620--92--J--0131, in part by the Advanced Research
Projects Agency under contract MDA972-90-C-0035.  Authors' email
addresses: bwolen@cs.cmu.edu, droh@cs.cmu.edu.
}

\thispagestyle{empty}

\subsection*{\centering Abstract}
{\em
When a computer program invokes a procedure, both the caller and the
callee must agree on how to pass the parameters into and out of the
procedure.  In this paper, this agreement is referred to as the
procedure call model.  In data parallel languages like High Performance
Fortran (HPF), the procedure call model for distributed parameters can
have a significant impact on procedure call overhead.  This paper
introduces a taxonomy of procedure call models, and examines how
different models can reduce the procedure call overhead by avoiding
unnecessary redistribution and by providing compile-time distribution
information.
A key result is that the procedure call model bounds the
availability of compile-time information on the distribution of
parameters, and this information can have an impact on the
quality of the redistribution code.
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section{Introduction}
When a sequential computer program invokes a procedure, the caller and
the callee must agree on how to pass parameters into and out of the
procedure.  We refer to this agreement as the {\em procedure call
model}.  The agreement is realized in the code in the form of an {\em
entry sequence} that runs before the procedure body and a {\em return
sequence} that runs after the procedure body.  Collectively the entry
and return sequences are known as the {\em calling sequences}.  Some
aspects of the procedure call model pertain to every parameter.  For
example, the caller and callee must agree on the order in which the
parameters will be pushed on to the stack.  Other aspects pertain to
each parameter individually, for example, the need for any type
conversions, or whether to pass a parameter using call-by-value or
call-by-reference. 
Depending on the language and implementation, different aspects of a
particular calling sequence might be specified by the programmer and
other aspects might be determined solely by the compiler. For example,
some compiler systems (e.g., Sun C compilers) determine the ordering
of parameters on the stack, while other systems (e.g., Borland C
compilers) allow the user to specify the ordering.

There is an additional complication when a data parallel program
~\cite{nesl94,pc++93,chapman92a,hpf93,fortrand92,iso90,stichnoth94,cmf91}
invokes a procedure: the procedure's parameters might be distributed
across the nodes of the system. In general, different
parameters can have different distributions, and the distribution of the
same actual parameter might change from invocation to invocation.  Thus,
calling sequences for data parallel programs must also include some
agreement about how to handle distributed parameters.  As with
sequential programs, the calling sequences might reflect a blanket
agreement that covers all distributed parameters.  For example, the
callee might agree to accept all parameters with arbitrary
distributions.  Or the callee might agree to restore every parameter in
every procedure to its entry distribution before returning control to
the caller.  In general though, each parameter can be treated
independently.  For example, the caller and callee might agree that one
parameter will have a certain distribution upon entry to the procedure,
that another parameter can have an arbitrary distribution, and so on.
Also, just as with sequential programs, the agreement captured in the
calling sequences might be determined by the compiler or the programmer.

Procedure call models can have a significant impact on procedure call
overhead in 
data parallel programs. This overhead, which is the additional running time
incurred by invoking procedures rather than inlining them, has two
components: (1) quality of the compiled code, and (2)
unnecessary parameter redistributions.  The procedure call model has an
impact on each component, and often there is tension between these two
components. For example, 
if a procedure agrees to accept its parameters in any distribution, the
entry sequence avoids redistributions, but at the cost of potentially
less efficient code in the procedure body.  On the other hand, if the
caller and callee agree on the entry distribution of the parameters,
then the compiler can generate more efficient code for the procedure
body, at the cost of a potential parameter redistribution during the
entry sequence.

Even though procedure call models can have a significant impact on
performance, they have not been studied much in the data parallel
literature. In this paper, we characterize the space of procedure call
models for data parallel programs and investigate the impact of
different models on procedure call overhead.  In particular, we discuss
the advantages and disadvantages of each model in terms of its effect on 
code quality and additional redistributions.  Next, we
measure the effects of factors that influence these redistribution
costs, including choice of distribution and the amount of compile-time
information about parameter distributions.  The measurements are
performed on High Performance Fortran (HPF)~\cite{hpf93} programs
compiled by a parallelizing Fortran compiler~\cite{stichnoth94} and
running on a 64-node parallel system~\cite{iwarp,iwarpcomm}.

The results of this study make two points clear. First, for both
procedure entry and return, each of the
models has advantages and disadvantages; no one model is best in
all cases.  Thus, we recommend that programming languages provide
directives that allow the programmer to explicitly define the procedure
call model for each distributed parameter.
Second, compile-time information about parameter distributions may or
may not have a significant impact depending upon the set of compiler
optimizations implemented.  In any case, distribution information
can lighten the burden on the compiler and can affect the code quality.
These results reinforce the case for HPF-like
interface blocks that allow procedures to export distribution
information at compile time.

The rest of the paper is as follows: Section~\ref{sec:models}
describes the space of procedure call models, and the advantages and
disadvantages of each model.  Section~\ref{sec:redistcost} describes
how compile-time distribution information can influence the
redistribution cost.
Section~\ref{sec:discussion} summarizes procedure call
models in existing data parallel languages and compiler systems.
Section~\ref{sec:summary} presents our conclusions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Procedure call models}
\label{sec:models}

Figure~\ref{fig:call} shows the anatomy of a procedure call --- the
execution of an {\em entry sequence}, followed by the procedure body,
and then a {\em return sequence}.

\begin{figure}[htbp]
\epsfxsize=3.25in
\centerline{\epsfbox{figures/call.eps}}
\caption{Anatomy of a procedure call}
\label{fig:call}
\end{figure}

The calling sequences reflect an agreement between the caller and
callee (or more accurately, an agreement between the compilers of the
caller and callee) about how to pass parameters into and out of the
procedure.  The agreement about how to pass parameters into a
procedure is called the {\em entry model}, and the agreement for
passing parameters out of the procedure is called the {\em return
model}.  Collectively, these agreements are referred to as {\em
procedure call models}.

For data parallel programs, the procedure call model must also include
agreements about how the parameters will be distributed on {\em
procedure entry} (i.e., just after the entry sequence) and on {\em
procedure return} (i.e., just after the return sequence).  On
procedure entry, a parameter's distribution can either {\em conform}
to some {\em conformation rules} (the {\em conform-on-entry} model) or
be {\em inherited}, as is, by the callee (the {\em inherit-on-entry}
model).  Similarly, on procedure return, a parameter's distribution
can either conform to some rules (the {\em conform-on-return} model)
or be inherited, as is, by the caller (the {\em inherit-on-return}
model).  The models for each parameter are independent, and the entry
and return models for a particular parameter are independent as well.
Also, we are assuming that procedures can change the distribution of a
formal parameter and that these changes can be reflected in the actual
parameter when the procedure returns.

Figure~\ref{fig:models} summarizes how we have partitioned the space
of procedure call models. The rest of this section discusses these
models in more detail.
\begin{figure}[htb]
\small
\centering
\begin{tabular}{|c||c|c|}
\hline
& Conform models & Inherit models\\
\hline
\hline
Entry models & {\em conform-on-entry} & {\em inherit-on-entry} \\
\hline
Return models & {\em conform-on-return} & {\em inherit-on-return} \\
\hline
\end{tabular}
\caption{Procedure call models}
\label{fig:models}
\end{figure}

\subsection*{Conform-on-entry}
The {\em conform-on-entry} model reflects an agreement between the caller
and the callee about the specific distribution of a parameter on procedure
entry, just after the execution of the last statement in the entry
sequence. The agreement is couched in terms of some conformation
rules. There are many possible kinds of conformation rules. For example, 
on procedure entry, the rule could require that a parameter's
distribution must conform to one particular distribution, or to a
small set of distributions~\cite{chapman92a}.

Conformation rules can be specified explicitly by the programmer
(typically by exporting the rule in a procedure interface block) or
determined automatically by the compiler. In general, the compiler has
complete freedom in specifying rules, as long as the compiler for the
caller and the compiler for the callee agree on the rule. For example,
an aggressive compiler could clone the procedure for a few common
distributions, and then export rules specifying that the parameters
are to conform to the one with minimum overhead.

When the compiler generates an entry sequence for the {\em
conform-on-entry} model, it must generate code that ensures the
distribution of each parameter conforms to the rule.  This will
typically involve redistribution code that changes the parameter from
the distribution it has just before the entry sequence (i.e., {\em the
source distribution}) to another distribution specified by the
conformation rule (i.e., the {\em target distribution}).  The
conformation process can take place on either the caller's or callee's
side of the entry sequence.  The advantage of redistributing on the
callee's side is smaller total code size because there are generally
multiple call sites for each callee.  The advantage of redistributing
on the caller's side is better code quality because at compile time, if
the source distribution can be known at all, it is known at the call
site.  Thus, the compiler can utilize this information to generate
more efficient redistribution code.  As Section~\ref{sec:distinfo}
shows, the redistribution cost can differ by as much as one order of
magnitude, depending on the amount of distribution information
available.  Therefore, if redistribution is necessary, it is more
efficient to do so at the entry sequence of the caller rather than that
of the callee.  However, callee redistribute has the advantage
that library procedures written in this model can be called with
actual parameters in any distribution. 
Thus, it is more user friendly.  Furthermore, if the library writer
decides a different distribution is more efficient for the computation
in the procedure body, recompilation of the library does not force
every caller's code to be recompiled.

\subsection*{Inherit-on-entry}
With the {\em inherit-on-entry} model, parameter distributions are
accepted as is. In some sense, this is an extreme case of a conform
model, with a ``nop'' conformation rule.  Inherit models are a form of
{\em lazy-redistribution}; redistribution occurs only when necessary.
The callee must be able to handle any input distribution, and in
general, the code generated by the compiler will not be as efficient
as code generated for a specific distribution.  However, in cases
where the computation does not depend on the ordering of the array
elements, a redistribution step can be completely avoided.  For
example, in a library routine that performs point-wise
or set operations, the {\em conform-on-entry} model will require a
redistribution step whenever the input distribution does not conform
to the conformation rule. By using the {\em inherit-on-entry} model,
this redistribution step can be eliminated.

This model has another additional advantage that is identical to that
of callee redistribute in the conform model; i.e.,
library procedures written using only this model can be called without
the caller worrying about the actual parameters' distributions.
Thus, it is more user friendly.  Furthermore, if the library is changed
so that the computation uses a different distribution of the parameter,
none of the callers needs to be recompiled.

The model has two drawbacks when redistribution of a formal
parameter is necessary inside the procedure body.  First, the
redistribution code must be able to handle all types of source
distributions.  If the procedure is a library written in a foreign
source language, writing this redistribution code
can be very difficult without compiler support.  This will limit
the number of usable of foreign source languages.
Another drawback is that when using this model, the
source distribution can become unknown to the compiler due to multiple
call-sites.   As we show in Section~\ref{sec:distinfo},
code quality for redistribution is generally
worse when the distribution information is unknown at compile
time.


\subsection*{Conform-on-return}
With the {\em conform-on-return} model, the caller and callee agree
that on procedure return, just after the last statement in the return
sequence, the distribution of a parameter will conform to some rules.
As with {\em conform-on-entry}, the rules can be specified either by
the programmer or by the compiler, and the compiler has complete freedom
in choosing the rules.  A common conformation rule used by compilers
is that a parameter's original distribution (just before the procedure
entry) must be restored when the procedure returns~\cite{chapman92a}.
This rule simplifies compiler analysis on the caller side. Another
example is that the compiler could analyze the callee and specify the
distribution of the distributed parameters at the return point.

The main advantage of the {\em conform-on-return} model is that some or
all of a parameter's distribution information is available to the 
caller's compiler which can utilize this information to generate
better code afterwards.
The conformation process in this model can take
place either in the callee or the caller side of the return sequence.
The advantage of redistributing on the callee side is smaller total
code size because there are generally multiple call sites for each
callee.  With regard to redistribution efficiency, depending on the
conformation rules, either side (callee or caller) could have more
distribution information.  For example, if a parameter's entry model
is {\em inherit-on-entry} and its return conformation rule requires
one to restore the parameter's original distribution, then in this
restoring process, the callee will have at least as much knowledge about
the source distribution as the caller, while the caller will have at
least as much knowledge about the target distribution as the callee.

\subsection*{Inherit-on-return}
With the {\em inherit-on-return} model, the caller inherits the
distribution of a parameter when the procedure returns. The main
advantage of this model is that when the distribution of the
parameter is changed in the procedure, this lazy redistribution can
avoid unnecessary data movement when the cost of redistribution
outweighs the overhead in code quality for the caller to inherit the
distribution.  For example, after the call returns, the
parameter may no longer be needed or will be redistributed before
the next use.

A major drawback of the {\em inherit-on-return} model is that if a
parameter is needed after the procedure return point, then since the
distribution information is no longer available at compile time, the
code generated might not be as efficient.  A way to recover the
distribution information is through interprocedural
analysis~\cite{hall92}. Or the {\em conform-on-return} model should be
used instead.


In summary, each distributed parameter in a procedure call can be
classified as either following a conform model or an inherit model
during the entry and return sequences.  In general, conform models
provide more compile-time information, and thus allow the compiler to
generate better quality code, at the cost of a potential parameter
redistribution. On the other hand, inherit models avoid the parameter
redistribution, but at the cost of potentially less efficient code.
For both procedure entry and return, no one model dominates the other.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Impact of distribution information on array redistribution}
\label{sec:redistcost}

Availability of distribution information at compile time can affect
the quality of the code generated, and in
particular the quality of the redistribution code (e.g., code that 
redistributes parameters in the procedure entry sequence, the procedure  
return sequence, or inside the procedure body).  This section examines
how availability of distribution information can influence the cost
of redistributing a 256K integer array on a 64-node iWarp
system~\cite{iwarp,iwarpcomm}.  The redistribution code is generated by
the Fx parallelizing Fortran compiler based on the algorithm
in~\cite{stichnoth94}. 

\subsection{iWarp and Fx}
The iWarp system is a distributed-memory multicomputer, consisting of
4 to 1024 nodes connected as a 2D torus.  iWarp is characterized by
{\em direct access to programmable connections}.  Connections between
arbitrary nodes can be established at run-time and left up for an
arbitrary amount of time. A connection can be established in roughly
20 $\mu$s.  Once the connection is established, a 32-bit data word can be
transferred between the connection and either user memory or a general
purpose register in 100 nanoseconds, roughly the same amount of time
as a register access.  The effective bandwidth between two node
programs communicating over a connection is 40 Mbytes/sec. The message
passing system used by the Fx compiler treats each message as a
short-lived connection, i.e., the connection is created for the
duration of a single message and then destroyed so that the hardware
resources can be used by other messages.  Program-to-program message
passing latency on iWarp for short messages is roughly 20 microseconds
and bandwidth for long messages approaches 40 Mbytes/second.  The
measurements in this papers were obtained on an $8 \times 8$ system.

Fx is a prototype HPF-like compiler developed at Carnegie Mellon.  Fx
supports block-cyclic distributions in an arbitrary number of array
dimensions.  For a given array dimension, a block-cyclic distribution
is characterized by the tuple $(n,b,p)$, where $n$ is the size of the
array dimension, $b$ is the block size, and $p$ is the number of
nodes, numbered $0,\ldots,p-1$.  Blocks of size $b$ are dealt out
cyclically to the $p$ nodes, such that block $0$ is assigned to node
$0$, block $p-1$ is assigned to node $p-1$, block $p$ is assigned to
node $0$, block $p+1$ is assigned to node $1$, and so on.  The block
distribution and the cyclic distribution are simply special cases of
the block-cyclic distribution, where $b = \left\lceil n/p
\right\rceil$ for the block distribution, and $b = 1$ for the cyclic
distribution.  For general block-cyclic distributions (i.e., neither block
nor cyclic distribution), the Fx compiler uses a {\em virtual cyclic}
approach~\cite{stichnoth93a} to generate redistribution code, as
opposed to a {\em virtual block} approach~\cite{gupta94}.  The virtual
cyclic approach iterates over the array sections as a union of cyclic
distributions,  while the virtual block approach iterates as a union of
block distributions.  The best approach depends on the block size.
The virtual cyclic approach favors smaller blocks, while the virtual
block approach favors larger blocks.  If the block size and number of
blocks per processor are roughly equal, then both approachs perform
about equally well.


\subsection{Impact on redistribution time}
\label{sec:distinfo}

In this section, we investigate how the amount of compile-time
distribution information affects the redistribution cost.  For
block-cyclic distributions, this information has four independent
components: (1) the destination distribution block size, (2) the
source distribution block size, (3) the number of processors, and (4)
the array size.  Each component can be known at compile time
independent of any other, which gives 16 possible cases for each
combination of source and destination distribution.

In our measurements, a data set consisting of redistribution costs for
16 possible cases is collected for each of the source/destination
combinations.  The measurements are done on combinations of
source/destination pairs formed from cyclic, block (block size 4K),
and general block-cyclic distributions.  For the general block-cyclic
distributions, block sizes of 2 (small), 64 (medium), and 2K (large)
are chosen as representatives.  The medium block size is chosen so
that the number of blocks per processor and the block size are equal.
Note that in this case, the virtual block and virtual cyclic
approaches work equally well.  Figure~\ref{fig:dist} shows the results
of two extreme cases from each combination: all distribution
information is known at compile time and no distribution information
is known.  Note that Figure~\ref{fig:dist} considers only data sets
where the source block size is greater than the destination block
size, since the symmetric cases have similar computation/communication
patterns and thus would have similar results.  The $\dagger$ mark
indicates those general block-cyclic cases where the virtual block
approach is more appropriate than the virtual cyclic approach.
Because the Fx compiler does not currently support the virtual block
approach, we simulate the redistribution process by using a block
distribution on multiple smaller size arrays to reflect the virtual
block approach.  Because this simulation is done at the source level,
it is less efficient than if the compiler supported the virtual block
approach.

\begin{figure}[htb]
\small
\centering
\begin{tabular}{|c|c|c||r|r|r|}
\hline
     & \multicolumn{2}{|c||}{Block Size} & \multicolumn{2}{c|}{Time (ms)} &
                                                             \\ \cline{2-5}
 Set &  Src & Dest & \multicolumn{1}{c|}{All} &
         \multicolumn{1}{c|}{None} & \multicolumn{1}{c|}{\% Diff}
                                                             \\ \hline  \hline
  A  &    2     &     1     &    8.9  &   10.8 &    21.3\%   \\ \hline
  B  &   64     &     1     &   14.6  &   16.8 &    15.1\%   \\ \hline
  C  &   64     &     2     &   17.2  &   17.7 &     2.9\%   \\ \hline
  D  &   2K     &     1     &   21.1{$^\dagger$}  &   25.7{$^\dagger$} &     4.6\%   \\ \hline
  E  &   2K     &     2     &   29.0{$^\dagger$}  &   30.2{$^\dagger$} &     3.6\%   \\ \hline
  F  &   2K     &    64     &  263.3{$^\dagger$}  &  288.7{$^\dagger$} &     9.6\%   \\ \hline
  G  &   4K     &     1     &   11.4  &   13.7 &    20.2\%   \\ \hline
  H  &   4K     &     2     &   15.3  &   15.8 &     3.3\%   \\ \hline
  I  &   4K     &    64     &  137.7  &  151.9 &    10.3\%   \\ \hline
  J  &   4K     &    2K     &    6.5{$^\dagger$}  &    6.8{$^\dagger$} &     4.6\%   \\ \hline
\end{tabular}
\caption{Time (ms) to redistribute a 256K-integer array over 64 nodes
when all parameters are known at compile time (4th column) vs. when none is
known (5th column). {$\dagger$} indicates the measurement is obtained by
simulating the virtual block approach.}  
\label{fig:dist}
\end{figure}

Figure~\ref{fig:dist} shows that whenever the cyclic distribution is
involved (sets A, B, D, and G), the distribution information
contributes about 15--20\% in redistribution overhead.  Over 90\% of
this difference is mainly because the compiler does not know that it
is actually dealing with the cyclic distribution.  Thus, whenever
possible, helping the compiler recognize the cyclic distribution case
is important.  For all other cases, redistribution costs are only
marginally affected by compile-time distribution information.


\begin{figure}[htb]
  \tt \small
  \begin{tabbing}
  tttt\=tttttt\=tttt\=tttt\=tttt\= \kill
  \> L1 \> for each destination processor $p$                 \\
  \> L2 \> \> for each of $p$'s destination array section $d$ \\
  \> L3 \> \> \> for each of my source array section $s$      \\
  \> B1 \> \> \> \> compute intersection of $d$ and $s$       \\
  \> B2 \> \> \> \> put intersected data into a buffer       \\
  \> S1 \> \> send data in the buffer to $p$                  \\
  \end{tabbing}
  
  \caption{Code for array redistribution.}
  \label{code:redistribution}
\end{figure}

In data sets that involve a block size of 64 (sets F and I), the
redistribution costs are one order of magnitude larger than the
others.  This anomaly is due to the fact that a block size of 64 is
the worst case because both the virtual cyclic and the virtual block
approaches require iterating over 64 array sections.
Figure~\ref{code:redistribution} shows a rough outline of the
redistribution code generated by Fx.  For set F, the statements {\tt
B1} and {\tt B2} in the loop body executed 8192 times ((64 processors)
$\times$ (64 destination array sections) $\times$ (2 source array
blocks)).  The program spends 71.8\% (189 ms) of the total
redistribution time in statement {\tt B1}.  An optimization that could
have been applied is that instead of using each element as the basic
unit of intersection, the compiler could use $\gcd$(source block size,
destination block size) elements as the unit for intersection.  For
example in set F, the unit of intersection could be 64 elements
($\gcd$(64, 2K)).  Then there would be only 1 destination array
section, thus reducing the execution frequency of the loop body from
8192 to 128 times.  Correspondingly, the time spent on executing
statement {\tt B1} would decrease from 189 ms to 2.95 ms ($=$ 189/64).
Thus the total redistribution time would be at most 77 ms ($=$ 263.3
$-$ (189 $-$ 2.95)).


\subsection{Impact on compiler optimizations}
\label{sec:opt}

In this section, we explore how distribution information affects 
three compiler optimizations on array redistribution code.

\subsubsection*{Loop elimination}
Since computing the array intersection (statement {\tt B1}) can be
expensive, trimming the 
the loop bounds to avoid computing trivially empty intersections
is important.   However, trimming loop bounds can also be relatively
expensive.  For sets A, B, D, and G in Figure~\ref{fig:dist}, whenever
the distribution is known to be cyclic (i.e. only one array section), 
loop {\tt L2} can be eliminated, which eliminates unnecessary loop bounds
trimming.  This optimization alone accounts for over 90\% of the
difference in these sets of data.
Lacking distribution information at compile time, this optimization
could be done at run-time, which would require the compiler to
generate code that chooses between the general code or code specialized 
for the cyclic distribution.  


\subsubsection*{Loop reordering} 
Since the loop bounds computation can be expensive, the loops {\tt L2}
and {\tt L3} in Figure~\ref{code:redistribution} can be interchanged
so that the number of loop bounds computations for the inner-most loop
is minimal; i.e., place the array with the most array sections in the
innermost loop.  In set B, a wrong ordering will increase the
redistribution cost from 16.8 ms to 176.1 ms.  Withoug distribution
information at compile time, this optimization would need need to be
done at run-time, which would require the compiler to generate code to
choose between 2 possible orderings.


\subsection*{Virtual cyclic vs. virtual block}
Choosing between virtual cyclic and virtual block can have a very
significant impact on redistribution cost.  For example, for set J in
Figure~\ref{fig:dist}, if the virtual cyclic approach is used for both
source and destination, the redistribution cost will degrade from 6.5
ms to 5.5 seconds.  Without distribution information at compile time,
this choice must be made at run-time.  Let $n$ be the total
number of distributed dimensions of source and destination
distributions.  Then there are 2$^{n}$ run-time choices.  For set
J, there are 4 run-time choices.


In summary, the distribution information can not only affect the
redistribution cost, it can also help lighten the burden on the
compiler.  Without the distribution information, the compiler can
either risk making the wrong choice at the compile time, or generate
an exponential number of run-time choices , since the number of
choices is the product of the number of choices for each optimization.
The former could end up to be an expensive mistake, while the later
might not be feasible if the number of choices becomes too large.


\section{Procedure call models in existing data parallel systems}
\label{sec:discussion}

The current specification of HPF~\cite{hpf93} allows the programmer to
choose the procedure call model on procedure entry, but not on
procedure return. Both {\em conform-on-entry} and {\em
inherit-on-entry} \  are supported. However the programmer's freedom to
specify the conformation rule is limited -- in the procedure interface
block, the programmer can specify a single distribution that the
parameter must conform to on entry. In HPF, the programmer can also
use the procedure interface block to choose the {\em inherit-on-entry}
model. An aggressive HPF compiler might also be able to determine that
the {\em inherit-on-entry} model is beneficial through interprocedural
analysis.

There is no mechanism in HPF for the programmer to specify the return
model for a procedure call.  As the availability of compile time
distribution information can have an impact on code quality,
extending the HPF procedure interface block to optionally contain
parameter distribution on return might be beneficial.
This extension would allow the
programmer to specify the distribution at return point in the event
that interprocedural analysis fails or doesn't exist.  By further
extending the HPF interface block to allow the programmer to choose
the {\em inherit-on-return} model, unnecessary redistribution can be
avoided, since the programmer might have more knowledge of the program
than interprocedural analysis can provide.  Furthermore, when the
procedure is written in a foreign source language like assembly (a
common practice for separately compiled vendor supplied library
routines), then interprocedural analysis can be very difficult if not
impossible.

The current implementation of the Fx compiler~\cite{stichnoth94}
provides directives that allow the programmer to choose either the
conform model or the inherit model on entry. Like HPF, the programmer
can specify a single distribution for the conformation rule, and there
is no support for either of the return models. Unlike HPF, Fx does not
provide a procedure interface block, which makes it more difficult to
write efficient separately-compiled library routines.

Vienna Fortran~\cite{chapman92a} allows the programmer to specify
either the {\em conform-on-entry} or {\em inherit-on-entry} models,
but does not support either of the return models.  It also allows the
programmer to specify a number of interesting and potentially very
useful conformation rules. As in Fx and HPF, the programmer can
specify a single distribution for the conformation rule. However, the
programmer can also specify a set of potential distributions, one of
which the parameter is guaranteed to have on entry. There is also a
special form of a case statement that allows the programmer to provide
the code for each of the different potential distributions. In a
sense, the programmer is giving hints to the compiler about how to
clone the procedure.

\section{Conclusions}
\label{sec:summary}

For both procedure entry and return, each of the procedure call models
presented in this paper has advantages and disadvantages; no one model
is best in all cases.  Using these procedure call models, a programmer
can avoid unnecessary redistributions in the procedure calling
sequences and can affect the code quality generated by providing
various amounts of distribution information at compile time.  Our
measurements show that compile-time distribution information does not
significantly affect the redistribution cost given a good set of
optimizations.  However, if the run-time optimizations become
infeasible (e.g., due to the code size), the compile-time distribution
information can have a very significant performance impact on the
redistribution cost.  Thus, data parallel languages should provide
directives that allow the programmer to explicitly define the
procedure call model for each procedure definition.

\section*{Acknowledgements}
We wish to thank Jim Stichnoth and Jaspal Subhlok for their key
contributions to the Fx compiler system and for their helpful comments
and suggestions.  We would also like to thank Alan Fisher and Claudson
Bornstein for their insights and comments.

\bibliography{/afs/cs/project/iwarp/member/droh/bib/refs}
\end{document}

