Mapping parallel programs onto parallel systems with torus and mesh-based communication structures
Lixin Tao, Eva Ma · 1988
The major objectives of this research are (1) to design efficient schemes for mapping parallel programs onto parallel processing systems to minimize the communication overhead incurred by the mismatch between the communication characteristics of the parallel programs and those of the parallel processing systems, and (2) to support logical inter-process communication at execution time to improve program readability, verifiability, productivity, and portability. We use graph mapping as the mathematical model of the program mapping problem. We introduce a rich class of low dilation cost graph embedding functions for toruses and meshes of various dimensions and various shapes (with lines, rings, and hypercubes as special cases). We design contraction functions to generalize the one-to-one embeddings to achieve optimal or good many-to-one graph mappings. We propose an efficient program loading approach based on inverses of mapping functions and a broadcast network. We design the shortest-path data routing scheme to carry out automatically our data routing strategies at execution time to simulate on the system any permutation type set or scatter type set of parallel neighboring communications in the task graph. For most of our mapping functions, the data routing complexities are the same as the corresponding dilation costs. For the rest, the data routing complexities are less than four times the corresponding dilation costs. Since our approach supports task graph level communication at execution time, even the object code of parallel programs can be completely transparent to system topologies.