Strategies for topology-aware task mapping and for rebalancing with bounded migrations
Authors:
Tarun Agarwal
Parallel Programming Laboratory, Department of Computer Science, University
of Illinois at Urbana-Champaign
Master's Thesis, Department of Computer Science, University of Illinois 2005
The efficient usage of parallel machines requires that both the compute nodes as well as the interconnection network be utilized efficiently. As the number of processors in parallel machines increases, the diameter of the interconnection topology can become quite large. In order to prevent messages from travelling over such large distances, the entities in a parallel application need to be mapped onto the interconnection topology so that communicating objects are placed in the same neighborhood. This thesis presents a mapping scheme, which produces good mappings that reduce the average number of hops travelled by a byte on the network. We find that a mapping produced by our scheme reduces the effective cost of communication on the network since packets encumber a fewer number of links on an average. This thesis also studies the problem of load rebalancing that arises in the context of dynamic load balancing. After the initial mapping, further load balancing steps can reduce the migration cost by adjusting the current mapping by migrating only a few objects. We compare two schemes for this problem, and show that a simple greedy heuristic works well in practice.