10000 Does recursive Bisection support breadth-first algorithm in the future? · Issue #144 · kahypar/kahypar · GitHub
[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to content

Does recursive Bisection support breadth-first algorithm in the future? #144

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.

Sign up for GitHub

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

Jump to bottom
Closed
lucifer4011 opened this issue Feb 24, 2023 · 7 comments
Closed

Does recursive Bisection support breadth-first algorithm in the future? #144

lucifer4011 opened this issue Feb 24, 2023 · 7 comments

Comments

@lucifer4011
Copy link

The code in func (recursive_bisection) only supports Depth-first algorithm. it means that the partition processes one side completely by recursive bisection , and then processes the other side. But i find the result is very worse when the part is large.

Does recursive Bisection Support support breadth-first algorithm in the future? I guess the feature will improve performance significantly.

thanks for your reply!
@SebastianSchlag
Copy link
Member

Hey @lucifer4011,
Thanks for reaching out. I'm not sure I follow. In traditional recursive bipartitioning (RB), it actually shouldn't matter whether you first completely bipartition one block of the initial two-way partition or if you alternate between the blocks, since refinement algorithms only work on "the current" partition and usually don't involve the other, already partitioned/unpartitioned blocks.
A general problem of RB algorithms is that with each additional bisection the resulting blocks will become "more difficult" to bipartition, because the corresponding subhypergraphs become denser and denser.

Out of curiosity: What values of $k$ are you using? What quality measure are you referring to? Is the quality worse compared to a different hypergraph partitioning algorithm or worse compared to a partition into fewer blocks?

In general, and if $k$ is not too large, using the multi-level direct $k$-way partitioning approach has resulted in partitions of higher quality compared to recursive-bipartitioning approach.

@lucifer4011
Copy link
Author
lucifer4011 commented Feb 27, 2023 •
edited
Loading

@SebastianSchlag
Thank you very much for your reply.
Maybe I didn't describe the problem well. In our application case, we want to divide K (K>=200) vertices into K parts, and then map the K parts to K physical positions, while minimizing the target value Cut or Connectivity. This means that the physical distance between each part is different. As far as I know, the part Id obtained by Kahypar is a logical concept , which is just a symbol. and suppose that the distance between each part is equal. The current algorithm only considers the number of cuts or connectivity. but does not consider the impact of different part Id.
Therefore, I don't know whether there is a good way to solve this problem. Make the K parts have the meaning of physical location.
for example k =4
image

@SebastianSchlag
Copy link
Member
SebastianSchlag commented Feb 27, 2023 •
edited
Loading

Thanks a lot for your explanation!

As far as I know, the part Id obtained by Kahypar is a logical concept , which is just a symbol. and suppose that the distance between each part is equal.

Yes that's correct. To KaHyPar, both of the partitions in your figure are identical.

I'm not entirely sure if it would help in your case, but one thing you could maybe look into is using fixed vertices in your hypergraph to encode some locality information.

@lucifer4011
Copy link
Author

@SebastianSchlag
Thank you. I have tried to set the outermost vertex as a fixed physical point, but the result shows that the part in the center is still chaotic.
Anyway, thank you very much for your reply. Let me think about how to apply it better. Maybe I can use bisection combined with terminal propagation algorithm to solve this problem.

@kittobi1992
Copy link
Member

The problem which you describe is an application of process mapping. I already describe this problem in another issue (see Issue #126). You can also find there some useful references. We currently plan to integrate this feature into Mt-Kahypar, which is the shared-memory parallelisation of KaHyPar. I will keep you updated once it is available.

@lucifer4011
Copy link
Author

@kittobi1992 thaks! The cause of the previous problem has been found. It is because kahypar is the concept of a logical part, which means that the interval between each part is the same. That's why the above problem occurs. I have found another way to solve it. Thanks!

@kittobi1992
Copy link
Member
kittobi1992 commented Apr 10, 2023 •
edited
Loading

The process mapping problem takes the distance between two blocks into account and has also a rich literature. But it is great to hear that you found another solution 😉

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@SebastianSchlag @kittobi1992 @lucifer4011
0