\documentclass{article}

\begin{document}


\section{Program transformation}

Program transformation phase can be done through traveling along the
parse tree again. During the second pass, different kind of operations
are carried on the intermediate representation of the source program.
In the end, unparse the modified intermediate representation, the node
program will be generated.


\subsection{Memory management}

Before discussing the actual translation for different language
components in details, it is neces sary to introduce the memory
strategy we intend to use in the node program.


\subsubsection{Temporary memory}

At present time, PCRC runtime library is based on standard Fortran 77
interface. Dynamic alloca tion of memory is not allowed. For memory
operation during the execution of the node program, a huge memory
chuck is set with common data block as memory stack. We only use the
stack for temporary memory allocation when communication is involved,
while statically allocate parti tioned array on each node processor.

The basic idea of using temporary memory can be illustrated through
the following example:

if in a program, we have

\begin{verbatim}
      A=B+C
\end{verbatim}

and remap communication is needed in the assignment, then the
temporary memory will be allo cated for array B and C, as tempB and
tempC from the memory stack mentioned above.

The temporary memory was looked as if their corresponding array
element is aligned and distrib uted the same way as the element in the
array A, and runtime function will be called to generate DAD for them.

Then a runtime function will be called to map B in tempB and C in
tempC respectively, after which the computation can be carried out
without communication.

Finally the temporary memory are returned to the stack.

The actual size of the temporary memory located is decided by the
element size and template array on which the array A is aligned to. It
can be calculated from runtime functions according to the DAD of the
array A.


\subsubsection{Memory access linearization}

For unified access of the memory, during the transformation
multi-dimension array is changed to one dimension array in the finial
node program. Explicit address calculation will be added.

This simplifies the translation of interface between procedure calls.
All information needed for an array dummy when calling a procedure is
the array address, which is referenced as an array name in Fortran
language, and the DAD handle.

\subsubsection{Ghost area}

Usually, when communication is needed, a temporary memory is
allocated. But as we noticed in the previous, if the communication is
of shift pattern, using ghost area will be a more effective way. As we
draw in the figure, the shadowed part, as ghost area of the array,
will be allocated along with the partitioned array.

In this way, when shift communication is needed, only array elements
in the edge will be moved among processors. The amount of data to be
sent and received will be much less than the one in remap
communication. In addition there is no additional memory operation
overhead, since the memory used is already allocated.

Currently, the runtime functions do not support this feature yet, a
tshift is used instead, which also need memory allocation, but have
fast execution compared with remap. We are working to improve this
part.

\subsection{Translating different language components}

In HPF language, the following parts need to be taken care of during
the transformation,

\begin{itemize}
\item DAD generation for distributed data

\item Expressions and assignment

\item Program execution control

\item Input and output

\item Procedures

\end{itemize}


These parts are corresponding to HPF data mapping directives, chapter
7, 8, 9 and chapter 12 in Fortran 95 language specification
respectively.

From the implementation point of view, most of the transformation
needed to deal with each part can be subdivided as two phases: format
transformation and node program generation.

In format transformation, the components of the actual source program
is changed, making them suitable for being further processed while
keeping the semantics meaning. The language features encountered in
the second phase will be narrowed down.

For example:
\begin{verbatim}
      A=B       
\end{verbatim}

can be changed into

\begin{verbatim}
      FORALL (tempI=1:n)        A(tempI)=B(tempI) 
\end{verbatim}

therefor the array assignment can be treated unanimously as forall
statement in the next phase.

Other transformation similar to this kind may include:
\begin{itemize}
\item where construct (using forall mask expression)
\item array section in assignment and input/output 
\item simplified data mapping directives
\item array element used as scalar variable
\end{itemize}

Since the change keeps the semantics of the original program
unchanged, it is also possi ble to further divide the whole process as
different small parts, with each of them takes care of a particular
issue in format transformation. This method helps us separate the
transformation pro gram as different modules, implemented and tested
independently.

The program generation phase carries out the actual transformation
work and generating the node program. In the following, we will use
simple examples to illustrate the translations done for dif ferent
language components. For simplification, the examples used only have
one-dimension array.  The DAD support array section, the translation
scheme introduced here can be easily generalized to deal with the
multi-dimension arrays. It has already been implemented in our frame
work of the HPF compiler.


