Overview of the dHPF Compiler

Fortran D95 Language

Fortran D95 is designed to support research on data-parallel programming in High Performance Fortran (HPF) and to explore extensions that would broaden HPF's applicability or enhance performance.

Features

• Fortran 77 + Fortran 90 array syntax + FORALL + ALLOCATE
• High Performance Fortran (HPF) data mapping directives for regular problems
  • ALIGN, DISTRIBUTE, REALIGN, REDISTRIBUTE, TEMPLATE, PROCESSORS
• INDEPENDENT, and ON_HOME
• Data-layout directives for out-of-core arrays
• experimental support (under development) for
  • data-mapping directives to support irregular problems
  • complex data structures
  • structured use of task parallelism

dHPF Compiler Organization

Front End

Purpose: parsing, semantic checking of HPF directives, and preprocessing code for further analysis

• semantic analysis of directives
• infer canonical synthetic layout directives for all program variables unmentioned in program directives
• intraprocedural flow-sensitive propagation of (RE)ALIGN, (RE)DISTRIBUTE to statements and array references
• Scalarization of F90 array statements into F77 loops

Limitations (May 1996)

• no interprocedural propagation of layout information

Preliminary Communication Placement

Purpose: provide feedback to the computation partitioner about where (conservatively) communication might be needed

Strategy

• conservatively assume all references to non-replicated variables may need communication
• hoist communication for a reference to the outermost loop level possible while respecting data dependences on the reference or its subscripts
• conservatively prevent communication from being hoisted out of ``non-do-loop'' iterative constructs

Limitations (May 1996)

• placement independent of resource constraints
• no support for pipelining communication to achieve partial parallelism

Computation Partitioning Selection

Purpose: a framework to evaluate and select from several computation partitioning alternatives, not restricted to the owner-computes rule.

Communication Refinement

Code Generation Overview

Code Generation for Computation Partitioning

• Statements in a loop can have different CPs
• Bottom-up code generation framework
  • partition computation one "scope" at a time
    using contextual information from enclosing scopes
  • different partitioning strategies can be used for different scopes
    • simple bounds reduction
    • loop splitting and bounds reduction
    • guards for run-time resolution
  • bottom-up order gives better compile-time efficiency with a possible small run-time cost due to imprecise contextual information
• Primary strategy for scopes with regular distributions is based on Omega library

Omega Library (University of Maryland)

• Sets of integer tuples, e.g.,

    Local := { [i,j] : 25 * p1 + 1 <= i <= 25 * p1 + 25 && 
                       (exists k: 4 * k = j - p2 && 1 <= j <= 100) }

• Mappings from tuples to tuples, e.g.,

    RefSubscript := { [i,j] -> [i',j'] : i' = i - 1 && j' = j }

• Rich collection of operations on sets and mappings, e.g.
  • composition

      DataAccessedByRef := RefSubscript(LocalIterSet)

  • codegen : generates a loop-nest that enumerates integer tuples in a set:

      for(t1 = 25*mypid1+1; t1 <= 25*mypid1+25; t1++)
        for(t2 = 1+(mypid2-(1))%4; t2 <= 100; t2 += 4)
          s1(t1,t2)

Omega-Based Framework for Data Parallel Code Generation

• Framework based on 6 fundamental components (synthesized from IR):
  3 types of sets
  Data: a set of data elements
  Iterations : a set of loop iterations
  Processors: a set of processors
  3 types of mappings
  Layout: data <-> processors
  Reference: iterations <-> data
  Comp.Part.: iterations <-> processors
• Use simple set equations to compute:
  • SEND/RECV data sets for a message between processor pairs
  • Local iteration set for a loop
  • Local iterations that read / write / read+write / don't access non-local data
• Invoke "codegen" to generate:
  • sequence of SPMD loop nest sections
  • loop nest to pack/unpack a message buffer

Omega-Based Framework: Example

  #   !HPF$ distribute A(BLOCK) on P(4)      ! sic
  #   do i = 1, 100
  #      ... = A(i-1) + ...                  ! non-local read
  #   enddo
	
  symbolic MYPID, Q
  
  Loop	         := { [i] : 1 <= i <= 100 }
  RefSubscript     := { [i] -> [i-1] }
  MyArraySection   := { [i] : 25 * MYPID <= i <= 25 * MYPID + 25 }
  
  LocalIterSetForQ := { [i] : iter i is executed by processor `Q'}
  ReadSectionForQ  := RefSubscript(LocalIterSetForQ)    # composition

  SendToQ          := ReadSectionForQ intersection MyLocalArraySection
       
  codegen SendToQ

Optimizations using the Omega Framework - I

• Each potentially non-local reference might need a guard
• Split partitioned loop into 2 sections

    NonLocalIterSet := { iterations that access potentially non-local data }
    LocalIterSet    := { iterations that access only local data }
  

• Only references in the NonLocalIterSet section need guards

Optimizations using the Omega Framework - II

• Split partitioned loop into 3 sections:

    NonLocalReadIterSet  := { iterations that read non-local data }
    NonLocalWriteIterSet := { iterations that write non-local data }
    LocalIterSet         := { iterations that access only local data }
  

• Overlap messages with Local computation:

   -- SEND for non-local READ --
        COMPUTE NonLocalWriteIterSet
                -- SEND for non-local WRITE --
        COMPUTE LocalIterSet 
   -- RECV for non-local READ --
        COMPUTE NonLocalReadIterSet 
                -- RECV for non-local WRITE --
  

Compiled Examples