Optimization-Based Mapping Framework for Parallel Applications

The optimal mapping of tasks of a parallel program onto nodes of a parallel computing system has a remarkable impact on application performance. In this paper we propose an optimization framework to solve the mapping problem, which takes into account the communication matrix of the application and a cost matrix that depends on the topology of the parallel system. This cost function can be a distance matrix (the classic approach), or can take into account other considerations. We propose a novel definition of the cost criterion, applicable to torus networks, that tries to distribute traffic evenly over the different axes: the Traffic Distribution criterion. As the mapping problem is a particular instance of the Quadratic Assignment Problem, we can apply any QAP solver to the mapping. In particular, in this work we use GRASP. Using simulation, we test the performance of the optimization-based mappings, and compare it with that of trivial mappings (consecutive, random), in two different environments: static (a single applications uses all system resources all the time) and dynamic (applications are managed by a scheduler, and use and free resources as needed), always using a system with a 2D topology and real application traffic. In both environments optimization-based mappings with the TD criterion provides excellent performance. 1