Based On Sequences Of The Tabu Search Algorithm In Vlsi The Bbl Layout

Now the technology of integrated circuit industry has already broken through the characteristic minimum size of 100nm, and the CPU based on 90nm will be launched in this year. The industry, as a whole, has been progressing rapidly in deep sub-micron technology. This trend has put great challenges for the present available tools of electric design automation. One of the challenges is that many new and specific deep sub-micron technology problems had not been considered, which will affect significantly chip's performance. The other is that many NP-hard problem is impossible or very difficult to be solved by using traditional optimum algorithms. Meantime, in the field of computational intelligence, a plenty of optimization techniques have showing their great capacity and potential in solving large-scale complex problems. Based on this background and by the support of the project "The application of the computational intelligence in VLSI physical design" from Sichuan Science and Technology Bureau Foundation, this dissertation is intended to develop a tabu search algorithm based on computational intelligence methodology for the placement of VLSI physical design.Because of the benefit of the BBL design mode and the insufficiency of the work on it, this dissertation merges the popular representation - "Sequence Pair" of the placement and the tabu search algorithm, then applies to solve the BBL placement. Based on experiments and the analyses using the related theories, constructive placement is created and some important parameters crucial for tabu search are decided. By the comparison of other algorithms, the experimental results show that the algorithm is effective and of high efficiency. Moreover, some related topics of the algorithm are given, such as the focus on optimization, the relationship between the convergence and the events happened with small probability. According to the shortage of the results given in this thesis, some comments on the improvement of the main frame of the tabu search algorithm are presented.