[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14]

Journal of Inforamtion Science and Engineering, ol.14 No.1, pp.27-51 (March 1998)
An Interprocedural Framework for Determining
Efficient Array Data Redistributions*

S.K.S. Gupta and S. Krishnamurthy+
Computer Science Department
Colorado State University
Fort Collins, CO 80523
+ Department of Computer Science
University of Illinois at Urbana-Champaign
Urbana, IL 61801

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.

Keywords: data redistribution, distributed memory machine, compiler optimization, dynamic programming, High Performance Fortran (HPF), interprocedural analysis, intermediate representations, flow analysis

Received April 25, 1997; revised December 20, 1997.
Communicated by Chau-Huang Huang.
* A preliminary version of the paper appeared in Frontiers'96 [9].