(3M) Calculator User Manual

neighbor proces ses, whether they are handled by the job itself or not, since it can
estimate in f
′
C
the dilation of the corresponding edges. This results in an interesting
feedback effect: once an edge has been kept in a cut between two subdomains, the
distance between its end vertices will be accounted for in the partial communication
cost function to be minimized, a nd following jobs will be more likely to keep these
vertices close to each other, as illustrated in Figure 2. The relative efficiency of
D
CL2
CL0
CL1
a. Depth-first sequencing.
D
CL1
CL2CL0
CL1
CL2
b. Breadth-first sequencing.
Figure 2: Influence of depth-first and br e adth-first sequencings on the bipartitioning
of a domain D belo nging to the leftmost branch of the bipartitioning tree. With
breadth-first sequencing, the partial mapping data regarding vertices b e longing to
the r ight branches of the bipartitioning tree are more accurate (C.L. stands for “Cut
Level”).
depth-first and bre adth-first sequencing schemes with respect to the structure of
the source and target graphs is discussed in [44].
3.1.6 Graph bipartitioning methods
The core of our recursive mapping algorithm uses process graph bipartitioning meth-
ods as black boxes. It a llows the mapper to run any type of graph bipartitioning
method co mpatible with our criteria for quality. Bipartitioning jobs maintain an in-
ternal image of the current bipartition, indicating for every vertex of the job whether
it is currently assigned to the first or to the second subdomain. It is therefo re possi-
ble to apply several different methods in sequence, each one starting from the result
of the previous one, and to select the methods with respect to the job character-
istics, thus enabling us to define mapping strategies. The currently implemented
graph bipartitioning methods are listed below.
Band
Like the multi-level method which will be described below, the band method
is a meta-algorithm, in the sense that it does not itself compute partitions, but
rather helps other partitioning algorithms perform better. It is a refinement
algorithm which, from a given initial partition, extr acts a band graph of given
width (which only contains graph vertices that are at most at this distance
from the separator), calls a partitioning strategy on this band graph, and
projects back the r e fined partition on the original graph. This method was
designed to be able to use expensive partitioning heuristics, such as genetic
algorithms, on large graphs, as it dramatically reduces the problem spa c e by
several orders of magnitude. However, it was found that, in a multi-level
context, it also improves partition quality, by c oercing partitions in a problem
12