Genetic Algorithm Applied Research In Vlsi Design Automation

Genetic algorithms (GAs) is a kind of self-adoption heuristic iterative global search algorithm. It has been used to deal with many difficult problems. Genetic algorithms is not only a optimize algorithm, but also a basic method that stemmed from evolutionary theory. It has many good characteristics, such as parallel search, global optimization, unreliable to problem model. And it can be programmed easily with high efficiency. Specific study on VLSI circuit partition, placement and floor-planning, routing, test pattern generation and test set minimization problems with the foundation of elaborate on the theory of GAs were presented on this dissertation. And the relevant genetic algorithms were designed. The main works and creative methods as follows: 1. The history of Genetic algorithms was retrospect simply and the state-of-the-art development was introduced. And the effect of reproduction operator, crossover operator and mutation operator was discussed. The Building Block Theory, Schema theory and the No Free Lunch theory were reported. Finally, the structure of GAs and the important components of GA was presented. 2. The property and characteristic of VLSI circuit partition was analyzed. An algorithm based GAs for VLSI circuit partition was designed. The algorithm can treat with 2-partition and K-partition problems, and also it can deal with area constrained multi-objective partition problem. And the satisfied results were obtained. 3. Placement and floor-planning problem was researched intensively. And a floor-planning algorithm that based on GAs was brought forward. The aspect of soft-block and the direction of hard-block was coded in chromosomes. And novel heuristic decoding method was designed. It can optimize multi-objective problem with area constrain and length of interconnections constrain. The experimental results show that the method could get better results than other floor-planning algorithms. 4. A via minimization algorithm for multi-layer channel routing is presented. The algorithm, which is based on unreserved layer model, firstly assign all nets to proper layers according to the positional relation between each net by using genetic algorithms, then using genetic algorithm to get a best order vector of the concerned layers nets, and finally assign each net to proper tracks with deposit algorithm. It overcomes the disadvantage of original assignment affecting to the final result in traditional via minimization algorithms. This algorithm has been proved to have a better result on via minimization. 5. The test pattern generation algorithms for combinational logic circuit and the fault types were discussed. And the pseudo-exhaustive algorithm was analyzed intensively. A partition-oriented algorithm and a Render-oriented algorithm for pseudo-exhaustive based on GAs were designed. The quantity of test vectors used by exhaustive test pattern generation can be decreased seriously. And it is of great importance to accelerate testing period and reduce testing cost. 6. The test sets minimization was discussed. According to the analysis on chromosome coding and evaluation function, faults-oriented coding genetic algorithm and test-vector-oriented coding genetic algorithm were designed for the minimization of test set. The methods were tested by practical examples, and the satisfied results were obtained.