A Recursive Partitioning Approach to Improving Hypergraph Partitioning

Balanced hypergraph partitioning (BHP) is a fundamental combinatorial optimization problem in application specific integrated circuit (ASIC) and field-programmable gate array (FPGA) design flows. Multi-level partitioners (MLP) comprise a set of heuristics and are a popular way to solve BHP problems. The BHP problem becomes more complex when the number of partitions (K) is large. Recursive bi-partitioning is a traditional way to solve the problem for larger values of K. However, recursive bi-partitioning is usable for only a smaller number of partitions. This work proposes to generalize recursive bi-partitioning to recursive K-way partitioning to make recursive partitioning usable for all non-prime values of K. The practical usefulness of the proposed recursive method was evaluated by enhancing a recent MLP, TritonPart, and assessed the performance using Titan23 benchmarks. The proposed recursive method helped TritonPart to successfully solve problems with larger K values than it could solve without using the proposed method. Secondly, it also improved the runtime of TritonPart. A comparison with MT-KaHyPar showed it can find solutions with 80% lower cutsize. In short, the proposed recursive method is a useful way to enhance the capability of existing MLPs in terms of their runtime and ability to solve problems of larger K values.