超大规模集成电路的聚类与划分算法

CORC > 自动化研究所 > 中国科学院自动化研究所 > 毕业生 > 博士学位论文

题名	超大规模集成电路的聚类与划分算法
作者	蒿杰
学位类别	工学博士
答辩日期	2009-05-24
授予单位	中国科学院研究生院
授予地点	中国科学院自动化研究所
导师	彭思龙
关键词	层次化聚类多级划分时序分析功耗分析独立线长预测 Hierarchical Clustering Multilevel Partitioning Timing Analysis Power Analysis Individual Wirelength Precdition
其他题名	Clustering and Partitioning Algorithm for Very Large Scale Integration Circuits
学位专业	计算机应用技术
中文摘要	聚类与划分算法分别采用自底向上和自顶向下的方法对电路进行层次化操作和分割操作，有效提高了EDA工具处理大规模电路的效率。本文着重研究了可进行特殊结构识别与处理的层次化聚类算法、时序驱动的多级划分算法、早期性能评估中所需的线长预测算法及其在性能驱动FPGA聚类算法中的应用。在层次化聚类算法方面，本文提出一种基于超图模型的高通用性层次化聚类算法。首先对网表中最基本的迭代、总线、扇入和串联结构进行自动识别，然后再按不同的组合方式进行多级聚类，最终建立起了网表的层次化结构。实验结果表明，该算法既可以得到较准确的层次信息又能保证较高的运算速度。本文在时序驱动的多级划分算法方面，分别提出了基于通路和基于线网的两种算法。对于基于通路的算法，首先通过聚类保护降低关键通路被分割的几率，减小后续操作对最小割目标的影响。然后使用划分保护控制通路被分割的次数，将关键通路时延限定在指定时钟周期之内。与现有算法相比，该算法不仅可以完全控制关键通路时延，而且只需对最底层网表进行一次时序分析。在基于线网的多级划分算法中，本文通过提出线网通路群的概念，使用全局性较强且计算代价较小的线网通路群关键度表示线网的时延权重，并以此指导划分操作。实验表明，在对线长目标影响较小的情况下，该方法不仅可以有效提高电路的时序性能，而且能够有效减小时序振荡现象。在性能驱动的聚类、划分算法中，需要使用预测线长值估算目标函数中的性能相关量，为此本文提出一种基于拓扑结构的线长预测模型。在拓扑级和物理级的定义下，首先依据布局区域假设，使用虚拟的物理级作为中间变量表示线长的预估值；然后根据拓扑级中结点的布放格式假设，使用已知的拓扑级代替物理级作为线长预估值的表示量。实验表明，该方法在预测精度和运算时间上全面优于MC和重回聚方法。另外，本文将线长预测方法应用到了性能驱动的FPGA聚类算法中。在聚类阶段，分别将关键通路上的线网和功耗值较大的线网用局部布线资源实现，以便提高时序性能和减小动态功耗。
英文摘要	This thesis researches coupling bottom-up clustering and top-down partitioning algorithm to improve the efficiency of EDA tool. We investigate clustering and partitioning algorithms for three kinds of applications, and it mainly includes hierarchical clustering algorithm for specified structures, timing-driven multilevel partitioning algorithm, wirelength prediction algorithm and its application for performance driven FPGA clustering. In hierarchical clustering, a novel 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. Experiments show that our algorithm can obtain exact hierarchical information with a low time complexity. In timing-driven multilevel partitioning algrithm, path-based and net-based algorithms are proposed, respectivly. In the clustering phase of path-based algrithm, for simultaneous cutsize and circuit delay minimization, the more critical and independent paths are clustered in the finer netlist. During the partitioning phase, critical path delay can satisfy the specified timing constrains by controlling the number of path cut. Our scheme is capable of overcoming drawbacks of current path-based timing-driven multilevel partitioning algorithms: uncontrolled path cut and frequent timing analysis. The experiments show a good trade-off between cutsize and delay is obtained in our algorithm. In net-based multilevel partitioning algorithm, according to the number of paths and path delay distribution characteristic in the path-group of a net, we obtain the net delay weight using 3-level weighting method. Experiments show that our method can effectively reduce critical path delay and timing oscillation with little wirelength increase. In performance-driven clustering and partitioning algorithm, we estimate the delay and power value using predicted wirelength because we can’t obtain the actual wirelength before placemeng and routing. In this paper, we propose a novel predicted model by the generic theoretical framework for wirelength prediction based on topological structure, which can be used for analysis and estimation...
语种	中文
其他标识符	200618014629094
内容类型	学位论文
源URL	[http://ir.ia.ac.cn/handle/173211/6151]
专题	毕业生_博士学位论文
推荐引用方式 GB/T 7714	蒿杰. 超大规模集成电路的聚类与划分算法[D]. 中国科学院自动化研究所. 中国科学院研究生院. 2009.