Topology Aware Task-To-Processor Assignment

Topology aware mapping has started to attain interest again by the development of supercomputers whose topologies consist of thousands of processors with large diameters. In such parallel architectures, it is possible to obtain performance improvements for the executed parallel programs via careful mapping of tasks to processors by considering properties of the underlying topology and the communication pattern of the mapped program. One of the most widely used metric for capturing a parallel program’s communication overhead is the hop-bytes metric which takes the processor topology into account which is in contrast to the assumptions made by the wormhole routing. In this work, we propose a KL-based iterative improvement heuristic for mapping tasks of a given program to the processors of the parallel architecture where the objective is the reduction of the communication volume that is modeled with the hop-bytes metric. We assume that the communication pattern of the program is known beforehand and the processor topology information is available. The algorithm basically tries to improve a given initial mapping with a number of successive task swaps defined within a given processor neighborhood. We test our algorithm for different number of tasks and processors and demonstrate its results by comparing it to random mapping, which is widely used in recent supercomputers