Scotch Brand 5.1.10 User Manual
Page 11
3.1.4
Partial cost function
The production of efficient complete mappings requires that all graph bipartition-
ings favor the criteria that we have chosen. Therefore, the bipartitioning of a
subgraph S
′
of S should maintain load balance within the user-specified tolerance,
and minimize the partial communication cost function f
′
C
, defined as
f
′
C
(τ
S,T
, ρ
S,T
)
def
=
v ∈ V (S
′
)
{v, v
′
} ∈ E(S)
w
S
({v, v
′
}) |ρ
S,T
({v, v
′
})| ,
which accounts for the dilation of edges internal to subgraph S
′
as well as for the
one of edges which belong to the cocycle of S
′
, as shown in Figure 1. Taking into
account the partial mapping results issued by previous bipartitionings makes it pos-
sible to avoid local choices that might prove globally bad, as explained below. This
amounts to incorporating additional constraints to the standard graph bipartition-
ing problem, turning it into a more general optimization problem termed skewed
graph partitioning
by some authors [27].
D
0
D
1
D
a. Initial position.
D
0
D
1
D
b. After one vertex is moved.
Figure 1: Edges accounted for in the partial communication cost function when
bipartitioning the subgraph associated with domain D between the two subdomains
D
0
and D
1
of D. Dotted edges are of dilation zero, their two ends being mapped
onto the same subdomain. Thin edges are cocycle edges.
3.1.5
Execution scheme
From an algorithmic point of view, our mapper behaves as a greedy algorithm, since
the mapping of a process to a subdomain is never reconsidered, and at each step
of which iterative algorithms can be applied. The double recursive call performed
at each step induces a recursion scheme in the shape of a binary tree, each vertex
of which corresponds to a bipartitioning job, that is, the bipartitioning of both a
domain and its associated subgraph.
In the case of depth-first sequencing, as written in the above sketch, biparti-
tioning jobs run in the left branches of the tree have no information on the dis-
tance between the vertices they handle and neighbor vertices to be processed in
the right branches. On the contrary, sequencing the jobs according to a by-level
(breadth-first) travel of the tree allows any bipartitioning job of a given level to
have information on the subdomains to which all the processes have been assigned
at the previous level. Thus, when deciding in which subdomain to put a given pro-
cess, a bipartitioning job can account for the communication costs induced by its
11