Ant Colony Algorithm In The Deep Sub-micron Vlsi Circuits Around The Obstacles To Wiring Problems

Now integrated circuit industry is evolving rapidly in deep sub-micron technology aimed at overcoming the barrier of wire width at lOOnm. This trend has put great challenges for the recently available tools of electronic design automation. One of the challenges is that for VLSI circuits, many NP-hard problem is impossible or very difficult to be solved using traditional optimum algorithms; the other is that many new and specific deep sub-micron technology problems had not been considered, which will influence chip's performance. And at the same time, in the field of computational intelligence, a number of optimization techniques have shown their great power and potential in solving large-scale complex problems. In "The Tenth Five-Year Plan"of China, software industry and IC industry were set to be the two most important fields of Chinese high-tech development programs. Under this background and support of Sichuan Science and Technology Bureau Foundation, this dissertation is intended to report some of our research results on performance-driven physical design 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 VisI chips, whatever they arenot-NP hard, NP comp1ete or NP difficult, are demanding more efficient routingalgorithms. This dissertation is mainly devoted to find a shortest path betweentwo dishnguished points among rectilinear obstacles under BBL mode, for bothghded and gridless model. Tho kinds of graphic model based on graphic-theoryand computational-geometry are presented. The new models are caPable ofsignificantly reducing the spatial-temporal complexity of the routing algorithms.Then an efficient routing algorithm, Intensified ACS (Ant Colony--System)algorithm, is presented in this thesis. By using the mechanism of cooperativelearning and working, the ACS a1gorithm a1lows us to route nets yielded fromthe aforementioned graph models efficiently. Finally, performance-drivenrouting a1gorithms witb physical constraints by applying ACS are discussed.