An interprocedural framework for determining efficient array data redistributions

Abstract

Modifying the data distributions over the course of a program to adapt to variations in the data reference patterns at different points may lead to significant computational benefits. However, these modifications themselves result in data redistribution overheads because of the interprocessor communication involved. Moreover, modifying distributions across procedure boundaries is more complex because of the impreciseness in the available information and the need to perform global data-flow analysis. This paper presents a framework to find good distributions for the global arrays at different program points in the presence of procedure calls. The distributions are chosen for their ability to offset the redistribution overheads by contributing significantly towards increasing the performance gains. The framework uses interprocedural analysis and dynamic programming techniques. Experimental results obtained by testing the dynamic programming algorithm on some standard HPF programs indicate that it is possible to determine efficient data redistributions at compile-time.