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 ex ceeds the number of processors available. The mapping problem (also kn own as task allocation) has been widely studied. We propose a new gene ralized mapping strategy that uses a combination of graph theory, math ematical programming, and heuristics. The key difference between our s trategy and those proposed previously is the interdependence between t he algorithm and the architecture. We use the knowledge from the given algorithm and the architecture to guide the mapping. The approach beg ins with a graphical representation of the parallel algorithm (problem graph) and the parallel computer (host graph). Using these representa tions, we generate a new graphical representation (extended host graph ) on which the problem graph is mapped. We use an accurate characteriz ation of the communication overhead in our objective functions to eval uate the optimality of the mapping. An efficient mapping scheme is dev eloped which uses two levels of optimization procedures. The objective functions include minimizing the communication overhead and minimizin g the total execution time which includes both computation and communi cation times. The mapping scheme is tested by simulation and further c onfirmed by mapping a real world application onto actual distributed e nvironments.