Vlsi Floorplanning Algorithm

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.