(3M) Calculator User Manual

3.1.4 Partial cost function
The production of efficient complete mappings requires that all graph bipar tition-
ings favor the criteria that we have chosen. Therefore, the bipartitioning of a
subgraph S
′
of S should maintain load balance within the user-s pecified tolerance,
and minimize the partial communication cost function f
′
C
, defined as
f
′
C
(τ
S,T
, ρ
S,T
)
def
=
X
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 bipar titionings makes it pos-
sible to avoid local choices that might prove globally bad, as explained below. This
amounts to incor po rating additional constraints to the standard gra ph 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 assoc iated with domain D between the two subdomains
D
0
and D
1
of D. Dotted edges are of dilation ze ro, their two ends being mapped
onto the same subdomain. Thin edges are coc ycle edges.
3.1.5 Execution sche me
From an alg orithmic point of view, our mapper behaves as a greedy algorithm, since
the mapping of a proc e ss to a subdomain is never reconsidered, and at each step
of which iterative algorithms can be applied. The double re cursive 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 s e quencing, 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 c ontrary, s e quencing 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 w hich all the proc e sses 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