Exploiting Ownership Sets in HPF
Pramod G. Joisha5
and Prithviraj Banerjee]5 
| (5) |
Center for Parallel and Distributed Computing, Electrical and Computer Engineering Department, Technological Institute, 2145 Sheridan Road, Northwestern University, IL, 60208–3118 |
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 data arrays onto processors. In this paper, a 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 data alignment and data 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 which requires the course vector as the only auxiliary vector. We develop b 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. We also show how the generation of communication code can be avoided 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.
This research was partially supported by the National Science Foundation under Grant NSF CCR–9526325, and in part by DARPA
under Contract F30602–98–2–0144.
A longer version of this paper has been submitted to the IEEE Transactions on Parallel and Distributed Processing.
The proofs for all lemmas and theorems are available in [9].
References secured to subscribers.