Subject: A proposal for EXECUTE-ON directive

From: Tin-Fook Ngai <[email-masked]>
Date: Tue, 15 Sep 92 12:16:43 -0700

The current HPF provides pretty adequate features to map data and to
specify data-parallel executions.  However, I found one important feature
still missing.  That is, for each parallel execution execution which data
accesses should be treated as local accesses and which can't.  Explicit
data mapping (i.e. alignment and distribution) does not necessarily
sufficient to determine the best execution location (provided that the
compiler is not super-smart).  In order to assist the compiler to generate
high performance code, a directive that hints at the execution location
will be very useful in HPF. So here comes this proposal.  Although it
comes late (I didn't make it into first reading in the last meeting!), I
wish we can fully discuss this important feature and incorporate it into
HPF (next meeting?).

This proposal is partially motivated by my previous discussion with
Michael Wolf of Oregon Graduate Institute.  He brought up the issue that
compiler may not be able to infer the best data locality from current HPF 
data mapping directives.  (See Example 6 in the proposal.)

Tin-Fook Ngai

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

A PROPOSAL FOR EXECUTE-ON DIRECTIVE IN HPF

September 14, 1992

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

The proposed EXECUTE-ON 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 align-spec [; LOCAL array-name-list]

CONSTRAINT

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

USAGE

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

INTERPRETATION

The subscript-list identifies a distinguish iteration index or an indexed
parallel assignment.  The align-spec identifies a template node.  The
EXECUTE-ON directive suggests that the iteration or parallel assignment
should be executed on the processor where the template node resides.  The
optional LOCAL directive informs the compiler 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 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 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 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 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 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 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)

!HPF$ REALIGNABLE B
!HPF$ TEMPLATE T(N,N)
!HPF$ ALIGN (:,:) WITH T:: A, B, C      
!HPF$ DISTRIBUTE T(BLOCK,*)             !* A,B,C are distributed by row blocks

      NOP = NUMBER_OF_PROCESSORS()
      IB = N/NOP

      DO IT = 0, NOP-1

!HPF$ REALIGN B(I,J) WITH T(I-IT*IB,J)  !* assuming warp around realignment

!HPF$ INDEPENDENT                       !* data parallel loop
        DO IP = 0, NOP-1     
!HPF$ EXECUTE (IP) ON 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

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

---

From: [email-masked]
Date: Mon, 5 Oct 1992 11:32:18 +0100

>
>> We cannot compile this subroutine independently. So we could forbid
>> subroutine calls.
>
>Why can't FOO be compile independently?  The EXECUTE ON directive means
>that FOO is called on the home of T1(I).  
>
>

Sorry, it was friday-afternoon. The example I was thinking of is:

Template T1(N)
  DO I=1,N
    EXECUTE (I) ON T1(I)
    C(I) = D(I)
   DO J=1,N
     A(I,J) = B(I,J)

Here A(I,J) is calculated in T(I). If we encapsulate the J-loop into a
subroutine we get something like:

Template T1(N)
  DO I=1,N
    EXECUTE (I) ON T1(I)
    C(I) = D(I)
    CALL FOO(A(I,:),B(I,:))
     
 SUBROUTINE FOO(AA,BB)
 ALIGN AA,BB with *
    DO J=1,N
    AA(J) = BB(J)

the dummy arguments AA and BB are aligned to the incoming array sections.
Normally, without any EXECUTE_ON, the subroutine would execute AA(J), which
is equivalent to A(I,J), on home A(I,J). However, with an EXECUTE_ON in the
main program there is no way the subroutine can know that AA(J) should be
executed on T(I). The consequence is that any subroutine call is to *undo*
the EXECUTE_ON on entry and *redo* the EXECUTE_ON on return.

- henk

================================================================
Henk J. Sips

Delft University of Technology
Lorentzweg 1
2628 CJ  Delft, the Netherlands
tel: +31.15.783191                     fax: +31.15.626740
e-mail: [email-masked]