Research And Application On Computational Intelligence For VLSI Physical Design

Very large scale integrated circuit design is progressing rapidly in deep sub-micron technology, which has broken through the characteristic minimum size of 100nm. This trend has put great challenges for the present available tools of electric design automation(EDA). It is impossible or very difficult to solve these highly complex problems by merely using traditional optimization algorithms. Besides, many newly emerging and specific deep sub-micron technology problems, which will significantly influence chip's performance,should be taken into account in modern EDA design tools. As far as the VLSI physical design is concerned, many problems have been proved to be NP-complete, such as placement, global routing and detailed routing.On the other hand,the computational intelligence, a novel approach of optimization techniques have showing its great capacity and potential in solving large-scale complex problems,hence the study of computational intelligence methods to solve existing problems is very necessary for high performance physical design in the deep sub-micron technology.Under this background ,based on the China Post-Doctorate Foundation and the project entitled "Application of the computational intelligence in VLSI physical design" of SiChuan Science and Technology Bureau, this dissertation is intended to develop some algorithms for VLSI physical design based on computational intelligence methodology.The main contributions of this dissertation are summarized as follows:1) Introduce the fractal technique into the VLSI physical design area. A novel fractal approach has been developed to estimate the wire-length of placement. The comparison between traditional methods and the new approach has been done. The simulation result obtained by the new algorithm is superior to that of the old one. This fact implies that the fractal algorithm is very effective and in practical.2) By combining the tabu search and the clustering technique, we propose a hybird algorithm to solve the placement problems,both for the BBL and the gate-array placement.Simulation results show that our hybird algorithm is of robustness and effectiveness,it is expected the algorithm is also uesful in other optimization problems. To testify the feasibility of using various computational intelligent algorithm, such as neural networks,genetic algorithm and ant colony system approach in solving a3) typical routing problem two terminal netlist routing, a comparative study of these algorithms with respect to a traditional approach maze routing algorithm is conducted. Simulation results show that the computational intelligent algorithms are superior to the traditional one.4) A method based on mean field annealing is designed to solve the channel routing, a comparative study with respect to Hopfield neural network approach is performced. Simulation results indicate that our algorithm is able to give high quality solution and remarkably reduced computation time...