基于超图模型的大规模门级网表层次化聚类算法

Hypergraph-Based Netlist Hierarchical Clustering Algorithm

为了克服现有层次化方法通用性差、运算效率不高、电路结构提取不准等缺点,提出了一种基于超图模型的层次化聚类算法.首先对网表中最基本的迭代、总线、扇入和串联结构进行自动识别,然后将这4种基本结构按不同的组合方式进行多级聚类,最终建立起了网表的层次化结构.由于文中基本结构聚类算法是专门针对超图数据结构设计的,其时间复杂度较低.实验结果表明,该算法既可以得到较准确的层次信息,又能保证较高的运算速度,对各种应用均有较好的效果.

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.