NOIP: Node Overlay Initial Partitioning Technique for Hypergraph Partitioning Problem

The hypergraph partitioning problem with the goal of minimizing the cut-size has extensive applications in the field of EDA. As an NP-hard problem, the industry commonly uses heuristic-based multilevel partitioning schemes to solve this problem. However, some well-known partitioners, like hMETIS and KaHyPar, each stage in the partitioning process is relatively independent, failing to make full use of the existing partitioning information. We propose a novel initial partitioning algorithm named Node Overlay Initial Partitioning (NOIP). This algorithm uses the existing partitioning results in the initial partitioning to find the fixed vertices at the maximum degree of overlay, and these fixed vertices are used to guide the subsequent initial partitioning. Through experiments based on Titan23, the partitioner integrated with NOIP can achieve a cut-size 0.86 times that of hMETIS within comparable time. Meanwhile, its characteristic of making full use of existing information during the partitioning process also brings new idea to the multilevel partitioning scheme, which enables the partitioner to achieve better results without consuming more time and resources.