Hypergraph-Based Netlist Hierarchical Clustering Algorithm

For extracting hierarchical circuit structures effectively in different applications,a clustering algorithm based on hypergraph model is proposed.Firstly,basic characteristic circuit structures such as the iterative structure,the bus structure,the fan-in structure and the series structure are recognized automatically.Then,by multilevel clustering,hierarchical design is constructed from these basic structures.Our clustering algorithm for basic structures is a high-efficiency method due to a good adaptability for hypergraph data structure.Experimental results show that the proposed algorithm can obtain exact hierarchical information with a low time complexity.