(3M) Calculator User Manual

space that derives from the one which was g lobally defined a t the coarsest
level, thus preventing local optimization refinement algorithms to be trapped
in lo c al optima of the finer graphs [8].
Diffusion
This global optimization method, presented in [42], flows two kinds of antag-
onistic liquids, scotch and anti-sco tch, from two sour c e ver tices, and se ts the
new frontier as the limit between vertices which contain scotch and the ones
which contain anti-scotch. In order to add load-balancing constraints to the
algorithm, a constant amount of liquid disappears from every vertex per unit
of time, so that no domain can spread ac ross more than half of the vertices.
Because se le c ting the source vertices is essential to the obtainment of use-
ful results, this method has been hard-coded so that the two source vertices
are the two vertices of highest indices, since in the band method these are
the anchor vertices which represent all of the remove d vertices of e ach part.
Therefore, this method must be used on ba nd graphs only, or on specifically
crafted graphs.
Exactifier
This greedy algorithm refines the current partition so as to reduce load imbal-
ance as much as possible, while keeping the value of the communication cost
function as small as possible. The vertex set is scanned in order of decreasing
vertex weights, and vertices are moved from one s ubdomain to the other if
doing so reduces load imbalance. When several vertices have same weight,
the vertex whose swap decreases most the communication cost function is se-
lected firs t. This method is us ed in post-processing of other methods when
load balance is mandatory. For weighted graphs, the strict enforcement of
load balance may cause the swapping of isolated vertices of small weight, thus
greatly increasing the cut. Therefore, great care should be taken when using
this method if connectivity or cut minimization are mandatory.
Fiduccia-Mattheyses
The Fiduccia-Mattheyses heuristics [12] is an almost-linea r improvement of
the famous Kernighan-Lin algorithm [35]. It tries to improve the bipartition
that is input to it by incrementally moving vertices between the subsets of
the partition, a s long as it can find sequences of moves that lower its commu-
nication cost. By considering sequences of moves instead of single swaps, the
algorithm allows hill-climbing from loc al minima of the cost function. As an
extension to the original Fiduccia-Mattheyses algorithm, we have developed
new data structures, based on logarithmic indexings of arrays, that allow us
to handle weighted graphs while preserving the almos t-linearity in time of the
algorithm [44].
As seve ral authors quoted before [24, 32], the Fiduccia-Mattheyses algorithm
gives better results when trying to optimize a good starting partition. There-
fore, it should not be used on its own, but rather after greedy starting methods
such as the Gibbs-Poole-Stockmeyer or the greedy graph gr owing methods.
Gibbs-Poole-Stockmeyer
This greedy bipartitioning method derives from an algorithm proposed by
Gibbs, Poole, and Stockmeyer to minimize the dilation of graph orderings,
that is, the maximum absolute va lue of the difference between the numbers of
neighbor vertices [18]. The graph is sliced by using a breadth-first spanning
13