Published Articles >> Table of Contents >> Abstract

28th Hawaii International Conference on System Sciences (HICSS'95)   p. 103
Automatic data and computation decomposition for distributed memory machines
Qi Ning, Centre de Recherche Inf. de Montreal, Que., Canada
V. Van Dongen, Centre de Recherche Inf. de Montreal, Que., Canada
G.R. Gao, Centre de Recherche Inf. de Montreal, Que., Canada

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/HICSS.1995.375472
Send link to a friend

Abstract
We have developed an automatic compile-time computation and data decomposition technique for distributed memory machines. Our method can handle complex programs containing perfect and nonperfect loop nests with or without loop-carried dependences. Applying our decomposition algorithms, a program is divided into collections (called clusters) of loop nests, such that data redistributions are allowed only between the clusters. Within each cluster of loop nests, decomposition and data locality constraints are formulated as a system of homogeneous linear equations which is solved by polynomial time algorithms. Our algorithm can selectively relax data locality constraints within a cluster to achieve a balance between parallelism and data locality. Such relaxations are guided by exploiting the hierarchical program nesting structures from outer to inner nesting levels to keep the communications at an outer-most level possible. This work is central to the on-going compiler development effort under the EPPP (Environment for Portable Parallel Programming) project. A brief discussion of the current implementation is included.
Back to Top Additional Information
Index Terms- distributed memory systems; program control structures; parallel programming; equations; computational complexity; relaxation; software portability; parallelising compilers; data handling; automatic data decomposition; automatic computation decomposition; distributed memory machines; compile-time technique; complex programs; perfect loop nests; nonperfect loop nests; loop-carried dependences; loop nest clusters; data redistributions; data locality constraint relaxation; homogeneous linear equations; polynomial time algorithms; parallelism; hierarchical program nesting structures; nesting levels; compiler development; EPPP project; Environment for Portable Parallel Programming Citation:  Qi Ning, V. Van Dongen, G.R. Gao, "Automatic data and computation decomposition for distributed memory machines," hicss, p. 103,  28th Hawaii International Conference on System Sciences (HICSS'95),  1995