An Improved Evolutionary Ant Colony Algorithm In Ultra-deep Sub-micron Vlsi Circuits Around The Barrier Wiring Problem In The Application

Since IC came forth, its evolution have almost accorded with the rule of Moore. Now the technology of IC had broken through the barrier of wire width at 100nm. With the condition of this, more and more problems of Physical Design of VLSI circuits change into NP-hard problem. Not only that but also the capacity of Physical Design of VLSI circuits itself do not catch up with the development of the technology of VLSI. For VLSI circuits, on the one hand many NP-hard problems are impossible or very difficult to be solved by using traditional optimum algorithms; on the other hand is that many new and specific deep sub-micron technology problems had not been considered, which will influence chip's performance. The same time, in the field of computational intelligence, a number of optimization techniques have showing their great capacity and potential in solving large-scale complex problems. Under this background and support of Sichuan Science and Technology Bureau Foundation, this dissertation is intended to report some of our research results for sloving routing problems of the VLSI circuits based on computational intelligence methodology. With the rapid progress in deep sub-micron technology, most of the routing problems raised in physical design of VLSI chips, whatever they are not-NP hard, NP complete or NP difficult, are demanding more efficient routing algorithms. This dissertation is mainly devoted to find a shortest path between two distinguished points among rectilinear obstacles under BBL mode, for both asymmetric grid graph and grid-off model. We have proposed two kinds of graphic model which allow us to reduce the spatial-temporal complexity of problem significantly. Based on these graphic models an efficient routing algorithm , called IEACS (Intensified Evolutionary Ant Colony System) algorithm is suggested. IEACS merges the ACS (Ant Colony System) and GA (Genetic Algorithm), thus features both the mechanism of cooperative learning of ACS and the information-exchange capability of GA, is presented in this thesis. In case of asymmetric grid graph and grid-off graphrouting, the IEACS algorithm is shown o be effective in finding a shortest path between two distinguished points among rectilinear obstacles. The effectiveness of IEACS is justified by some examples. Finally, the usefulness of solving other kinds of routing problems is also discussed.