Investigation On The Ant Colony Algorithm Used For Physical Design Of VLSI Circuits

Now integrated circuit industry is evolving rapidly in deep sub-microntechnology aimed at overcoming the barrier of wire width at 100nm. This trend has put treat challenges for the recently available tools of electronic design automation. One of the challenges is that for VLSI circuits, many NP-hard problems 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 dine, in the field of computational intelligence, a number of optimization techniques have shown their great power and potential in solving large-scale complex problems. Under this background, 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 VLSI chips, whatever they are not-NP hard, NP complete or NP difficult, are demanding more efficient routing algorithms.As one of the latter algorithms, ant colony algorithm has been used to many fields, such as: Traveling Salesman Problem, Quadratic Assignment Problem, Network Routing and Load-Balancing Problem, VLSI Design, etc.This dissertation is mainly devoted to find a shortest path between two distinguished points among rectilinear obstacles under BBL mode, for both grided and gridless model. Two kinds of graphic model based on graphic-theory and computational-geometry are presented. The new models are capable of significantly 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 cooperative learning and working, the ACS algorithm allows us to route nets yielded from the aforementioned graph models efficiently.In this dissertation, a gridless net routing with ant colony algorithm for IC design is presented. For a given routing plane, first of all, this algorithm generates the corresponding grid group by barriers and nets' ports, establishes initialization pheromone matrix, then the algorithm will use the character of ant colony algorithm to find out the shortest routing path only if it exits. At the same time, the conception of gravitation is used to find the path in this paper, which can help ants find the aim more quickly.As one of the latter algorithms, particle swarm optimization (PSO) algorithm has been used to many fields. In this dissertation, a gridless net routing with particle swarm optimization algorithm for IC design is presented for the layout of IC design. For a given layout plane, first of all, this algorithm generates the corresponding grid group by barriers and nets' ports with the thought of gridless net routing, establishes initialization fuzzy matrix, then utilizes the global optimization character to find out the best layout route only if it exits. The results of model simulation indicate that PSO algorithm is feasible and efficient in IC layout design.