

\subsection{Loop Level Parallelization}

In HPF the parallel loops are specified by the user explicitly using
{\tt FORALL} or {\tt INDEPENDENT DO} statements. Regular {\tt DO} 
loops are executed completely sequential. {\tt FORALL} is a generalization
of the Fortran 90 array assignment and {\tt WHERE} statements \cite{HPFBook}.
The statement executes in parallel and the results are identical if 
it is re-executed with the same data. 
A multiple-statement {\tt FORALL} (i.e., construct) is the same as a 
series of single statement {\tt FORALL} statements.
Every statement of 
the {\tt FORALL} has one synchronization point after the right-hand side
is computed and after the assignment is made to the left-hand side. 
 
{\tt INDEPENDENT DO} is for situations where the programmer knows that
a loop is parallel, but the compiler cannot detect this parallelism. 
This is especially
useful for array indices that are computed at runtime or involve a
level of indirection. 
When necessary, the {\tt NEW}  clause is used to declare
temporaries in {\tt INDEPENDENT} loops to preserve the assertions for being an
{\tt INDEPENDENT} loop. For each {\tt NEW} object a new instance
of that variable is created at  each iteration of the loop.

\subsection{Communication Optimizations}

HPF compilers take care of generating the
appropriate communication calls and bringing in the required non-local
data automatically. However, the success of the compilers at this 
early stage is still influenced by the way the programmer specifies the code
 fragments that require communication. 
Uniform or aggregate styles of communication \cite{LiChen} are more efficient 
on a network of workstations environment with high latencies.
Before moving particles to other processors, we formed {\em send-lists}
containing all the particles to be moved  and transferred these 
lists to the neighbors by using aggregate communication primitives
such as {\tt CSHIFT or TRANSPOSE} at each step. 

\subsection{Passing Distributed Data to Subroutines}

When it is more efficient to use a different data mapping in a subroutine,
the subroutine temporarily alters the data mapping of a data structure
visible to its caller.  
Since remapping a large data set imposes a large runtime overhead,
we avoided any unnecessary data remappings over subroutine boundaries by using 
the HPF's descriptive directives.
A {\bf descriptive
directive} asserts that no remapping of an actual argument is required
and describes the mapping of a dummy argument that is the same as the
actual one. 
A representative example is the passing of the {\sc part} array into 
subroutines:

{\small \sf
\begin{tabbing}
xxxxxxxxxx\=xxxxx\= \kill
\>     !HPF\$ DISTRIBUTE *(*, *, BLOCK) ONTO PRCS :: part
\end{tabbing}
}

{\tt INTENT} attributes are added to the subroutine interfaces to supply the 
compiler with more hints regarding the use of dummy variables inside the 
routine.

\subsection{Extrinsic Procedures}

HPF's {\tt EXTRINSIC} mechanism provides a means of
calling  procedures written in other parallel programming
schemes (such as SPMD) or in other programming languages. We benefited from
this mechanism in two ways. First, it helped us to implement the routines that
cannot be efficiently implemented using HPF's native data parallel constructs.
For example, the Fast Fourier Transform routine involves a great deal 
of permutative
kind of communication where each sender has a unique distinct destination.
This type of patterns can only be efficiently implemented using the
message-passing SPMD style of programming. 
Second, we used extrinsic procedures to simulate the {\tt INDEPENDENT DO} 
statement, when it is ignored by the compiler.

The PGI compiler only allows the use of extrinsics procedures written in 
Fortran 77. We used PGI's own runtime communication library  for 
message passing.
We believe that our implementation is no different than what the compiler
would do to support this statement. Since we used the PGI's own message-passing
library (the other alternative was MPI), the performance figures 
would also be the same.
%DEC compiler supports extrinsics written in HPF and allows using PVM 
%libraries for message passing. 

\subsection{Compiler Restrictions}

The PGI compiler cannot detect nonlinear dependencies in {\tt INDEPENDENT DO}
loops. In the case of a nonlinear dependency,
it assumes the loop is serial and calls {\tt pghpf\_get\_scalar()}, which is a
very expensive communication function.  It actually does an all-to-all
broadcast.
 There are at least two kinds of distributed array references in our code 
that cause the PGI compiler to choose a less efficient implementation strategy 
than needed. 
\begin{itemize}
\item
   Indirect array references such as 
{\small \sf 
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxx\kill
\>\>    part(1,ihole(j+jsl(2,k),k),k) = rbufr(1,j,k)
\end{tabbing}
}
where one array is used to
index another array  prevent communication analysis at compile time  and 
consequently do cause a 
collective communication before the loop. The compiler generates 
{\tt pghpf\_get\_scalar({\sc jsl(2,k)})} calls  to bring the index array 
item to the local processor and then generates another
 {\tt pghpf\_get\_scalar({\sc ihole()})} call for the second indirection.
A third one follows for {\sc part} itself.     
\item
   The array references used in  a conditional expression of a loop body
such as
{\small \sf 
\begin{tabbing}
xxxxxxxxxx\=xxxxx\=xxxxx\=xxxxx\kill
\>\>    if (jsr(1,k) < nbmax) then \\
\>\>\>       sbufl(1,jsl(1,k),k) = part(2,j,k) \\
\>\>    endif
\end{tabbing}
}
  cause the loop to be executed in serial (Surprise!).
\end{itemize}
The compiler has a special flag ({\tt -Mreplicate}) that replicates the
arrays falling into the above two categories on each processor, thus
overriding the distribution directives given in the program.
Individual elements do not have to be brought in as above. Instead, all
the non-local elements of distributed elements may be copied into their 
counterparts before being used. 





