Subject: Local Subroutine proposal

From: [email-masked]
Date: Tue, 16 Jun 92 16:12:15 -0500

Forwarded from Marc Snir...

------- Forwarded Message

Date: Mon, 15 Jun 92 20:07:43 EDT
From: "Marc Snir" <[email-masked]>
To: [email-masked]
Subject: Forwarding note
Reply-To: [email-masked]
Status: RO

- ------------------------------- Referenced Note ---------------------------
%local.tex
%Snir
\documentstyle[11pt]{article}
\pagestyle{plain}
\pagenumbering{arabic}
\marginparwidth 0pt
\oddsidemargin  .25in
\evensidemargin  .25in
\marginparsep 0pt
\topmargin   -.5in
\textwidth 6in
\textheight  9.0in

\title{Proposal for Local Routines}
\author{Marc Snir}
%\date{   }

\begin{document}

\maketitle

\section{Overview}
Local routines are an escape mechanism for allowing to call SPMD code
from an HPF program.  Such mechanism will allow to deal with those
problems that are not dealt efficiently in HPF, and to hand-tune
critical kernels.  In addition, the local routine interface allows to
develop message passing run-time libraries that can be called from HPF.

Local routines are external -- they are not part of the HPF language.   The
local routines need not be necessarily be compiled by the same compiler
that compiles HPF -- although HPF compilers may be able to handle F90
local routines.

The
execution model for local routines is different from the HPF execution model:
Local routines are executed on each processor; they can access on each
processor the local part of distributed arrays; they can use
arbitrary message passing libraries for interprocessor communication. Thus, data
distribution and parallelism are not semantically transparent inside
local routines (this is a reason for their :q.external:eq. status).  However,
if local routine fulfills the requirement listed below,
then the execution
of local routines is semantically equivalent to the execution of an HPF routine.

We describe here an interface to F90 routines
- -- F77 or C routines can be dealt with in a similar manner.

\section{Requirements from the Caller}
\begin{enumerate}
\item
The caller must include an interface definition (in HPF syntax)
for each local routine called.  The local routine is declared with the keyword
LOCAL.  The interface block may contain HPF align/distribute directives for
alignable/distributable arrays.
\item
If the local routine is a function that returns a scalar value then
the corresponding HPF function returns a 1 dimensional array of size
NUMPROC, distributed one element per processor.  If the local function returns
an array of rank $k$ then the corresponding HPF function returns an array of
rank $k+1$ with the leading dimension of size NUMPROC, block distributed
among the processors.
\end{enumerate}
\section{Calling sequence generated by HPF compiler}
\begin{enumerate}
\item
For each nondistributable argument a corresponding name
(of the same type) must be present in each processor.
\item
Compatibility must be enforced between actual and formal parameters in terms of
type, shape, alignment and distribution prior to the call.
\item
Each argument for which an HPF align/distribute directive appears in the
interface block is realigned/redistributed according to the
directive prior to the call (directives are binding in local routine
interfaces!).  The original distribution is restored after the call returns.
\item
If a variable is replicated, then all copies are updated
prior to the call to contain the current value of
the name according to the sequential semantics of the source program.
\item
All processors are synchronized before and after the call.
\item
The local subroutine is called on each processor, with a parameter list
described below.
\item
For each nondistributable dummy argument, the routine is passed
the local copy of the actual argument. For each distributable dummy argument,
the local routine is passed two actual arguments.  The first one is an array
that consists of the local elements of the distributed array.  The second one is
a {\em distributed array descriptor}. (DAD).  The DAD describes the
current distribution of an HPF array.
\end{enumerate}
\section{Requirements from the Callee}
\begin{enumerate}
\item
Arguments are accessed in the conventional manner.
IN/OUT restrictions on them must be obeyed as stated in
the interface.
\item
DAD's are accessed using special functions
described below.  DAD's can be used to access non-local elements of
distributed arrays.
\item
If a value is being returned into a replicated argument, then all
copies must have identical values at the local subroutine(s) return.
\end{enumerate}

The execution of a local routine that fulfills these rules is semantically
equivalent to the execution of an HPF routine, assuming that HPF routines can
query the current distribution of its arguments.
\section{Query and access functions}

These functions can be called from local routines to access and manipulate
HPF arrays.  The list below is not exhaustive.   The first
argument in each call is a DAD.

