| Currently, Integrated Circuit(IC) industry is progressing rapidly in deep sub-micron technology aiming at tackling the barrier of wire width at 45nm and 15nm.The trend has been bringing great challenges for existing EDA(Electronic Design Automation) tools, One of which is that many NP-hard problems are impossible or very difficult to be solved by traditional optimal algorithms for VLSI circuits. Another is that many new and particular deep sub-micron technology problems had not been well considered, which will influence chip's performance to some degree. Meanwhile, in the field of computational intelligence, many optimization techniques shows their great power and potential in solving large-scale and very large-scale complex problems in EDA field. 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 the support of Sichuan Science and Technology Bureau Foundation, this dissertation is intended to report some of our research results on channel routing and Over-the-Cell channel routing and performance-driven physical design of the VLSI circuits based on bubble-sorting 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 solving the crosstalk minimization problem met in non-Manhattan channel routing.Main contributions of this thesis are summarized as the following:1, By the researching of the General Graph Theoretic Framework for ChannelRouting, we present the general graph theoretic framework for over-the-cell channelrouting in the standard cell design technology. Considering the particularity of theover-the-cell area, we define a new constraint on the nets and find a novel solution... |
