Balancing Partitions
Hello
I use metis to partition a graph over 2/4/8 partitions in a multi-constrained setting (7 or 12 constraints).
As I want METIS to try to balance every resource about equally over the partitions I use the default settings (as I understood it from the manual, the default settings will try to balance all resources equally over the partitions so every partition (e.g. 4 partitions) should have about 1/4th of the resource weights of every constraint.).
I understand that it is inherently impossible to get really balanced partitions in such a setting while still minimizing edge cut.
Nevertheless I would like to try to get partitions which are a bit more balanced. At the moment some partitions seem very unbalanced for a certain resource.
Is there a way to tweak METIS to try to generate partitions which are more balanced?
Here is one of my METIS execution logs:
******************************************************************************
METIS 5.0 Copyright 1998-13, Regents of the University of Minnesota
(HEAD: , Built on: Jun 8 2014, 15:09:41)
size of idx_t: 64bits, real_t: 32bits, idx_t *: 64bits
Graph Information -----------------------------------------------------------
Name: lubm160_d_4.metis, #Vertices: 521254, #Edges: 588197, #Parts: 4
Balancing constraints: 7
Options ---------------------------------------------------------------------
ptype=kway, objtype=cut, ctype=shem, rtype=greedy, iptype=metisrb
dbglvl=0, ufactor=1.030, no2hop=NO, minconn=NO, contig=NO, nooutput=NO
seed=-1, niter=10, ncuts=1
Direct k-way Partitioning ---------------------------------------------------
- Edgecut: 300630000, communication volume: 156670.
- Balance:
constraint #0: 1.180 out of 0.000
constraint #1: 1.180 out of 0.000
constraint #2: 1.180 out of 0.000
constraint #3: 1.143 out of 0.095
constraint #4: 1.091 out of 0.364
constraint #5: 1.180 out of 0.007
constraint #6: 1.180 out of 0.000
- Subdomain connectivity: max: 3, min: 3, avg: 3.00
- There are 4 non-contiguous partitions.
Total components after removing the cut edges: 102812,
max components: 39096 for pid: 2.
Timing Information ----------------------------------------------------------
I/O: 0.392 sec
Partitioning: 3.608 sec (METIS time)
Reporting: 0.244 sec
Memory Information ----------------------------------------------------------
Max memory used: 110.723 MB
******************************************************************************
As a question on the side: I have a hard time actually understanding the output log. Is there documentation about that? I didn't find anything in the manual. Especially the "Balance" part for the constraints. What does the "1.180 out of 0.000" or "1.091 out of 0.364" actually mean?
Thank you very much.
Submitted by Chrigi on Mon, 2014-08-11 04:01
»
- Login to post comments
RE: In cases like that, I will
In cases like that, I will try the recursive bisectioning approach instead of the k-way partitioning.
Also, you may want to try different seeds and see if any of the solutions that come are better balanced.
As far interpretation of the output, constraint #4: 1.091 out of 0.364 indicates that there is a vertex whose 4th weight is already 36.4% of the weight that each partition can have (i.e., a very heavy node, which can create balancing problems).
george
RE: George, I also use multi
George,
I also use multi constraints and K-way. And I also found the workaround to call RSB routine in place of KWAY when I encounter some bad load-balancing.
Especially, in the case I often encounter, with most of all domains well balanced except one.
In such cases, it generally works better with RSB but not every time unfortunatelly.
My general observation, maybe it is only me, is that for load-balancing multi constraints, the previous version of Metis was really better. But for the rest, and especially memory management, latest Metis is really great!
Chrigi,
By chance, did you try your example with previous Metis version?
Eric.