A generalized scheme for mapping parallel algorithms

Abstract
A generalized mapping strategy that uses a combination of graph theory, mathematicalprogramming, and heuristics is proposed. The authors use the knowledge from the givenalgorithm and the architecture to guide the mapping. The approach begins with agraphical representation of the parallel algorithm (problem graph) and the parallelcomputer (host graph). Using these representations, the authors generate a newgraphical representation (extended host graph) on which the problem graph is mapped.An accurate characterization of the communication overhead is used in the objectivefunctions to evaluate the optimality of the mapping. An efficient mapping scheme isdeveloped which uses two levels of optimization procedures. The objective functionsinclude minimizing the communication overhead and minimizing the total execution timewhich includes both computation and communication times. The mapping scheme istested by simulation and further confirmed by mapping a real world application ontoactual distributed environments.

This publication has 49 references indexed in Scilit: