1 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.

1.1 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.

1.1.1 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

      A=B+C

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.

1.1.2 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.

1.1.3 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.

1.2 Translating different language components

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

• DAD generation for distributed data

• Expressions and assignment

• Program execution control

• Input and output

• Procedures

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:

      A=B

can be changed into

      FORALL (tempI=1:n)        A(tempI)=B(tempI)

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

Other transformation similar to this kind may include:

• where construct (using forall mask expression)

• array section in assignment and input/output

• simplified data mapping directives

• array element used as scalar variable

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.

1.2.1 DAD generation

Given the follow HPF program

      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)

will be changed to:

      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))

We can summarize this part as following: For each processor array, a grp value will be created with corresponding

processor shape; For each template, a rng value will be created to record its distribution code, distribution stride and offset. For each partitioned array, a 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 grp, rng, dad and set array align. Finally, if needed a tag is used to indicate where the name come from.

1.2.2 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:

FORALL (i=-7:190:4) X(i) = Y(1*i+3) + Y(1*i+3)

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

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)

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

X(pcrc_sdx0) = Y(pcrc_sdx1)+Y(pcrc_sdx2)

And we can see there is no need to exchange data among the processors. If we have the program header as:

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)

and a forall statement like:

FORALL (i=-8:190:3) X(i) = Y(1*i+4

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

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)

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

The computation is carried out by,

X(pcrc_sdx0) = pcrc_real_stack(pcrc_tbs1+pcrc_sdx1)+pcrc_rea&
&l_stack(pcrc_tbs2+pcrc_sdx0)

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

      REAL sclr

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

Then for an assignment like,

      sclr=X(3)

will be translated to:

      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)

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.

1.2.3 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

100   sclr=X(3)

then we may add

100   continue

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

1.2.4 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,

      PRINT 111, (X(i),i=-98,197)
111   FORMAT(1x,f17.2)

will be translated as:

      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)

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.

1.2.5 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.

      CALL FOO(X(-75:194:1),Y(-49:821:3))

will change to,

  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)

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,

SUBROUTINE FOO(X,Y)
REAL X(:), Y(:)
!HPF$ INHERIT X,Y
(execution part ... )
END

Then it will be translated as,

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

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:

• add declaration for each processor (grp)

• add declaration for each template (rng)

• add declaration for each distributed array (local array)

• add declaration for DAD handle

• add declaration for loop bounds add declaration for temporary loop index and factor

• add call pcrc init() and call pcrc finalize()

• add processor definition statements

• add template definition statements

• add distributed array definition statements

2 Related work