\subsubsection{DAD generation}

Given the follow HPF program 

\begin{verbatim}
      PROGRAM MAIN 
      REAL X(-17:190), Y(-75:221) 
!HPF$ PROCESSORS P(4) 
!HPF$ TEMPLATE TX(-238:3373),TY(-227:3384) 
!HPF$ DISTRIBUTE TX(BLOCK) ONTO P 
!HPF$ DISTRIBUTE TY(BLOCK) ONTO P 
!HPF$ ALIGN X(i) WITH TX(3*i+7) 
!HPF$ ALIGN Y(i) WITH TY(3*i+9) 
\end{verbatim}

will be changed to:

\begin{verbatim}
      pcrc_shp_P(1) = 4
      pcrc_grp_P = pcrc_new_group_grid (1,pcrc_shp_P)
      pcrc_rng_TY(1) = pcrc_new_range_distribute ((-227),3384,1,pcrc_grp&
     &_P,1)
      pcrc_rng_TX(1) = pcrc_new_range_distribute ((-238),3373,1,pcrc_grp&
     &_P,1)
      pcrc_dad_Y = pcrc_new_array_data (Y,pcrc_real,pcrc_size_real,1,pcr&
     &c_grp_P)
      call pcrc_set_array_align (pcrc_dad_Y,1,(-75),221,3,9,pcrc_rng_TY(&
     &1))
      pcrc_dad_X = pcrc_new_array_data (X,pcrc_real,pcrc_size_real,1,pcr&
     &c_grp_P)
      call pcrc_set_array_align (pcrc_dad_X,1,(-17),190,3,7,pcrc_rng_TX(&
     &1))
\end{verbatim}

We can summarize this part as following:

For each processor array, a {\em grp} value will be created with
corresponding processor shape; For each template, a {\em rng} value will be
created to record its distribution code, distribution stride and
offset.  For each partitioned array, a {\em dad} value will be created to
record its shape and its alignment stride and offset, this is the DAD
handle for this array.

Note the generated name used in this report mainly have three parts.
The pcrc is used as a prefix to indicate this is a PCRC run-time
function. Followed by the name of variables or functions, such as {\tt
  grp}, {\tt rng}, \texttt{dad} and \texttt{set\_array\_align}. Finally,
if needed a tag is used to indicate where the name come from.


\subsubsection{Expressions and assignment}

As we said previously, some fundamental work has already been done in
the format transformation phase, the major subject in this part is to
deal with forall statement and scalar assignment.

For a forall statement, we explain the translation in case of no
communication, shift and remap with examples separately.

We still use the same program header in previous example, a forall
statement like:

\begin{verbatim}
      FORALL (i=-7:190:4) X(i) = Y(1*i+3) + Y(1*i+3) 
\end{verbatim}

does not need communication, so the corresponding node program will be:

\begin{verbatim}
      pcrc_irg0 = pcrc_new_range_loop ((-7),190,4,1,0,pcrc_rng (pcrc_dad&
     &_X,1))
      call pcrc_loop_bounds (pcrc_irg0,pcrc_lil_i,pcrc_liu_i,pcrc_lis_i)
      call pcrc_coef (pcrc_dad_X,1,(-7),190,4,1,0,0,pcrc_u00,pcrc_v00)
      pcrc_sdd0 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_sdd0,1,(-7),190,4,pcrc_dad_X,1)
      call pcrc_coef (pcrc_dad_Y,1,(-7),190,4,1,3,0,pcrc_u10,pcrc_v10)
      call pcrc_coef (pcrc_dad_Y,1,(-7),190,4,1,3,0,pcrc_u20,pcrc_v20)
      if (pcrc_on (pcrc_grp (pcrc_sdd0))) then
         do  i=0,(pcrc_liu_i-pcrc_lil_i)/pcrc_lis_i,1
            pcrc_sdx2 = (pcrc_v20+pcrc_u20*i)*pcrc_str (pcrc_dad_Y,1)
            pcrc_sdx1 = (pcrc_v10+pcrc_u10*i)*pcrc_str (pcrc_dad_Y,1)
            pcrc_sdx0 = (pcrc_v00+pcrc_u00*i)*pcrc_str (pcrc_dad_X,1)
            X(pcrc_sdx0) = Y(pcrc_sdx1)+Y(pcrc_sdx2)
         enddo
      endif
      call pcrc_delete_array (pcrc_sdd0)
      call pcrc_delete_range (pcrc_irg0)
