Analyzing Ownership Sets in HPF
Pramod G. Joisha and Prithviraj Banerjee
Abstract
Ownership sets are fundamental to the partitioning of program
computations across processors by the owner-computes rule. These sets
arise due to the mapping of arrays onto processors. In this report, we
focus on how ownership sets can be efficiently determined in the
context of the HPF language, and show how the structure of these sets
can be symbolically characterized in the presence of arbitrary array
alignment and array distribution directives. Our starting point is a
system of equalities and inequalities due to Ancourt et al. that
captures the array mapping problem in HPF. We arrive at a refined
system that enables us to efficiently solve for the ownership set using
the Fourier-Motzkin Elimination technique, and that requires the course
vector as the only auxiliary vector. The formulation makes it possible
to enumerate the elements of the ownership set exactly once, a feature
that is very beneficial when such sets are applied to handle
DO loops qualified by HPF's INDEPENDENT directive.
We develop important and general properties pertaining to HPF
alignments and distributions, and show how they can be used to
eliminate redundant communication due to array replication.
Polynomial-time schemes that determine whether the ownership set of a
particular processor with respect to some array is the empty set, or
whether the ownership set of every processor with respect to some array
is the empty set, are presented. We show how distribution directives
with unspecified processor meshes can be efficiently handled at compile
time. We also show how to avoid the generation of communication code
when pairs of array references are ultimately mapped onto the same
processors. Experimental data demonstrating the improved code
performance that the latter optimization enables is presented and
discussed.