Distribution Assignment Placement: Cleaning up after (Data) Tiling

Jens Knoop(a) and Eduard Mehofer (b)
(a) University of Dortmund
(b) University of Vienna


Data locality and workload balance are key factors for getting high performance out of data-parallel programs on multiprocessor architectures. Data-parallel languages like High Performance Fortran (HPF) thus offer means for specifying data distributions as well as for changing distributions dynamically in order to maintain these properties. Redistributions, however, can be quite expensive and significantly degrade a program's performance. In this talk, we report on a novel, aggressive approach for cleaning unnecessary distributions off a program. It works by eliminating {\em partially dead\/} and {\em partially redundant\/} distribution changes. Basically, this approach evolves from extending and combining two algorithms for these optimizations achieving each on its own optimal results. We demonstrate that combining them demands for a refined optimality investigation. Moreover, we show that the data-parallel setting leads to a family of algorithms of varying power and efficiency allowing user-customized solutions. The power and flexibility of the new approach are demonstrated by several examples ranging from typical HPF fragments to real world programs. Performance measurements additionally underline its importance and effectivity.

Keywords: Data-parallel languages, High Performance Fortran (HPF), dynamic data redistribution, data-flow analysis, optimization, partially dead and partially redundant assignment elimination.

Further info and related paper(s):