NASA NTRS2000
Development of HPF versions of NPB and ARC3D has shown that HPF provides an efficient, concise way to express parallelism and to organize data traffic. The use of HPF, as noted in the papers, requires an intimate knowledge of the applications and a detailed analysis of data affinity, data movement, and data granularity. To simplify and accelerate the task of developing HPF versions of existing CFD applications we have designed and implemented ADAPT (Automatic Data Alignment and Placement Tool). ADAPT analyzes a CFD application working on a single structured grid and generates HPF TEMPLATE, (RE)DISTRIBUTION, ALIGNMENT, and INDEPENDENT directives. The directives can be generated on the nest level, subroutine level, application level, or on the application interface level. ADAPT annotates an existing CFD FORTRAN application, performing computations on single or multiple grids. On each grid the application is considered as a sequence of operators, each applied to a set of variables defined in a particular grid domain. ADAPT automatically detects implicit operators (i.e., having data dependences) and explicit operators (without data dependences). For parallelization of an explicit operator ADAPT creates a template for the operator domain, aligns arrays used in the operator with the template, distributes the template, and declares the loops over the distributed dimensions as INDEPENDENT. For parallelization of an implicit operator, the distribution of the operator's domain should be consistent with the operator's dependences. Any dependence between sections distributed on different processors would preclude parallelization if the compiler does not have an ability to pipeline computations. If a data distribution is "orthogonal" to the dependences of an implicit operator, then the loop which implements the operator can be declared as INDEPENDENT. ADAPT starts with an analysis of array index expressions of the loop nests. For each pair of arrays referenced in an assignment statement, it generates an arc in the alignment graph and annotates it with an affinity relation. The template, alignment, and distribution directives for a particular loop nest are then derived from a transitive closure of the affinity relation. A compromise of data distributions in different nests and subroutines is achieved by merging annotated alignment graphs for adjacent nests/stibroutine calls in the nest/call graph of the application in the process called distribution lifting. ADAPT has been implemented as a C++ program running in conjunction with a parallelization tool called CAPTools. ADAPT uses the parse tree, interprocedural analysis and application database generated by CAPTools. It also uses the Directed Graph class, initially implemented in p2d2 (parallel debugger oi distributed programs), and some other classes supporting symbolic computations. ADAPT uses data distribution techniques described. ADAPT was tested with ARC3D and the FT benchmark and has demonstrated a code performance within a factor of 1.5 of handwritten versions.