Scotch Brand 5.1.10 - Manual (Page 12)

neighbor processes, 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, and 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
CL2 CL0
CL1
CL2
b. Breadth-first sequencing.
Figure 2: Influence of depth-first and breadth-first sequencings on the bipartitioning
of a domain D belonging to the leftmost branch of the bipartitioning tree. With
breadth-first sequencing, the partial mapping data regarding vertices belonging to
the right branches of the bipartitioning tree are more accurate (C.L. stands for “Cut
Level”).
depth-first and breadth-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 allows the mapper to run any type of graph bipartitioning
method compatible 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 therefore 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, extracts 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 refined 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 space by
several orders of magnitude. However, it was found that, in a multi-level
context, it also improves partition quality, by coercing partitions in a problem
12