Strategies for topology-aware task mapping and for rebalancing with bounded migrations
Thesis 2005
Publication Type: MS Thesis
Repository URL: tarun-thesis
Abstract
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 traveling 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 traveled 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.
TextRef
Tarun Agarwal, "Strategies for topology-aware task mapping and for rebalancing with bounded migrations", Dept. of Computer Science, University of Illinois, 2005.
People
Research Areas