\end{verbatim}

In this part of the node program segment, the local loop bounds lil,
liu, lis is calculated out first according to the forall index range
and the DAD of the LHS. Run time function coef is called to get the
address coefficient for each array dimension, which later are used to
collate the local address in the array reference. To make sure the
calculation is needed on the current processor, an if statement is
inserted. This is optional in main program but necessary in any
procedures, since the LHS may be a dummy whose actual argument is an
array section.

And finally, the destructor of the temporary value is called. 

The computation is carried by 

\begin{verbatim}
      X(pcrc_sdx0) = Y(pcrc_sdx1)+Y(pcrc_sdx2)
\end{verbatim}

And we can see there is no need to exchange data among the processors.

If we have the program header as:

\begin{verbatim}
      PROGRAM MAIN 
      REAL X(-98:197), Y(-47:390) 
!HPF$ PROCESSORS P(4) 
!HPF$ TEMPLATE TX(-199:473),TY(-95:786) 
!HPF$ DISTRIBUTE TX(CYCLIC) ONTO P 
!HPF$ DISTRIBUTE TY(CYCLIC) ONTO P 
!HPF$ ALIGN X(i) WITH TX(2*i+5) 
!HPF$ ALIGN Y(i) WITH TY(2*i+0) 
\end{verbatim}

and a forall statement like:

\begin{verbatim}
      FORALL (i=-8:190:3) X(i) = Y(1*i+4
\end{verbatim}

it will cause both shift and remap communication. The corresponding
translation of the forall statement is:

\begin{verbatim}
      pcrc_irg0 = pcrc_new_range_loop ((-8),190,3,1,0,pcrc_rng (pcrc_dad&
     &_X,1))
      call pcrc_loop_bounds (pcrc_irg0,pcrc_lil_i,pcrc_liu_i,pcrc_lis_i)
      call pcrc_coef (pcrc_dad_X,1,(-8),190,3,1,0,0,pcrc_u00,pcrc_v00)
      pcrc_sdd0 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_sdd0,1,(-8),190,3,pcrc_dad_X,1)
      call pcrc_coef (pcrc_dad_Y,1,(-8),190,3,1,4,3,pcrc_u10,pcrc_v10)
      pcrc_sdd1 = pcrc_new_array_section (1,pcrc_dad_Y)
      call pcrc_set_array_triplet (pcrc_sdd1,1,(-4),194,3,pcrc_dad_Y,1)
      pcrc_tdd1 = pcrc_new_array_section (1,pcrc_dad_Y)
      call pcrc_set_array_triplet (pcrc_tdd1,1,(-4),194,3,pcrc_dad_Y,1)
      pcrc_tbs1 = pcrc_real_alloc (pcrc_size (pcrc_tdd1))
      call pcrc_reset_array_base (pcrc_tdd1,pcrc_real_stack(pcrc_tbs1))
      call pcrc_tshift (pcrc_real_stack(pcrc_tbs1),pcrc_sdd1,1,3)
      pcrc_sdd2 = pcrc_new_array_section (1,pcrc_dad_Y)
      call pcrc_set_array_triplet (pcrc_sdd2,1,(-15),381,6,pcrc_dad_Y,1)
      pcrc_tdd2 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_tdd2,1,(-8),190,3,pcrc_dad_X,1)
      pcrc_tbs2 = pcrc_real_alloc (pcrc_size (pcrc_tdd2))
      call pcrc_reset_array_base (pcrc_tdd2,pcrc_real_stack(pcrc_tbs2))
      call pcrc_remap (pcrc_tdd2,pcrc_sdd2)
      if (pcrc_on (pcrc_grp (pcrc_sdd0))) then
         do  i=0,(pcrc_liu_i-pcrc_lil_i)/pcrc_lis_i,1
            pcrc_sdx1 = (pcrc_v10+pcrc_u10*i)*pcrc_str (pcrc_sdd1,1)
            pcrc_sdx0 = (pcrc_v00+pcrc_u00*i)*pcrc_str (pcrc_dad_X,1)
            X(pcrc_sdx0) = pcrc_real_stack(pcrc_tbs1+pcrc_sdx1)+pcrc_rea&
     &l_stack(pcrc_tbs2+pcrc_sdx0)
         enddo
      endif
      call pcrc_real_free (pcrc_tbs2)
      call pcrc_delete_array (pcrc_tdd2)
      call pcrc_delete_array (pcrc_sdd2)
      call pcrc_real_free (pcrc_tbs1)
      call pcrc_delete_array (pcrc_tdd1)
      call pcrc_delete_array (pcrc_sdd1)
      call pcrc_delete_array (pcrc_sdd0)
      call pcrc_delete_range (pcrc_irg0)
