【作者】 南国芳；

【导师】 寇纪淞；

【作者基本信息】 天津大学 ， 管理科学与工程， 2004， 博士

【摘要】 当前集成电路工艺技术的快速发展冲击着VLSI CAD技术,即CAD软件的发展落后于集成电路工艺技术的发展。这就要求研究人员根据目前的工艺技术不断改进布局布线、逻辑综合及验证工具,开发出更加适合VLSI产业发展的物理设计算法及可靠的集成电路设计软件产品。本文即是在这个思想的引导下展开的,主要研究内容如下:1. 系统阐述了VLSI CAD技术的发展及集成电路物理设计的主要内容,对物理设计中几个重要阶段(如电路划分、标准单元布局和时钟布线)中所采用算法的研究进展做了详细介绍,同时在第二章介绍了物理设计的算法基础。2. 在电路划分问题的研究中,先后提出了K-L改进划分算法、基于聚类技术的F-M电路划分算法、不同编码的遗传算法设计及混合式遗传电路划分算法,前两种方法均为传统启发式算法的改进,较之原有算法得出的结果有所改进。基于不同编码技术的遗传算法设计及混合式遗传算法的提出是该部分的一个创新点。遗传算法中分别采用0-1编码和基于模块编号的整数编码方式,并设计了相应的适应度函数及遗传算子。将两种遗传算法用于标准标杆电路的测试,划分结果得到了较大的改善。混合式遗传算法则是在标准遗传算法的基础上,用整个K-L算法作为变异算子,虽然每一代进化中增加了算法的复杂度,但是总的来说降低了计算时间。3. 针对标准单元布局问题,提出了一种适应性模拟退火算法,在传统的模拟退火算法中引入适应性初始温度和适应性搜索区域的概念,并对标准单元布局中目标函数中的惩罚项作出相应改进,同时对相关的退火策略及参数优化进行了设计。和传统模拟退火算法得出的结果相比,该算法在布局效果上和时间性能上均显示出优越性;利用上述相关策略及参数,还提出了基于遗传算法的标准单元布局算法。4. 时钟信号和时钟偏差对电路性能的影响也越来越明显。针对传统的时钟网络拓扑生成算法存在的不足,提出了 “多级”概念并设计了基于多级遗传算法和多级模拟退火算法的时钟二叉树形成算法。两种方法虽然形式上不同,且有共同的特点。在对随机测试例子和标准标杆测试例子的测试中发现,较之传统的启发式算法,二者都能产生较好的测试结果。更多还原

【Abstract】 The rapid development of IC technology has a great effect on the VLSI CAD technology. The development of CAD software lays behind to IC technology, which requires that researchers improve the existing tools constantly and develop more suitable physical design algorithms and reliable software product for VLSI design according to the latest IC technology, including placement, routing, logic synthesis and verification. This thesis is based on the above idea, and the main contents are as follows:1. The development of VLAI CAD technology and the main contents of physical design are systematically discussed, and researches on algorithms for several key phases (circuit partitioning, standard-cell placement, and clock routing) in VLSI physical design are introduced in detail. At the same time, algorithm basis on physical design is presented in Chapter two.2. In the research on circuit partitioning, several algorithms are presented, such as the improved K-L partitioning algorithm, clustering and F-M based partitioning algorithm, two novel encoding strategies based genetic partitioning algorithms, and a kind of hybrid genetic partitioning algorithm. The former two methods are designed based on traditional heuristic algorithms and they both get better results when compared with their standard algorithms. The two later methods are newly designed in the thesis. These genetic algorithms adapt 0-1 encoding and integer encoding based on module number. The corresponding fitness function and genetic operators are designed. These two algorithms are applied to test several benchmark circuits, and the partitioning results are markedly improved. The hybrid algorithm is based on standard genetic algorithm, and uses the whole K-L algorithm as the mutation operator. Although complexity in each generation is increased, the whole computation time is reduced greatly.3. A standard cell placement algorithm based on adaptive simulated annealing is presented. The adaptively initial temperature and adaptive searching region are added to traditional simulated annealing algorithm, and punishment item in objective function is improved. The annealing strategy and controlling parameters are optimized for standard cell placement problem. Experiments show the advantages of the new algorithm in placement results and time performance while compared with the results by traditional simulated annealing algorithm. Based on corresponding strategies and optimized parameters mentioned above, a kind of genetic algorithm for standard cell placement is also presented.4. Clock signal and clock skew become more and more important in the circuit performance. Due to the shortcomings of traditional algorithms for topology of clock nets, the “multi-level” concept is presented and multi-level genetic algorithm and multi-level simulated annealing algorithm are designed for the construction of clock binary tree. There are differences in forms between two algorithms, but they also have some same characters. In the test of random circuit and benchmark circuit, two algorithms both get better results compared with traditional heuristic algorithms.更多还原