A Study Of Crosstalk Minimization In A Bubble-sorting-based Non-Manhattan Channel Routing

Now integrated circuit industry is progressing rapidly in deep sub-micron technology aimed at conquering the barrier of wire width at 45nm. 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 by 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 and very 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 non-Manhattan structure 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:As a gridded channel routing problem in physical design of VLSI circuits, we firstly present an approach by using an improved bubble-sorting-based non-Manhattan channel router to minimize the tracks and wire lengths of the channel.The improved non-Manhattan channel router brings forward the crosstalk model in gridded non-Manhattan channel on the basis of the traditional crosstalk model in Manhattan channel. By keeping the tracks constant, an optimization algorithm, which is based on the above-mentioned non-Manhattan channel router and crosstalk model, is designed aiming at minimizing the crosstalk in the channelThe optimization algorithm has been implemented in C++/C and verified through experiments on some benchmarks. Simulation experiment results demonstrate that our algorithm is promising in developing performance-driven routing software package.