\end{verbatim}

The node program segment bears some similarity with the former one,
except temporary memory need to be allocated, the \emph{tbs} value are
used as the pointer to the temporary memory in the stack, and
\emph{tdd} is their corresponding DAD handler. Run time function
"\texttt{alloc}" is called to obtain the memory, and was dellocated
with runtime "\texttt{free}" function in a reverse order after the
computation is done.

The computation is carried out by,

\begin{verbatim}
      X(pcrc_sdx0) = pcrc_real_stack(pcrc_tbs1+pcrc_sdx1)+pcrc_rea&
     &l_stack(pcrc_tbs2+pcrc_sdx0)
\end{verbatim}

The data accessed in the stack is prepared by the runtime function
tshift and remap according to corresponding to DAD handler.

Since the run time function did not support the ghost area yet, the
shift communication also need temporary array allocation.

For a scalar assignment, if we have

\begin{verbatim}
      REAL sclr
\end{verbatim}

in the node program, a \emph{dad} value will also be created for it
whenever necessary,

Then for an assignment like,

\begin{verbatim}
      sclr=X(3)
\end{verbatim}

will be translated to:

\begin{verbatim}
      pcrc_sdd1 = pcrc_new_array_section (0,pcrc_dad_X)
      call pcrc_set_array_scalar (pcrc_sdd1,3,pcrc_dad_X,1)
      pcrc_tdd1 = pcrc_new_array_copy (pcrc_real_stack,pcrc_dad_sclr)
      pcrc_tbs1 = pcrc_real_alloc (pcrc_size (pcrc_tdd1))
      call pcrc_reset_array_base (pcrc_tdd1,pcrc_real_stack(pcrc_tbs1))
      call pcrc_remap (pcrc_tdd1,pcrc_sdd1)
      sclr = pcrc_real_stack(pcrc_tbs1)
      call pcrc_real_free (pcrc_tbs1)
      call pcrc_delete_array (pcrc_tdd1)
      call pcrc_delete_array (pcrc_sdd1)
\end{verbatim}

The remap function is used here to broadcast the array element to
temporary memory located on every processors. Then the assignment is
from the temporary memory to the scalar.

Another situation need to take care of is when forall index used as a
reference in the forall assign ment, local-to-global index
transformation is needed.


\subsubsection{Program execution control}

In this part, the compiling strategy for independent do is beyond the
scope of this report, so there is nothing special need to be done for
the IF construct, CASE construct, DO construct, and CON TINUE
statement, STOP statement.

If a statement is labeled in source program, we can put a labeled
continue statement before the cor responding translation part in the
node program, for example, if the in previous example the assign
statement is labeled as

\begin{verbatim}
100   sclr=X(3)
\end{verbatim}

then we may add

\begin{verbatim}
100   continue
\end{verbatim}

before the translated node program segment for the original assign
statement. Therefor, the branching in execution control won't need any
special translation either.


\subsubsection{Input and output}

The translation for the input and output statement is quite similar to
the one for forall statement.  The implied do loop index is treated
the same way as the forall index. For example,

\begin{verbatim}
      PRINT 111, (X(i),i=-98,197) 
111   FORMAT(1x,f17.2) 
\end{verbatim}

will be translated as:

