Topology Optimization Design Of Power/Ground Nets And Application Of An EACS Algorithm To Multi-terminal Net's Obstacle Detour Routing In VLSI Circuit Physical Design

In VLSI circuit physical design, it's crucial to get a good P/G (Power/Ground) nets topology design since the result of P/G nets routing could affect the whole chip's area and electricity performance significantly.Recently, some researchers have presented some effective algorithms for P/G nets topology design, but up to now, there are few algorithms considering the relevant constrains in the stage of topology optimization. In fact, without these kinds of performance consideration, it's difficult for us to take full advantage of the existing conditions to improve the chip performance further.Based on the analysis of noise uniform distribution and reliability of module operation, in this thesis, we present a synchronizing method for the optimum design of P/G nets topology. Experimental results demonstrate that our approach is able to give more uniform noise distribution and better operating reliability.On the other hand, with the rapid progress in very-deep sub-micron (VDSM) 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,such as some computational intelligence algorithms. Accordingly, in this thesis we propose a novel gridless routing algorithm for solving obstacle detoured multi-terminal net routing problem in physical design of VLSI circuits. Firstly, this algorithm maps a given routing instance to the corresponding graph model (Path Graph), which is a kind of asymmetric grid graph suitable for BBL (Building Block Layout) mode. After that, we complete the main routing process based on an EACS (Evolutionary Ant Colony System) algorithm in which the crossover operation in GA (Genetic Algorithm) is introduced into the ACS (Ant Colony System) algorithm. Finally, the given simulation experiment results obtained by the use of the EACS algorithm demonstrate that it is very effective in obstacle detoured routing of VLSI circuit physical design.