A GENERALIZED SCHEME FOR MAPPING PARALLEL ALGORITHMS

The mapping problem arises when the dependency structure of a parallel algorithm differs from the processor interconnection of the parallel computer or when the number of processes generated by the algorithm exceeds the number of processors available. The mapping problem (also known as task allocation) has been widely studied. We propose a new generalized mapping strategy that uses a combination of graph theory, mathematical programming, and heuristics. The key difference between our strategy and those proposed previously is the interdependence between the algorithm and the architecture. We use the knowledge from the given algorithm and the architecture to guide the mapping. The approach begins with a graphical representation of the parallel algorithm (problem graph) and the parallel computer (host graph). Using these representations, we generate a new graphical representation (extended host graph) on which the problem graph is mapped. We use an accurate characterization of the communication overhead in our objective functions to evaluate the optimality of the mapping. An efficient mapping scheme is developed which uses two levels of optimization procedures. The objective functions include minimizing the communication overhead and minimizing the total execution time which includes both computation and communication times. The mapping scheme is tested by simulation and further confirmed by mapping a real world application onto actual distributed environments.