-
Notifications
You must be signed in to change notification settings - Fork 90
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Performance of coarsing for super large case #36
Comments
Hi, Is there algorithm that based on coarsing on edge, instead of node ? Best wishes, |
Hi, 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.
Could you please elaborate on that? Best, |
Hi Sebastian, Thanks for your reply. Best wishes, |
Hi Frandy,
Ok, then at least we can rule out that the running time is due to assertions in debug mode.
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:
Unfortunately, I think you won't become faster than PaToH, even if you disable refinement in KaHyPar.
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.
Feel free to upload the hypergraph here: https://www.dropbox.com/request/qbzbbb5hHnHkgjmCyxLq
|
Hi Sebastian, I have upload the data into Baidu Netdisk, you can download with below link: Best wishes, |
Hi Jiandong, |
@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 :( |
Hi, sorry. |
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. |
Got it. |
Hi Sebastian, Tried below change, the 1st pass of coarsing reduce to 282s, and total coarsing time reduce from 2158s to 642s. Best wishes, |
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. ;-) |
ok, I'll give you my graph reader and test program later. |
Hi Sebastian, Here is the graph reader and my test program. Best wishes, |
Hi Sebastian, About coarsing, I wonder if it is ok to collapse edge ? Best wishes, |
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. |
Hi,
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.
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: Best
|
Hi Sebastian, Thanks for your advice. Best wishes, |
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
The text was updated successfully, but these errors were encountered: