What objective is satisfied first?

When partitionning a mesh (or a graph), there are 2 different objectives to satisfy: load balancing, and edge-cut. Which one of those 2 objectives is satisfied first. Or, are they satisfied both at the same time?

I have the following (very simple) graph :

adj : 0 2 3 5 6
adjncy : 1 2 0 0 3 2
vwgt : 66 66 21 21
adjwgt : 1 1 1 1 1 1

A very simple way to partition this graph would be to put one element that weights 66 with one element that weights 21, which would lead to a (87, 87) partition, which would be perfect. However, this also leads to a edge-cut of 2.

If I give this input to METIS, it gives me another partition, in which the two "66" elements are grouped together (and so are the two "21" elements), with an edge-cut of 1.

So, my question is : does Metis "search" for the best edge-cut AND THEN try to enhance the load balancing on each partition, OR does it search for the best load balancing AND THEN try to minimize the edge-cut, OR does it minimize the following objective [ abs(load1-load2) + edge_cut ]??

My interpretation of my results is that it first searches for the best edge_cut...

Thanks in advance...

Benoît Schiltz

RE: so, why?

Thanks for answering!!

So why in my very particular case is the load balancing so "misbalanced"? I mean, on my very little graph, the ratio between the less loaded part and the most loaded part is something like (21*2)/(66*2) = 1/3 ???? Isn't it surprising to have a result that is so bad while there is a much better solution with the same ratio that takes the value 1?

Also, on much larger meshes (or graphes), is it normal that for a 8-part partitioning, the ratio of the less loaded part and the most loaded part is something like 70%? It seems to me that is is a bit bad as a partitioning, no? The load-balancing is crucial for the soft I am developing, and that kind of misbalanced partition can lead to desastrous speed-ups in parallel computations (I develop a CFD-like time domain aeroacoustic simulation tool). Any ideas on how to improve the partitioning?

Again, Thanks in advance!!

Benoît Schiltz

RE: The load imbalance can

The load imbalance can happen for four reasons:
- metis has a loose 1.03% load imbalance that it considers to be good enough
- if the graph is too small, metis's heuristic balancing scheme tends to fail
- if you are over-partitioning a graph (nparts ~= nvtxs), the heuristics can
also fail.
- if the vertices have significantly different weights, then the recursive
decomposition approach that metis uses to compute the initial partitioning
may get it into a bad corner, in which balance cannot be achieved.

One way to try eliminate the last case is to formulate your partitioning problem
as a two-constraint problem whose second constraint will be to balance the number
of nodes between the partitions (the first constraint will be to balance the sum
of the vertex weights).

RE: load imbalance

Is it possible to do that with Metis? Is it equivalent to : first partitioning with weights set to 1, and then give the result as input for a second partitioning with the "real" weights ?

How will I be able to deal with this two-constraint problem _and_ the minimization of the edge-cut?

The ideal scheme to me would be :
-achieve a "perfect" (1.03 seems ok to me) load-balancing
-have an edge-cut that is "reasonable"
(what I mean is that, clearly at this stage, the load balancing is much more important to me than the edge-cut, _but_ I cannot afford to affect a zero weight on the edges, because it would increase dramatically my communications between processes)

Any comment is welcome, thanks a lot...

Benoît schiltz

RE: Metis has multi-constraint

Metis has multi-constraint partitioning routines that allow you to do that. Essentially, the two constraints are modeled as different vertex weights. Read the manual...

RE: Metis actually enforces the

Metis actually enforces the load balance first and then optimizes the cut. The load balance is treated as a constraint.