\begin{verbatim}

    arank(a)       rank of the matrix
    alow(a,k)      lower bound of k-th dimension of matrix
    ahigh(a,k)     upper bound of k-th dimension of matrix

    collapse(a,k)  whether the k-th dimension is collapsed or not

    prank(a)       rank of processor array pa that a is distributed to
    phigh(a,k)     number of processors in the k-th dimension of pa
    preplica(a,k)  whether the k-th dimension of pa is replicated
    pdist(a,k)     distribution type in the k-th dimension (blk,cyc)
    pparam(a,k)    distribution parameter (blk size etc)
    plist(a)       linear list of processors for this matrix

    offset(a,i1,i2,..)  if the (i1,i2,..)-th element of the matrix
                        is located in this processor, return its offset
                        into the data area, else return -1
    pnumber(a,i1,i2,..) processor number where (i1,i2,..)-th element
                        is located
    fetch(a,i1,i2,..,v) fetches (i1,i2,..)-th element of HPF matrix
                        and stores it in v (may involve communication
                        with another processor)
    store(a,i1,i2,..,v) storess the value of v into (i1,i2,...,)-th
                        element of HPF matrix (if element is replicated
                        value is stored in all copies -- may involve
                        communication with other processors)
\end{verbatim}

\section{Sample HPF Programs}

\subsection{Matrix multiplication}

\subsubsection{HPF Code}
\begin{verbatim}

C    The MATMULT routine computes C=A*B.  A copy of row A(I,*) and
C    column B(*,J) is broadcast to the processor that computes C(I,J) before
C    before the call to MATMULT.

        INTERFACE
           LOCAL   SUBROUTINE  MATMULT(A,B,C)
              REAL,  DIMENSION(:,:), INTENT(IN)  ::  A,B
              REAL,  DIMENSION(:,:), INTENT(OUT) ::  C
*HPF$         ALIGN A(I,J) WITH C(I,*)
*HPF$         ALIGN B(I,J) WITH C(*,J)
END SUBROUTINE  MATMULT
        END INTERFACE

   ..............
CALL MATMULT(A,B,C)
   ..............

\end{verbatim}

\subsubsection{Local Subroutine}

\begin{verbatim}

C    Each processor is passed 3 arrays of rank 2.  Assume that the global HPF
C    arrays A,B and C have dimensions LxM, MxN and LxN, respectively.  The
C    local array CC is (a copy of) a rectangular subarray of C.
C    Let I1,I2,...,Ir and J1,J2,...,Js be, respectively, the row and column
C    indices of this subarray at a processor.  Then AA is (a copy of) the
C    subarray of A with row indices I1,...,Ir and column indices 1,...,M; and BB
C    is (a copy of) the subarray of B with row indices 1,...,M and column
C    indices J1,...,Js.   C may be replicated, in which case copies of C(I,J)
C    will be consistently updated at various processors.

     SUBROUTINE  MATMULT(N,AA,DA,BB,DB,CC,DC)
     REAL AA(*,*), BB(*,*), CC(*,*)

C     loop uses local indices

     DO I=LBOUND(CC,1), UBOUND(CC,1)
        DO J=LBOUND(CC,2), UBOUND(CC,2)
           CC(I,J) = SUM(AA(I,:)*BB(:,J))
        END DO
     RETURN
     END

\end{verbatim}

\subsection{Sum Reduction}

\subsubsection{HPF Code}

\begin{verbatim}

C    The SREDUCE routine computes at each processor the sum of the local
C    elements of an array of rank 1.  It returns an array that consists of
C    one sum per processor.  The sum reduction is completed by reducing this
C    array of partial sums.  The function fails if the array is replicated.

        INTERFACE
           LOCAL REAL FUNCTION SREDUCE(A)
              REAL,  DIMENSION(:), INTENT(IN)  ::  A
           END FUNCTION SREDUCE
        END INTERFACE

   .................
TOTAL = SUM(SREDUCE(A))
   ..................

\end{verbatim}

\subsubsection{Local Subroutine}

\begin{verbatim}

     SUBROUTINE  SREDUCE(AA,DA)
     REAL AA(*)

     IF PREPLICA(DA,1)
           THEN CALL ERROR()
           ELSE RETURN(SUM(AA))
     END IF
     END

\end{verbatim}
\section{Miscellany}
\subsection{Common}

If common blocks are distributable in HPF then some mechanism need be provided
for Local routines to access the local slice of a distributed common block.
\end{document}

------- End of Forwarded Message