Subject: Revised proposal on EXECUTE-ON

From: Tin-Fook Ngai <[email-masked]>
Date: Wed, 14 Oct 92 12:47:42 -0700

Here is my revised proposal on the EXECUTE-ON-HOME directive.  (Thanks to
Hank for his comments.)  I will submit later a Latex version for inclusion
into the HPF Language Specification as required.

A remark regarding Clement's ON-Clause: I wrote my proposal after I read
Clement's proposal.  As pointed out by Clement, the application of my
EXECUTE-ON-HOME is more restricted than his ON-Clause.  But the
EXECUTE-ON-HOME is more specific and useful for those parallel executions
supported in the current HPF proposal. The EXECUTE-ON-HOME directive
allows explicit mapping of indexed executions to template nodes in a way
similar to the current HPF alignment, while Clement's ON-Clause relies on
the underlying shape to determine the mapping.  I believe the explicit
mapping in EXECUTE-ON-HOME is more general and useful.

Tin-Fook

------------------

==========
Changes:
1. Change keyword from EXECUTE ON to EXECUTE ON_HOME 
2. Allow nested EXECUTE-ON-HOME directives.  Only the immediately preceding
   directive is effective.
3. EXECUTE-ON-HOME directives have effect only on the caller of a subroutine
   call not on the called subroutine.  
4. Rewrite Example 6 to conform with current HPFF proposal that does not
   support automatic wrap-around mapping
==========

A PROPOSAL FOR EXECUTE-ON-HOME DIRECTIVE IN HPF 

Originated: September 14, 1992
Revised: October 14, 1992

Tin-Fook Ngai
Hewlett-Packard Laboratories
Email: [email-masked]

The proposed EXECUTE-ON-HOME directive is used to suggest where an
iteration of a DO construct or an indexed parallel assignment should be
executed.  The directive informs the compiler which data access should be
local and which data access may be remote.

SYNTAX

!HPF$ EXECUTE (subscript-list) ON_HOME align-spec [; LOCAL array-name-list]

CONSTRAINT

Each point in the index space must be executed on only one template
node.

USAGE AND SCOPE

1. The EXECUTE-ON-HOME directive must immediately precede the
corresponding DO loop body, array assignment, FORALL statement, FORALL
construct or individual assignment statement in a FORALL construct.

2. The scope of an EXECUTE-ON-HOME directive is the entire loop body of
the enclosing DO construct, or the following array assignment, FORALL
statement, FORALL construct or assignment statement in a FORALL construct.

3. EXECUTE-ON-HOME directives can be nested, but only the immediately
preceding EXECUTE-ON-HOME directive is effective.

INTERPRETATION

The subscript-list identifies a distinct iteration index or an indexed
parallel assignment.  The align-spec identifies a template node.  The
EXECUTE-ON-HOME directive suggests that the iteration or parallel
assignment should be executed on the processor to where the template node
is mapped.  When the EXECUTE-ON-HOME directive is applied to a subroutine
call, it affects only the execution location of the caller but not the
execution location of the called subroutine.

The optional LOCAL directive informs the compiler that all data accesses
to the specified array-name-list can be handled as local data accesses if
the related HPF data mapping directives are honored.

EXAMPLES

Example 1

      REAL A(N), B(N)
!HPF$ TEMPLATE T(N)
!HPF$ ALIGN WITH T:: A, B
!HPF$ DISTRIBUTE T(CYCLIC(2))

!HPF$ INDEPENDENT            
      DO I = 1, N/2 
!HPF$ EXECUTE (I) ON_HOME T(2*I); LOCAL A, B, C
      ! we know that P(2*I-1) and P(2*I) is a permutation of 2*I-1 and 2*I
        A(P(2*I - 1)) = B(2*I - 1) + C(2*I - 1)    
        A(P(2*I)) = B(2*I) + C(2*I)
      END DO

Example 2

      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B
!HPF$ EXECUTE (I,J) ON_HOME T(I+1,J-1)
      FORALL (I=1:N-1, J=2:N)   A(I,J) = A(I+1,J-1) + B(I+1,J-1)

Example 3

      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B
!HPF$ EXECUTE (I,J) ON_HOME T(I,J)   ! applies to the entire FORALL construct
      FORALL (I=1:N-1, J=2:N) 
	A(I,J) = A(I+1,J-1) + B(I+1,J-1)
	B(I,J) = A(I,J) + B(I+1,J-1)
      END FORALL

Example 4

      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B
      FORALL (I=1:N-1, J=2:N) 
!HPF$ EXECUTE (I,J) ON_HOME T(I,J)  ! applies only to the following assignment
	A(I,J) = A(I+1,J-1) + B(I+1,J-1)
	B(I,J) = A(I,J) + B(I+1,J-1)
      END FORALL

Example 5 

      REAL A(N,N), B(N,N)
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN WITH T:: A, B

!HPF$ EXECUTE (I,J) ON_HOME T(I+1,J-1)
      A(1:N-1,2:N) = A(2:N,1:N-1) + B(2:N,1:N-1)

Example 6 
 
      !* Original program due to Michael Wolfe of Oregan Graduate Institute

      !* This program performs matrix multiplication C = A x B
      !* In each step, array B is rotated by row-blocks, multiplied
      !* diagonal-block-wise in parallel with A, results are accumulated in C 

      !* Note: without the EXECUTE-ON-HOME and LOCAL directive, the compiler
      !* will have a hard time to figure out all A, B and C accesses are 
      !* actual local, thus unable to generate the best efficient code 
      !* (i.e. communication-free and no runtime checking in the parallel 
      !* loop body).
 
      REAL A(N,N), B(N,N), C(N,N)

      PARAMETER(NOP = NUMBER_OF_PROCESSORS())
!HPF$ REALIGNABLE B
!HPF$ TEMPLATE T(2*N,N)                 !* to allow wrap around mapping
!HPF$ ALIGN (I,J) WITH T(I,J):: A, C      
!HPF$ ALIGN B(I,J) WITH T(N+I,J)
!HPF$ DISTRIBUTE T(CYCLIC(N/NOP),*)     !* A,B,C are distributed by row blocks

      IB = N/NOP

      DO IT = 0, NOP-1

!HPF$ REALIGN B(I,J) WITH T(N-IT*IB+I,J)  !* in effect, rotate by row-blocks

!HPF$ INDEPENDENT                       !* data parallel loop
        DO IP = 0, NOP-1     
!HPF$ EXECUTE (IP) ON_HOME T(IP*IB+1,1); LOCAL A, B, C
          ITP = MOD( IT+IP, NOP )

          DO I = 1, IB
            DO J = 1, N
              DO K = 1, IB
                C(IP*IB+I,J) = C(IP*IB+I,J) + A(IP*IB+I,ITP*IB+K)*B(ITP*IB+K,J)
              ENDDO  !* K
            ENDDO  !* J
          ENDDO  !* I
        ENDDO  !* IP

      ENDDO  !* IT

END OF PROPOSAL

------------------------------------------------------------------------------