超大规模集成电路的平面布图规划算法研究

【作者】 赵长虹；

【导师】 周电；

【作者基本信息】 复旦大学 ， 微电子学与固体电子学， 2006， 博士

【摘要】 随着超大规模集成电路的飞速发展，越来越多的模块被集成到同一块芯片上，基于分级的设计流程已成为必然趋势，因此平面布图规划越来越重要。基于这样的原因，本文深入探讨了平面布图规划的各种表示方法，主要研究了传统的平面布图规划问题和新约束条件下的平面布图规划问题。在传统的平面布图规划领域的研究中，提出基于权重的平面布图规划算法和基于线性规划的软模块调整方法。在考虑各种新约束的平面布图规划算法中，提出多时钟系统的平面布图规划算法和考虑电压降的平面布图规划算法。在基于权重的平面布图规划算法研究中，针对各个模块的面积以及长边长度的不同提出权重的概念，并在此基础上提出基于权重的布图规划算法，该算法根据各个模块权重的不同在优化过程中以不同概率选择相应的模块，克服了原有算法以相同的概率选择各个模块的缺点，达到了更好的布图规划效果。针对软模块的调整问题，本文分析了基于最优化求解超大规模集成电路平面布图规划的方法，对目标函数中的芯片面积本文提出通过估计芯片的长宽比对目标函数进行线性化。此外本文提出利用分段线性的方法对模块面积约束条件线性化，保证了解空间的可行性。实验结果表明使用本文提出的线性规划模型在保证了解空间可行性的同时达到了良好的布图规划效果。针对多时钟系统的平面布图规划，本文给出了容许的多时钟系统平面布图的定义以及相应的定理和证明，并基于序列对表示法和模拟退火算法提出了多时钟系统平面布图规划算法，对软模块的优化采用了线性规划的方法。本文提出算法在不增加时间复杂度的前提下，根据多时钟系统的特点大大减小了解空间。实验结果表明本文提出的算法对多时钟域平面布图规划有良好效果。随着集成电路工艺发展，工作电压降低，功耗密度增大，电源网络电压降的问题将越发突出。本文提出在平面布图规划阶段考虑电压降约束，在物理设计初期解决电压降问题，从而加快了物理设计收敛。首先提出了一个快速而满足一定精度的量化电压降的模型，然后基于模拟退火算法和序列对表示法提出考虑电压降的平面布图算法。对软模块的优化采用了线性规划的方法。实验结果表明，本算法在达到良好的平面布图规划效果的同时，有效地降低芯片的平均电压降以及最大电压降。更多还原

【Abstract】 With the fast scaling of integrated circuit technology and the dramatic increase in the complexity of VLSI circuits, IP reuse is becoming a trend. More and more IPs are integrated on a chip. Circuits with such complexity have to be designed hierarchically. As a result, floorplan is becoming more and more important. The study of this dissertation is focused on the traditional floorplanning and the floorplanning with constraints. In the study of traditional floorplanning, the floorplanning algorithm based on weight and the method to adjust soft blocks based on linear programming are presented. In the study of floorplanning with constraints, floorplanning algorithms with multiple clock domains and IR-Drop consideration are presented. In the study of floorplanning algorithm based on weight, this dissertation presents the weight model of each block and the corresponding floorplanning algorithm based on B~*-tree. In the optimization process, blocks with different weight are selected with different probability. Experiments show that this algorithm improves the quality of floorplanning compared with the floorplanning algorithm of B~*-tree. In the study of the adjustment of soft blocks, this dissertation analyzes the floorplanning methods based on linear programming and presents a linear replacement of the non-linear objective function by estimating the chip ratio. It also presents the sub-section linearization methods to replace the nonlinear items in the constraint inequalities. Different from former floorplanning methods based on linear programming, solutions of the method in the dissertation always lie in the feasible region of the original floorplanning model based on mathematical programming. Experiments show that good results can be obtained with solutions always lying in the feasible region by our linear programming model.In the study of floorplanning algorithm with multiple clock domains, this dissertation presents the model of floorplanning with multiple clock domains and the corresponding algorithms based on simulated annealing algorithm and sequence pair representation. The main contribution is to solve the floorplanning problem with multiple clock domains while the solution space is decreased dramatically. In the process of soft blocks adjustment, linear programming is used to optimize the chip area. Experiments show that good results can be obtained for the floorplanning with multiple clock domains by this algorithm.In the study of floorplanning algorithm with IR-drop consideration, IR-drop constraint is considered in order to solve the problem in the early stage of physical design and to shorten the time to market. First, a fast model with some extend of accuracy is proposed to quantify the IR-drop of a block. Then the selection strategy in simulating annealing based on the model is introduced. Experiments show that good results can be obtained with average IR-drop and maximum IR-drop decreased dramatically.更多还原