Performance of coarsing for super large case

[Frandy]

Hi，

I tested one large hypergraph from vlsi circuit with KaHyPar-K config. It is very slow.
The size is hypernode: 11965399, hyperedge: 4586372, pins: 22904645.
In the 1st pass of ml_coarser, it reduces nodes to 4919487, and takes 1001.71s. And
in the 2nd pass, it reduce nodes to 1802051, takes 673.67s.
While patoh can finish partition in 250s.
Do you have any suggestions ?
Maybe I can try special coarsing first, such as for node connect to only one edge? For those node, if weight is not much large, should can be contract safely. Then can avoid heavy rate operation.
How do you think about it ?

Best wishes,
Frandy

[Frandy]

Hi,

Is there algorithm that based on coarsing on edge, instead of node ?
For this hypergraph, edge is only a half of node.
Will it be more effeicient to traverse edges ?

Best wishes,
Frandy

[SebastianSchlag]

Hi,
~1000s seems awfully slow for one iteration of the ml_coarsener. Usually, the main running time bottleneck of KaHyPar is the refinement phase. I just looked at one of my benchmark hypergraphs that has 9845725 nodes, 6920306 hyperedges, and 57156537 pins. There coarsening took only around 180s. Just to be sure, did you build in release mode, i.e. using cmake .. -DCMAKE_BUILD_TYPE=RELEASE? If not, that might explain the large running time.

Is it possible for you to send me the hypergraph so that I can debug the running time issue? Maybe there is some structure in your instance that slows down the coarsening.

Currently there is no coarsening algorithm that contracts entire hyperedges. I played around with this a couple of years ago, but solution quality turned out to be worse.

In general, if you just want a reasonably good partitioning very fast, then PaToH is the way to go. If you aim at getting the best solution quality at the cost of increased running time, then KaHyPar is the better option.

For this hypergraph, edge is only a half of node.

Could you please elaborate on that?

Best,
Sebastian

[Frandy]

Hi Sebastian,

Thanks for your reply.
I build kahypar with release mode.
Yes, refine is also very slow, and I have to turn off refine, and uncoarsing still takes 400s.
We use PaToH before, but we still want to get it faster.
We tried PaToH for bisect in parallel mode, but seems PaToH interface can not be used in multi-thread.
For the large hypergraph, it is about 80M after compress.
I'm afraid I can not send it to you for now. Sorry.

Best wishes,
Frandy

[SebastianSchlag]

Hi Frandy,

Hi Sebastian,

Thanks for your reply.
I build kahypar with release mode.

Ok, then at least we can rule out that the running time is due to assertions in debug mode.

Yes, refine is also very slow, and I have to turn off refine, and uncoarsing still takes 400s.

Hm... I've seen rare occasions where coarsening becomes slow because of of the way nodes are chosen to be contracted. A thing that you could try is modifying:
https://github.com/SebastianSchlag/kahypar/blob/master/kahypar/partition/coarsening/ml_coarsener.h#L106 to the following:
if (_hg.nodeDegree(hn) > _hg.nodeDegree(rating.target)) {
performContraction(hn, rating.target);
} else {
performContraction(rating.target, hn);
}
I've also been working on a faster version of contractions/uncontractions.. however this code is not yet finished, since coarsening was almost never actually a real bottleneck.

We use PaToH before, but we still want to get it faster.

Unfortunately, I think you won't become faster than PaToH, even if you disable refinement in KaHyPar.
Since it is designed to be an n-level algorithm, it will always be slower then PaToH.

We tried PaToH for bisect in parallel mode, but seems PaToH interface can not be used in multi-thread.

Yes. I think that won't work. There has been a huge amount of effort put into PaToH's memory management etc. to make it as fast as possible. I think that multi-threading is not supported.

For the large hypergraph, it is about 80M after compress.
I'm afraid I can not send it to you for now. Sorry.

