CRPC-TR91166-S:  Using Problem and Algorithm Topology for Parallelization

Lorie M. Liebrock, Darrell L. Hicks, Ken W. Kennedy, Jack J. Dongarra

July, 1991

Efficient parallelization for distributed memory parallel processors
requires that some parallel decomposition of the program be found and that
communication be encoded which satisfies all dependences in the decomposed
program. With the use of the Rice Fortran D compiler, the parallelization
problem is reduced to finding "proper" data structure partitions (in the
form of decomposition, alignment and distribution statements). Our
conjecture is that understanding problem topology is useful in optimizing
parallel programs in computational physics and other computational
sciences. In particular, the notion of topology can be used in the
compilation process to assist with parallelization. This thesis will be
explored by: developing a graphical tool, TopView, that uses problem
topology to provide recommendations for the alignment and distribution of
data structures; and extending Fortran D's capability to express and take
advantage of topology for the important case of irregularly coupled regular
meshes.