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