基于超图模型的大规模门级网表层次化聚类算法 - 多维数据分析实验室.PDF

第 2l卷 第 1期 计算机辅助设计与图形学学报 Vo1．21，No．1 2009年 1月 JOURNAIOFCOMPUTER—AIDEDDESIGN COMPUTER GRAPHICS Jan．，2009 基于超图模型的大规模 门级网表层次化聚类算法 蒿 杰 彭思龙 (中国科学 院 自动化研究所围家专用集成 电路设计工程研究中心 北京 100190) (simonsumig@yahoo．co171．cn) 摘 要 为了克服现有层次化方法通用性差、运算效率不高、电路结构提取不准等缺点，提 出了一种基于超 图模型 的层次化聚类算法．首先对网表中最基本的迭代、总线、扇入和串联结构进行 自动识别，然后将这 4种基本结构按不 同的组合方式进行多级聚类 ，最终建立起了网表的层次化结构 ．由于文 中基本结构聚类算法是专 门针对超图数据结 构设计 的，其时间复杂度较低 ．实验结果表明，该算法既可 以得到较准确的层次信息，又能保证较高的运算速度 ，对 各种应用均有较好 的效果． 关键词 层次化 ；聚类 ；超图；超大规模集成 电路 中图法分类号 TP391．72 Hypergraph-BasedNetlistHierarchicalClusteringAlgorithm Hao]ie PengSilong (NationalASICDesignEngineeringCenter，InstituteofAutomation，ChineseAcademyofSciences，Beijing 100190) Abstract For extracting hierarchicalcircuit structures effectively in different applications， a clustering algorithm based on hypergraph modelisproposed ． Firstly，basic characteristic circuit structuressuch asthe iterative structure，the bus structure，the fan—in structure and the series structure are recognized automatically． Then， by multilevel clustering， hierarchica1 design is constructed from thesebasicstructures． Ourclustering algorithm forbasicstructuresisahigh— efficiencymethodduetoagoodadaptabilityforhypergraph datastructure Experimentalresultsshow ． thattheproposedalgorithm canobtainexacthierarchica1informationwithalow timecomplexitv ． Keywords hierarchy；clustering；hypergraph；VLSIcircuits 随着集成电路工艺的发展 ，电路网表 的规模越 小的时间复杂度 ，还要能够得到较准确的结构、功能 来越大 ，而常用 的EDA工具很难直接在最底层网 方面的信息，有的算法还需保证一定 的网表规模下 表上进行操作．在有关划分 、布局 引、版图原理