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
Submitted by schiltz on Wed, 2008-03-05 10:40
»
- Login to post comments
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.