\begin{verbatim}
      pcrc_sdd0 = pcrc_new_array_section (1,pcrc_dad_X)
      call pcrc_set_array_triplet (pcrc_sdd0,1,(-98),197,1,pcrc_dad_X,1)

      pcrc_tdd0 = pcrc_new_array_data (pcrc_real_stack,pcrc_real,pcrc_si&
     &ze_real,1,pcrc_group_root)
      call pcrc_set_array_collapse (pcrc_tdd0,1,0,295)
      pcrc_tbs0 = pcrc_real_alloc (pcrc_size (pcrc_tdd0))
      call pcrc_reset_array_base (pcrc_tdd0,pcrc_real_stack(pcrc_tbs0))
      call pcrc_remap (pcrc_tdd0,pcrc_sdd0)
      if (pcrc_on (pcrc_group_root)) then
        print 111, (pcrc_real_stack(pcrc_tbs0+i), i=0,295)
      endif
      call pcrc_real_free (pcrc_tbs0)
      call pcrc_delete_array (pcrc_tdd0)
      call pcrc_delete_array (pcrc_sdd0)
111      format (1X,F17.2)
\end{verbatim}

Unlike the forall statement, the temporary array is allocated as the
array section to be printed is replicated on each processor. After the
remap communication, each processor will acquire a copy of the array
section, though only root processor will execute the following print
statement.

Here remap function is used as a multi-gather operation, though only
one copy of the data moved to the rood processor will be enough. A
little overhead is involved, we don't think it will have much effect
on the performance.

\subsubsection{Procedures}

The procedure transformation of the program also has similarity with
forall statement. We can think the dummy array as LHS and actual array
as RHS. Detecting communication introduced pre viously can also used
here. The DAD needed to do communication can be generated according to
the procedure interface. So the caller can map the data needed by the
callee.

\begin{verbatim}
      CALL FOO(X(-75:194:1),Y(-49:821:3)) 
\end{verbatim}

will change to,

\begin{verbatim}
        pcrc_sdd1 = pcrc_new_array_section (1,pcrc_dad_X)
        call pcrc_set_array_triplet (pcrc_sdd1,1,(-75),194,1,pcrc_dad_X,1)
        pcrc_sdd2 = pcrc_new_array_section (1,pcrc_dad_Y)
        call pcrc_set_array_triplet (pcrc_sdd2,1,(-49),821,3,pcrc_dad_Y,1)
        call FOO (X(0),pcrc_sdd1,Y(0),pcrc_sdd2)
        call pcrc_delete_array (pcrc_sdd2)
        call pcrc_delete_array (pcrc_sdd1)
\end{verbatim}
if there is no communication needed for a data mapping provided in
proceduer interface. We can see that the DAD handle are also put into
the actrul argument list.

Now we can see the callee part of the procedure. If a procedure
defined as,

\begin{verbatim}
      SUBROUTINE FOO(X,Y) 
      REAL X(:), Y(:) 
!HPF$ INHERIT X,Y 

      (execution part ... )

      END
\end{verbatim}

Then it will be translated as,

\begin{verbatim}
      subroutine FOO(X, pcrc_dad_X, Y, pcrc_dad_Y)
      integer :: pcrc_dad_X,pcrc_dad_Y
      real :: Y(0:*)
      real :: X(0:*)
        (other delaration ... )
      call pcrc_reset_push_bounds (pcrc_dad_Y,1,1,pcrc_alb_Y0,pcrc_aub_Y&
     &0,pcrc_ast_Y0)
      call pcrc_reset_push_bounds (pcrc_dad_X,1,1,pcrc_alb_X0,pcrc_aub_X&
     &0,pcrc_ast_X0)

      (translation of execution part ...)

      call pcrc_reset_pop_bounds (pcrc_dad_X,1,pcrc_alb_X0,pcrc_aub_X0,p&
     &crc_ast_X0)
      call pcrc_reset_pop_bounds (pcrc_dad_Y,1,pcrc_alb_Y0,pcrc_aub_Y0,p&
     &crc_ast_Y0)
      end 
\end{verbatim}

Dummy DADs are also added in argument list. And it is also tried to
save and restore the accrual DAD when come in and out of the
procedure, since some operations inside the procedure transfor mation
may change the DAD value.

Aside translation for each language component, there some preparing
work also need to be done:

\begin{itemize}
\item add declaration for each processor (grp)
\item add declaration for each template (rng)
\item add declaration for each distributed array (local array)
\item add declaration for DAD handle 
\item add declaration for loop bounds add declaration for temporary
  loop index and factor
\item add call pcrc\_init() and call pcrc\_finalize() 
\item add processor definition statements 
\item add template definition statements
\item add distributed array definition statements
\end{itemize}

\section{Related work}


\end{document}