Feel free to upload the hypergraph here: https://www.dropbox.com/request/qbzbbb5hHnHkgjmCyxLq
I would really be interested in debugging this performance issue.

Best wishes,
Frandy

[Frandy]

Hi Sebastian,

I have upload the data into Baidu Netdisk, you can download with below link:
https://pan.baidu.com/s/1uEJOSn-UtCnKfHRxKJFyng

Best wishes,
Jiandong Cheng

[SebastianSchlag]

Hi Jiandong,
thank you very much. I'll take a look at this as soon as possible.

[SebastianSchlag]

@Frandy unfortunately I am not able to download the file from baidu, since it seems that it is not possible to download it without having an account :(

[Frandy]

Hi, sorry.
I have uploaded to the dropbox link you given. please check it.

[SebastianSchlag]

Thanks! I will take a look at it as soon as possible. Might take a couple of days, because I'm currently working towards a deadline. I'll keep you updated.

[Frandy]

Got it.
Thanks.

[Frandy]

Hi Sebastian,

Tried below change, the 1st pass of coarsing reduce to 282s, and total coarsing time reduce from 2158s to 642s.
if (_hg.nodeDegree(hn) > _hg.nodeDegree(rating.target)) {
performContraction(hn, rating.target);
} else {
performContraction(rating.target, hn);
}

Best wishes,
Frandy

[SebastianSchlag]

Thank you very much for the update. I'm pretty sure I know why it is so slow otherwise. I already got an idea on how to fix it / make it more robust (even without the if). However I'll need some time do to the actual implementation.

I downloaded the hypergraph today and noticed that it is in PaToH format. Would it be possible to also upload it in hMetis/KaHyPar Format? I don't have a converter PaToH->hMetis at hand right now. ;-)

[Frandy]

ok, I'll give you my graph reader and test program later.

[Frandy]

Hi Sebastian,

Here is the graph reader and my test program.
https://github.com/Frandy/graph_reader

Best wishes,
Frandy

[Frandy]

Hi Sebastian,

About coarsing, I wonder if it is ok to collapse edge ?
For my case, hyperedge is less than hypernode. When coarsing by heavy edge policy, it start from one hypernode, select the hyperedge with the heavest weight (w(e) / |e| -1, and w(e)=1 in my case ) .
If from the view of hyperedge, it shows the same weight to hypernode around it. How about contract all those node together ?
Or epsically for |e|=2 ?

Best wishes,
Frandy

[SebastianSchlag]

Hi Sebastian,

Here is the graph reader and my test program.
https://github.com/Frandy/graph_reader

Best wishes,
Frandy

Thank you very much. Unfortunately I'm still busy with an upcoming paper deadline, but I'll take a look at it as soon as I can.

[SebastianSchlag]

Hi,

Hi Sebastian,

About coarsing, I wonder if it is ok to collapse edge ?

When I started working on KaHyPar, I added a coarsening strategy that contracted entire hyperedges at once. However, since this provided worse solutions compared to heavy edge node-based coarsening, I did not include it into KaHyPar.

For my case, hyperedge is less than hypernode. When coarsing by heavy edge policy, it start from one hypernode, select the hyperedge with the heavest weight (w(e) / |e| -1, and w(e)=1 in my case ) .
If from the view of hyperedge, it shows the same weight to hypernode around it. How about contract all those node together ?
Or epsically for |e|=2 ?

You could certainly try contracting entire edges at once. Maybe it works reasonably well for your application. In order to write your own coarsening algorithm, you can take a look at this commit:
bce825a
Altough the branch is currently not up-to-date anymore, the commit shows how a new coarsening algorithm can be integrated into the framework.

Best
Sebastian

Best wishes,
Frandy

[Frandy]

Hi Sebastian,

Thanks for your advice.
How do you think about multi-thread for coarsing and uncoarsing ? Or other directions to speedup ?
Hope more discussition after you have time.

Best wishes,
Frandy
.