Application On The Ant Colony Algorithm Used For Physical Design Of Integrated Circuits

With the increasing of the Integrated Circuit scale, decreasing of IC characteristic size, system clock frequency become higher, IC technology has encountered a lot of challenges. The most important issue is that the development of technique has greatly dropt behind of the productivity ability. On the other hand, along with VLSI complexity becomes more and more high, many problems of the physical design in VLSI have already been proved is a NP-hard problem, so a fast and efficient physical layout design has to dependent on advanced EDA method. At the same time, in the field of computation intelligence, various optimized techniques have provided new thoughts and methods whatever in not-NP, NP-complete or NP-hard problem. Under this background this dissertation is intended to discuss the application of computation intelligence method in physical design which is the most important tache in VLSI design.Along with continuously development of the VLSI craft, the scale of the routing problem in physical design sharply augments. Traditional optimization algorithms are facing with expansion of computation, easily sinking into local extremum and can't close to global optimization, so we need to find out more efficient routing algorithms. In this dissertation, firstly we introduced the theory of ACS(Ant Colony System) combined the trip salesmen problem(TSP); Secondly, introduced a shortest path between two distinguished points among rectilinear obstacles under BBL(Building Blocks Layout) mold; Thirdly, discussed establishment of the connection graph and solution both grid model (symmetrical grid and asymmetric grid) and gridless model using ACS algorithm; At last we discussed the solution in multi-layer router and multi-terminal net router, also proved the feasibility of the ACS algorithm in some other router problem(such as in minimum-cost\ capability-driven routing issue).