% {{{  hpf.tex
%--------------------------------------------------------------
% HPF
% ---
% 25 min talk at SERC-funded workshop 'Data parallel languages',
% (organised by Chris Jesshope).
% Lille, Wed 20- Fri 22 April 1994.
%
% To obtain slides (landscape format) do:
%   latex hpf  &&  dvips -x 2000 -o hpf.ps hpf.dvi
%--------------------------------------------------------------
\documentstyle{myslides}
\parskip=1ex
\parindent=0em
%\special{dvitops: landscape}
% {{{  newcommands
\newcommand{\bct}{\begin{center} \begin{tabular}}
\newcommand{\ect}{\end{tabular}  \end{center}}
\newcommand{\bd}{\begin{description}}
\newcommand{\ed}{\end{description}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\bq}{\begin{quote}}
\newcommand{\eq}{\end{quote}}
\newcommand{\bt}{\begin{tabbing}}
\newcommand{\et}{\end{tabbing}}
\newcommand{\bre}{\begin{list}{(\roman{romanctr})}{\usecounter{romanctr}}}
\newcommand{\ere}{\end{list}}

\newcounter{romanctr}	% for roman-enumerated lists ('\bre' and 'ere')

\setlength{\unitlength}{\baselineskip}

\newlength{\templen}
% }}}

\begin{document}

% {{{  title page and contents: 'HPF' -- ok
\vspace*{\fill}
{\centering \Large High Performance Fortran (HPF)	\\}

\vspace{\baselineskip}

{\centering	John Merlin and Bryan Carpenter		\\
		University of Southampton.		\\[\baselineskip]
		Workshop on Data-parallel Languages and Compilers,	\\
		University of Lille,			\\
		20 April 1994.				\\}

\vspace{\baselineskip}

\subsection*{Contents}
\be
	\item Overview of HPF
	\item \mbox{Efficient translation of HPF for
distributed memory systems}
\ee
\vspace*{\fill}

\newpage
% }}}

% {{{  \section*{(1)~~Overview of HPF}
\section*{(1)~~Overview of HPF}

% This HPF Overview stuff is copied from '../europort/hpf.tex',
% with a few changes.

% {{{  \subsection*{Introduction} -- 2 slides
\subsection*{Introduction}
\bi
	\item \mbox{{\bf High Performance Fortran (HPF)}: an informal 
standard} \mbox{for extensions to Fortran~90 to assist its
implementation} on parallel architectures (particularly 
distributed memory), especially for data-parallel computations.

	\item {\em No explicit message-passing\/}!  Instead, specify
{\em data \mbox{distribution}.}

HPF compiler automatically partitions data and inserts message-passing.

	\item HPF model:
	\bi
		\item global name space;
		\item compiles to data parallel SPMD program;
		\item single execution thread {\em except for\/}
functions in \verb@FORALL@, \verb@INDEPENDENT@ loops, `extrinsic' procedures.
	\ei
\newpage

	\item Many extensions, including those for data distribution,
are {\em directives\/}  (i.e.\ structured comments).

Thus HPF should be portable across the whole spectrum of architectures
(SM, DM, SIMD, uni-processor).

	\item \mbox{Developed by the HPFF (HPF Forum), Jan 92 -- May 93.}
\mbox{Over 40 organisations participated.  Significant European input.}

Currently HPF 1.1 development is underway.

	\item \mbox{HPF Spec published in {\em Sci.\ Prog\/}, 
\underline{2} (1), Sept.\ 93.}	\\
Available by ftp from {\bf cs.rice.edu} and elsewhere.
\ei
% }}}
\newpage

% 2nd slide is hand-written, showing 3 level linear mapping:
%  problem, abstract machine & machine mapping

% {{{  \subsection*{Alignment}
\subsection*{Alignment}

{\bf {\tt TEMPLATE} directive:}~~declares abstract array, e.g.:
\begin{verbatim}
  CHPF$ TEMPLATE  T (10),  T2 (10,10)
\end{verbatim}
\settowidth{\templen}{\bf {\tt ALIGN} directive:~~}
{\bf {\tt ALIGN} directive:}~~ declares mapping of array $\rightarrow$
			template or		\\
\hspace*{\templen} another array, e.g.:	\\[0.8\baselineskip]
\verb@  CHPF$ ALIGN  A(I)  WITH  T(I)@		\\[0.3\baselineskip]
\verb@  CHPF$ ALIGN  B(I)  WITH  T(2*I+2)    @
\setlength{\unitlength}{0.8\baselineskip}
\parbox{11.5\unitlength}{		% so piccy centred on line!
	% {{{  picture!
	\begin{picture}(10,1)
	
	\put(0,0){\line(1,0){10}}
	\put(0,1){\line(1,0){10}}
	
	\put(0,0){\line(0,1){1}}
	\put(1,0){\line(0,1){1}}
	\put(2,0){\line(0,1){1}}
	\put(3,0){\line(0,1){1}}
	\put(4,0){\line(0,1){1}}
	\put(5,0){\line(0,1){1}}
	\put(6,0){\line(0,1){1}}
	\put(7,0){\line(0,1){1}}
	\put(8,0){\line(0,1){1}}
	\put(9,0){\line(0,1){1}}
	\put(10,0){\line(0,1){1}}
	
	\put(3,0){\makebox(1,1){{\tt B}$_{1}$}}
	\put(5,0){\makebox(1,1){{\tt B}$_{2}$}}
	\put(7,0){\makebox(1,1){{\tt B}$_{3}$}}
	\put(9,0){\makebox(1,1){{\tt B}$_{4}$}}
	
	\end{picture}
	% }}}
}						\\[0.3\baselineskip]
\verb@  CHPF$ ALIGN  A2(I,J)  WITH  T2(J,I) ! transpose dimensions@	\\[0.3\baselineskip]
\verb@  CHPF$ ALIGN  A2(I,*)  WITH  T(I)    ! 2nd. dim 'collapsed'@	\\[0.3\baselineskip]
\verb@  CHPF$ ALIGN  A(I)  WITH  T2(I,*)    ! 'replicated'@		\\[0.3\baselineskip]
\verb@  CHPF$ ALIGN  A(I)  WITH  T2(I,2)    ! 'embedded'@		\\[0.8\baselineskip]
Also an {\em executable\/} form ({\tt REALIGN})---i.e.\ can perform 
{\em dynamic\/} re-alignment.

% }}}
\newpage

% {{{  \subsection*{Distribution}
\subsection*{Distribution}

{\bf {\tt PROCESSORS} directive:} \mbox{~declares (abstract) processor arrays, 
e.g.:}
\begin{verbatim}
  CHPF$ PROCESSORS P (4),  P2 (4,4)
\end{verbatim}
\settowidth{\templen}{\bf {\tt DISTRIBUTE} directive:~~}
{\bf {\tt DISTRIBUTE} directive:} \mbox{~declares mapping of template or array}\\
\hspace*{\templen} $\rightarrow$ processors, e.g.:	\\[0.8\baselineskip]
\verb@  CHPF$ DISTRIBUTE  T (BLOCK) ONTO P ! distrib elems in blocks@
							\\[0.3\baselineskip]
\verb@  CHPF$ DISTRIBUTE  T (CYCLIC)       ! distrib elems cyclically@
							\\[0.3\baselineskip]
\verb@  CHPF$ DISTRIBUTE  T (CYCLIC (2))   ! distrib blocks of 2@	\\
\verb@                                     ! elements cyclically@
							\\[0.3\baselineskip]
\verb@  CHPF$ DISTRIBUTE  T (*)            ! not distributed@
							\\[0.3\baselineskip]
\verb@  CHPF$ DISTRIBUTE  T2 (BLOCK, CYCLIC) ONTO P2@	\\[0.8\baselineskip]
Also an {\em executable\/} form ({\tt REDISTRIBUTE})---i.e.\ can perform \\
{\em dynamic\/} re-distribution.

% }}}
\newpage

% {{{  \subsection*{Concurrent execution features}
\subsection*{Concurrent execution features}

\mbox{{\bf {\tt FORALL} statement and construct:}~~a data parallel `loop', e.g.:}
% RHS is fully evaluated, for all index values, before assignment, e.g.:
\begin{verbatim}
  FORALL (i = 2:9) A(i) = 0.5*(A(i-1) + A(i+1))
\end{verbatim}

{\bf {\tt PURE} functions and subroutines:}	
\mbox{~~~Defined} to be side-effect free, so can be executed 
concurrently, e.g.\ in \verb@FORALL@.	\\
\mbox{~~~~~Hence can get `MIMD parallelism' over array elements, e.g.:}
\begin{verbatim}
  PURE INTEGER FUNCTION itns (c)
    COMPLEX, INTENT (IN) :: c;   COMPLEX :: z = c
    itns = 0
    DO WHILE (ABS (z) < 2.0  .AND.  itns < 100)
      z = z*z + c
      itns = itns + 1
    ENDDO
    IF (ABS (z) < 2.0) itns = -1
  END FUNCTION itns
  ...
  FORALL (i=1:m,j=1:n) mandel(i,j) = itns (CMPLX(.1*i, .1*j))
\end{verbatim}

\newpage

\mbox{{\bf {\tt INDEPENDENT} directive:} ~~asserts that iterations of a 
\verb@DO@-loop} or \verb@FORALL@ are data independent, and so can be 
executed \mbox{concurrently}.  E.g.:
\begin{verbatim}
  CHPF$ INDEPENDENT, NEW (s)
        DO i = 1, 100
          s = b(i-1) + b(i+1)
          CALL sub (a(i), s)
        ENDDO
\end{verbatim}
% }}}
\newpage

% {{{  \subsection*{HPF intrinsics} & {HPF standard library}
\subsection*{HPF intrinsics}

\bi
	\item system inquiry functions: \verb@NUMBER_OF_PROCESSORS ([DIM])@
and \verb@PROCESSORS_SHAPE ()@.  These query the physical (not abstract) 
machine, and can be used in declarations.
	\item computational intrinsic: \verb@ILEN (I)@;
	\item extensions to Fortran~90 intrinsics \verb@MAXLOC@ and 
\verb@MINLOC@.
\ei

\subsection*{HPF standard library}

Obtained from a module:~~\verb@USE HPF_LIBRARY@.
\bi
	\item combining-scatter functions; ~~parallel prefix/suffix 
\mbox{functions}; ~~sorting functions; ~~bit operation functions.
	\item mapping inquiry subroutines:
\begin{verbatim}
 HPF_ALIGNMENT (ARRAY, [LB, UB, STRIDE, AXIS_MAP, ...])
 HPF_TEMPLATE  (ARRAY, [TEMPLATE_RANK, LB, UB, ...])
 HPF_DISTRIBUTION (ARRAY, [AXIS_TYPE, AXIS_INFO, ...])
\end{verbatim}
\ei
% }}}
\newpage

% {{{  \subsection*{Extrinsic procedures}
\subsection*{Extrinsic procedures}

Can call non-HPF procedures ({\em extrinsic procedures\/}) from
an HPF program, e.g.\ for message-passing, assembly or other non-Fortran 
language programming, etc.

Generally not portable.

% }}}
\newpage

% {{{  \subsection*{Restrictions on sequence and storage association}
\subsection*{\mbox{Restrictions on sequence and storage association}}

\setlength{\unitlength}{0.8\baselineskip}
\settowidth{\templen}{\tt ~~~~~~COMMON~/com/~a(100),~b(100)~~~~~~}

\mbox{{\em Sequence association\/}: equivalencing arrays via 
\verb@EQUIVALENCE@ \& \verb@COMMON@:}	\\[0.7\baselineskip]
%
% {{{  example:  code & diagrams
\parbox{\templen}{\tt
\mbox{~~~~SUBROUTINE~s1}		\\
\mbox{~~~~~~REAL~x(100)}		\\
\mbox{~~~~~~COMMON~/com/~a(100),~b(100)}	\\
\mbox{~~~~~~EQUIVALENCE~(x(1),~a(50))}	\\
\mbox{~~~~~~...}}
\parbox{10\unitlength}{		% so piccy centred on line!
	% {{{  picture!
	\begin{picture}(10,2)
	
	\put(2.5, 0){\line(1,0){5}}
	\put(0,1){\line(1,0){10}}
	\put(0,2){\line(1,0){10}}
	
	\put(2.5, 0){\line(0,1){1}}
	\put(7.5, 0){\line(0,1){1}}
	\put(0, 1){\line(0,1){1}}
	\put(5, 1){\line(0,1){1}}
	\put(10,1){\line(0,1){1}}
	
	\put(4.5, 0){\makebox(1,1){\tt x}}
	\put(2, 1){\makebox(1,1){\tt a}}
	\put(7, 1){\makebox(1,1){\tt b}}
	
	\end{picture}
	% }}}
}					\\[0.3\baselineskip]
\parbox{\templen}{\tt
\mbox{~~~~SUBROUTINE~s2}		\\
\mbox{~~~~~~COMMON~/com/~d~(200)}}
\parbox{10\unitlength}{		% so piccy centred on line!
	% {{{  picture!
	\begin{picture}(10,2)
	
	\put(0,0){\line(1,0){10}}
	\put(0,1){\line(1,0){10}}
	\put(0,2){\line(1,0){10}}
	
	\put(0,0){\line(0,1){2}}
	\put(10,0){\line(0,1){2}}
	\put(5,1){\line(0,1){1}}
	
	\put(4.5, 0){\makebox(1,1){\tt d}}
	\put(2, 1){\makebox(1,1){\tt a}}
	\put(7, 1){\makebox(1,1){\tt b}}
	
	\end{picture}
	% }}}
}					\\[0.7\baselineskip]
% }}}
%
\mbox{{\em Storage association\/}: sectioning / reshaping arrays via 
proc arguments:}			\\[0.7\baselineskip]
%
% {{{  example:  code & diagram
\addtolength{\templen}{-\unitlength}
\parbox{\templen}{\tt
\mbox{~~~~~~REAL~a(5,5)}	\\
\mbox{~~~~~~CALL~s~(~a(2,2)~)}	\\
\mbox{~~~~~~...}		\\
\mbox{~~~~SUBROUTINE~s~(v)}	\\
\mbox{~~~~~~REAL~v(5)}}
\parbox{6\unitlength}{		% so piccy centred on line!
	% {{{  picture!
	\begin{picture}(6,5)
	
	\put(1,0){\line(1,0){5}}
	\put(1,1){\line(1,0){5}}
	\put(1,2){\line(1,0){5}}
	\put(1,3){\line(1,0){5}}
	\put(1,4){\line(1,0){5}}
	\put(1,5){\line(1,0){5}}
	
	\put(1,0){\line(0,1){5}}
	\put(2,0){\line(0,1){5}}
	\put(3,0){\line(0,1){5}}
	\put(4,0){\line(0,1){5}}
	\put(5,0){\line(0,1){5}}
	\put(6,0){\line(0,1){5}}
	
	\put(0,4){\makebox(1,1){\tt a}}
	\put(3,2){\makebox(1,1){{\tt v}$_{1}$}}
	\put(4,2){\makebox(1,1){{\tt v}$_{2}$}}
	\put(5,2){\makebox(1,1){{\tt v}$_{3}$}}
	\put(1,1){\makebox(1,1){{\tt v}$_{4}$}}
	\put(2,1){\makebox(1,1){{\tt v}$_{5}$}}
	
	\end{picture}
	% }}}
}					\\[0.7\baselineskip]
% }}}
%
Difficult to support this for distributed arrays in HPF, so:
\vspace{-0.4\baselineskip}
\bi
	\item \mbox{\verb@SEQUENCE@ directive must declare arrays 
subject to these assocs;}\vspace{-0.2\baselineskip}
	\item there are restrictions on distribution.
\ei
% }}}
\newpage

% {{{  \subsection*{Subset HPF}
\subsection*{Subset HPF}

\mbox{An official subset of HPF has been defined for fast implementation.}
It comprises:
\bd
	\item[a Fortran~90 subset,] \mbox{which is (roughly) all of Fortran~77
plus \ldots}
	\bi
		\item non-character array syntax;
		\item all new Fortran~90 intrinsics;
		\item procedure interface blocks;
		\item \mbox{`cleaner' syntax features (MIL 1753), e.g.\
\verb@DO WHILE@, \verb@ENDDO@;}
		\item lexical improvements \& new declaration forms.
	\ei

	\item[all HPF extensions {\em except\/}] (roughly speaking) \ldots
	\bi
		\item dynamic realignment \& redistribution;
		\item \verb@PURE@ procedures;
		\item \verb@FORALL@ constructs (but not statements!);
		\item the \verb@HPF_LIBRARY@ module;
		\item the \verb@EXTRINSIC@ mechanism.
	\ei
\ed
% }}}
\newpage


% }}}

% {{{  \section*{(2)~`Efficient translation of HPF for \mbox{distributed} memory systems'}
\section*{\mbox{(2)~`Efficient translation of HPF for~~~~~~~~~~~~~~~~~~} \mbox{~~~~~~distributed memory systems'}}

% {{{  \subsection*{Introduction} -- ok
\subsection*{Introduction}

2 year SERC-funded project, starting 1 April 1994, in \mbox{collaboration}
with NAG Ltd.

Objectives:
\bi
	\item \mbox{To develop optimisation techniques for HPF, in
particular:}
	\bi
		\item efficient placement of calculations;
		\item efficient organisation of communications.
	\ei
	\item To implement this research in a Subset HPF 
\mbox{compilation} system (i.e. translator + communications library).
\ei

Also, JISC-funded project (Jan--Dec 94) to develop runtime library 
for the system.

\newpage

% }}}
% {{{  \subsection*{Overview of Subset HPF compilation system} -- ok
\subsection*{Overview of Subset HPF compilation system}

Based on further development of the `ADAPT' system,
\mbox{developed} at Southampton over the last few years.
\vspace{0.8\baselineskip}
{\small
\begin{center}
\begin{picture}(20,10)
\setlength{\unitlength}{\baselineskip}

\put(7,8){\makebox(5,2){\small Subset HPF}}
\put(9.5,9){\oval(5,2)}

\put(9.5,8){\vector(0,-1){2}}

{\thicklines
\put(7,4){\framebox(5,2){\shortstack{\small\bf ADAPT \\ translator}}}
}

\put(9.5,4){\vector(0,-1){2}}

{\thicklines
\put(0,0){\makebox(5,2){\shortstack{\small\bf Host I/O \\ server}}}
\put(2.5,1){\oval(5,2)}
}

\put(7,0){\makebox(5,2){\shortstack{\small F90 node \\ program}}}
\put(9.5,1){\oval(5,2)}

\put(14,1){\vector(-1,0){2}}

{\thicklines
\put(14,0){\makebox(6,2){\shortstack{\small \bf ADLIB \\ comms library}}}
\put(17,1){\oval(6,2)}
}
\end{picture}
\end{center}
}
\mbox{`ADLIB' will contain high-level, array-based comms routines}	\\
\mbox{(e.g.\ data remapping operations, gather-scatter, \ldots).}

Message-passing implemented in PVM (and later MPI?).

Plan initial release end of 1994; optimised version at end of project.

\newpage
% }}}
% {{{  \subsection*{Efficient calculation placement} -- ok
\subsection*{Efficient calculation placement}

HPF defines the distribution of {\em data\/}, but not of {\em calculation\/}.

\vspace{0.5\baselineskip}

\mbox{The {\em `owner computes'\/} heuristic is widely used.
However, it is}	\\
\mbox{often inefficient in comms, temporary storage and processor use.}  E.g.:
\begin{verbatim}
CHPF$ ALIGN WITH A(I) :: B(I), C(I), D(I)
      A(1) = B(9) + C(9) + D(9)     ! each RHS element
                                    ! copied to home (A(1))

CHPF$ DISTRIBUTE D1 (BLOCK), D2 (BLOCK), R (*)
      R(:) = D1(:) + D2(:)          ! D1 & D2 copied to 
                                    ! all processors.
\end{verbatim}
Also, it gives no guidance if expression is not RHS of an \mbox{assignment},
e.g.: ~~output item, ~~actual argument, ~~\verb@IF@ condition, \ldots

\newpage
% }}}

% Bryan's slides ??...

% {{{  \subsection*{Efficient communications management}
\subsection*{Efficient communications management}

The placement of data and calculations determines what data 
communications are required.

Organising these comms efficiently is a complex matter.  E.g:
\bi
	\item Consider simple shift of unknown size:
\begin{verbatim}
  A(i:j) = ... + B(i+n:j+n) + ...
\end{verbatim}
\vspace{-0.5\baselineskip}
\setlength{\unitlength}{\baselineskip}
\begin{center}
% {{{  
\begin{picture}(20,5)

{\thicklines
\put(5,2){\line(1,0){15}}
\put(5,3){\line(1,0){15}}
\put(5,4){\line(1,0){15}}

\put(5,2){\line(0,1){2}}
\put(20,2){\line(0,1){2}}

\put(7,3){\line(0,1){1}}
\put(13,3){\line(0,1){1}}

\put(10,2){\line(0,1){1}}
\put(16,2){\line(0,1){1}}
}
% hash in the boxes for sections A(i:j) and B(i+n:j+n)

{\thinlines
\put( 7  , 3.5){\line(1,1){.5}}
\put( 7  , 3  ){\line(1,1){1}}
\put( 7.5, 3  ){\line(1,1){1}}
\put( 8  , 3  ){\line(1,1){1}}
\put( 8.5, 3  ){\line(1,1){1}}
\put( 9  , 3  ){\line(1,1){1}}
\put( 9.5, 3  ){\line(1,1){1}}
\put(10  , 3  ){\line(1,1){1}}

\put(10  , 2.5){\line(1,1){1.5}}
\put(10  , 2  ){\line(1,1){2}}
\put(10.5, 2  ){\line(1,1){2}}
\put(11  , 2  ){\line(1,1){2}}
\put(11.5, 2  ){\line(1,1){1.5}}
\put(12  , 2  ){\line(1,1){1}}
\put(12.5, 2  ){\line(1,1){1}}
\put(13  , 2  ){\line(1,1){1}}
\put(13.5, 2  ){\line(1,1){1}}
\put(14  , 2  ){\line(1,1){1}}
\put(14.5, 2  ){\line(1,1){1}}
\put(15  , 2  ){\line(1,1){1}}
\put(15.5, 2  ){\line(1,1){.5}}

% dashed processor lines

\put( 5,0){\dashbox{.3}(0,4){}}
\put( 8,0){\dashbox{.3}(0,4){}}
\put(11,0){\dashbox{.3}(0,4){}}
\put(14,0){\dashbox{.3}(0,4){}}
\put(17,0){\dashbox{.3}(0,4){}}
\put(20,0){\dashbox{.3}(0,4){}}
}

% labelling

\put(0,3){\makebox(4.5, 1)[r]{\tt A}}
\put(0,2){\makebox(4.5, 1)[r]{\tt B}}
\put(0,0){\makebox(4.5, 1)[rb]{\it processor no.\/}}

\put(6, 0){\makebox(1,1)[b]{$p_1$}}
\put(9, 0){\makebox(1,1)[b]{$p_2$}}
\put(12,0){\makebox(1,1)[b]{$p_3$}}
\put(15,0){\makebox(1,1)[b]{$p_4$}}
\put(18,0){\makebox(1,1)[b]{$p_5$}}

\put( 6.5, 4){\makebox(1,1){\tt i}}
\put(12.5, 4){\makebox(1,1){\tt j}}

\put( 9.5,1){\makebox(1,1){\tt i+n}}
\put(15.5,1){\makebox(1,1){\tt j+n}}

\end{picture}
% }}}
\end{center}
2 possible schemes:
\bre
	\item collective shift into temporary of same size as 
whole local segment of \verb@B@~~~({\em but\/} may involve local copying);
	\item \mbox{generate code with branches to perform most efficient}
\mbox{comms for every case~~~({\em but\/} complex control flow \& tests).}
\ere
\ei

\newpage

\bi
	\item If shift is of known (small) size:
\begin{verbatim}
  A(i:j) = ... + B(i+1:j+1) + ...
\end{verbatim}
can just shift data required (without local copying), and partition 
the assignment into {\em local\/} and {\em non-local\/} parts.

Destination of communicated data can be:
	\bre
		\item temporary array;
		\item overlap area in \verb@B@.
	\ere

	\item Overlap scheme is most efficient, but requires:
	\bi
		\item access patterns fairly local, and known statically;
		\item global analysis of {\em all\/} accesses to array.
	\ei
Can it be generalised?
\ei

% }}}

% }}}

\end{document}

% }}}
