Research On Algorithms For Solving Key Problems In VLSI Physical Design

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.